#include <iostream>
#include <list>
#include <mutex>
#include <set>
#include <thread>

using namespace std;

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

#define N 8

typedef std::list<int> PositionList;

void print_board(PositionList positions) {
   cout << "\n+"; for (int c = 0; c < N; ++c) cout << "-"; cout << "+\n";
   for (int& col: positions) {
      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) {
   auto it1 = pl1.begin(); auto it2 = pl2.begin();
   while (it1 != pl1.end() && it2 != pl2.end()) {
      if (*it1 != *it2) return *it1 < *it2;
      ++it1; ++it2;
   }
   return it2 != pl2.end();
}

class Results {
   public:
      void add(const PositionList& result) {
	 std::lock_guard<std::mutex> lock(mutex);
	 results.insert(result);
      }
      void print() const {
	 std::lock_guard<std::mutex> lock(mutex);
	 for (const PositionList& result: results) {
	    print_board(result);
	 }
      }
   private:
      mutable std::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),
	    positions(other.positions) {
	 positions.push_back(c);
         INCL(rows, r); INCL(cols, c);
         INCL(diags1, r - c + N - 1);
         INCL(diags2, r + c);
      }
      void operator()() {
	 if (row == N) {
	    results.add(positions);
	 } 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 at (row,col)
	       threads.push_back(std::thread(Thread(*this, row, col)));
	    }
	    for (auto& t: threads) {
	       t.join();
	    }
	 }
      }
   private:
      Results& results;
      std::list<std::thread> 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 positions;
};

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