#include <iostream>
#include <boost/thread.hpp>
#include <boost/thread/mutex.hpp>

using namespace std;

#define INSET(member,set) ((1<<(member))&set)
#define INCL(set,member) ((set) |= 1<<(member))

#define N 8

boost::mutex cout_mutex;

class Thread {
   public:
      Thread() : row(0), rows(0), cols(0), diags1(0), diags2(0) {
      }
      Thread(const Thread& other, int r, int c) :
	    row(r+1), rows(other.rows), cols(other.cols),
	    diags1(other.diags1), diags2(other.diags2),
	    pos(other.pos) {
	 pos.push_back(Position(r, c));
         INCL(rows, r); INCL(cols, c);
         INCL(diags1, r - c + N - 1);
         INCL(diags2, r + c);
      }
      void operator()() {
	 if (row == N) {
	    print_board();
	 } else {
	    for (int col = 0; col < N; ++col) {
	       if (INSET(row, rows)) continue;
	       if (INSET(col, cols)) continue;
	       if (INSET(row - col + N - 1, diags1)) continue;
	       if (INSET(row + col, diags2)) continue;
	       // create new thread with a queen set a (row,col)
	       threads.push_back(new boost::thread(Thread(*this, row, col)));
	    }
	    for (ThreadList::iterator it = threads.begin();
		  it != threads.end(); ++it) {
	       (*it)->join();
	       delete *it;
	    }
	 }
      }
      void print_board() {
	 boost::lock_guard<boost::mutex> lock(cout_mutex);
	 cout << "\n+"; for (int c = 0; c < N; ++c) cout << "-"; cout << "+\n";
	 for (PositionList::iterator it = pos.begin();
	       it != pos.end(); ++it) {
	    int col = it->col;
	    cout << "|";
	    for (int c = 0; c < N; ++c) {
	       if (c == col) {
		  cout << "Q";
	       } else {
		  cout << ".";
	       }
	    }
	    cout << "|" << endl;
	 }
	 cout << "+"; for (int c = 0; c < N; ++c) cout << "-"; cout << "+\n";
      }
   private:
      typedef std::list<boost::thread*> ThreadList;
      ThreadList threads;
      int row; /* current row */
      struct Position {
	 Position(int r, int c) : row(r), col(c) {
	 }
	 int row, col;
      };
      typedef std::list<Position> PositionList;
      PositionList pos;
      /* a queen on (row, col) threatens a row, a column,
	 and 2 diagonals;
	 rows and columns are characterized by their number (0..n-1),
	 the diagonals by row-col+n-1 and row+col,
	 (n is a shorthand for the square size of the board)
      */
      int rows, cols; /* bitmaps of [0..n-1] */
      int diags1; /* bitmap of [0..2*(n-1)] used for row-col+n-1 */
      int diags2; /* bitmap of [0..2*(n-1)] used for row+col */
};

int main() {
   Thread qt;
   boost::thread queens(qt);
   queens.join();
}