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

using namespace std;

/* simple operations on bitsets represented by unsigned int */
constexpr bool in_set(unsigned int member, unsigned int set) {
   return (1<<member) & set;
}
constexpr unsigned int include(unsigned int set, unsigned int member) {
   return set | (1<<member);
}
constexpr unsigned int N = 8; /* side length of chess board */

/* mutex that helps to assure that no more than one thread
   writes to std::cout */
std::mutex cout_mutex;

class Thread {
   public:
      Thread() : row(0), rows(0), cols(0), diags1(0), diags2(0) {
      }
      Thread(const Thread& other, unsigned int r, unsigned int c) :
	    row(r+1), rows(other.rows), cols(other.cols),
	    diags1(other.diags1), diags2(other.diags2),
	    positions(other.positions) {
	 positions.push_back(c);
         rows = include(rows, r); cols = include(cols, c);
         diags1 = include(diags1, r - c + N - 1);
         diags2 = include(diags2, r + c);
      }
      void operator()() {
	 if (row == N) {
	    print_board();
	 } else {
	    for (unsigned int col = 0; col < N; ++col) {
	       if (in_set(row, rows)) continue;
	       if (in_set(col, cols)) continue;
	       if (in_set(row - col + N - 1, diags1)) continue;
	       if (in_set(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 (unsigned int c = 0; c < N; ++c) cout << "-"; cout << "+\n";
	 for (unsigned int col: positions) {
	    cout << "|";
	    for (unsigned int c = 0; c < N; ++c) {
	       if (c == col) {
		  cout << "Q";
	       } else {
		  cout << ".";
	       }
	    }
	    cout << "|" << endl;
	 }
	 cout << "+";
	 for (unsigned int c = 0; c < N; ++c) cout << "-"; cout << "+\n";
      }
   private:
      unsigned 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)
      */
      unsigned int rows, cols; /* bitmaps of [0..n-1] */
      unsigned int diags1; /* bitmap of [0..2*(n-1)] used for row-col+n-1 */
      unsigned int diags2; /* bitmap of [0..2*(n-1)] used for row+col */
      std::list<std::thread> threads; /* list of forked-off threads */
      std::list<unsigned int> positions; /* columns of the queens */
};

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();
}