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

using namespace std;

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

#define N 8


struct Position {
   Position(int r, int c) : row(r), col(c) {
   }
   int row, col;
};
typedef std::list<Position> PositionList;

void print_board(PositionList pos) {
   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";
}

bool operator<(const PositionList& pl1, const PositionList& pl2) {
   PositionList::const_iterator it1 = pl1.begin();
   PositionList::const_iterator it2 = pl2.begin();
   while (it1 != pl1.end() && it2 != pl2.end()) {
      if (it1->row != it2->row) return it1->row < it2->row;
      if (it1->col != it2->col) return it1->col < it2->col;
      ++it1; ++it2;
   }
   return it2 != pl2.end();
}

class Results {
   public:
      void add(const PositionList& result) {
	 boost::lock_guard<boost::mutex> lock(mutex);
	 results.insert(result);
      }
      void print() {
	 boost::lock_guard<boost::mutex> lock(mutex);
	 for (std::set<PositionList>::iterator it = results.begin();
	       it != results.end(); ++it) {
	    print_board(*it);
	 }
      }
   private:
      boost::mutex mutex;
      std::set<PositionList> results;
};

class Thread {
   public:
      Thread(Results& res) :
	 results(res), row(0), rows(0), cols(0), diags1(0), diags2(0) {
      }
      Thread(const Thread& other, int r, int c) :
	    results(other.results),
	    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) {
	    results.add(pos);
	 } 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;
	    }
	 }
      }
   private:
      Results& results;
      typedef std::list<boost::thread*> ThreadList;
      ThreadList threads;
      int row; /* current row */
      /* 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 */
      PositionList pos;
};

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