Eight queens

8queens .cc

#include <array>
#include <atomic>
#include <chrono>
#include <cstdint>
#include <iostream>
#include <set>
#include <unordered_set>
#include <vector>

constexpr int GRID_SIZE = 15;

class board;

int solc = 0;

int rowmasks[GRID_SIZE];
int rowmasks_inv[GRID_SIZE];

void make_masks() {
  for (int i = 0; i < GRID_SIZE; ++i) {
    rowmasks[i] = (1 << i);
    rowmasks_inv[i] = ~(1 << i);
  }
}

struct column {
  int queen_row = -1;
  int allowed = 0xffffffff;

  void remove_allowed(int row) {
    if (row < 0 || row >= GRID_SIZE)
      return;
    allowed &= rowmasks_inv[row]; /*~(1 << row);*/
  }
  bool is_allowed(int row) { return allowed & rowmasks[row]; /*(1 << row);*/ }
};

class board {
  std::array<column, GRID_SIZE> cols;
  size_t next_col = 0;

public:
  void place_queen(int row) {
    for (int c = next_col + 1; c < GRID_SIZE; ++c) {
      cols[c].remove_allowed(row + (c - next_col));
      cols[c].remove_allowed(row - (c - next_col));
      cols[c].remove_allowed(row);
    }
    cols[next_col].queen_row = row;
    next_col++;
  }

  void solve() {
    if (next_col == GRID_SIZE) {
      solc++;
    } else {
      for (int row = 0; row < GRID_SIZE; ++row) {
        if (cols[next_col].is_allowed(row)) {
          auto copy = *this;
          copy.place_queen(row);
          copy.solve();
        }
      }
    }
  }
};

int main() {
  make_masks();

  int k = 1;
  std::atomic_thread_fence(std::memory_order_seq_cst);
  auto start = std::chrono::high_resolution_clock::now();

  for (int i = 0; i < k; ++i) {
    board b;
    b.solve();
  }
  auto diff = std::chrono::high_resolution_clock::now() - start;
  std::atomic_thread_fence(std::memory_order_seq_cst);

  std::cout << (std::chrono::duration<double, std::milli>(diff).count() / k)
            << " us\n";
  std::cout << solc << std::endl;
}