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

using namespace std;

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

#define N 8

std::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),
	    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) {
	    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 at (row,col)
	       threads.push_back(std::thread(Thread(*this, row, col)));
	    }
	    for (auto& t: threads) {
	       t.join();
	    }
	 }
      }
      void print_board() {
	 std::lock_guard<std::mutex> lock(cout_mutex);
	 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";
      }
   private:
      std::list<std::thread> threads;
      int row; /* current row */
      std::list<int> positions; /* columns of the queens */
      /* 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() {
   /* spawn off the first thread with an empty board;
      note that we need the extra parentheses to avoid this
      being misinterpreted as a function declaration */
   std::thread queens((Thread()));
   queens.join();
}