N Queens with OpenMP

queens-omp.cc

//compile with -fopenmp -Ofast -march=native -funroll-loops
#include <stdio.h>
typedef unsigned int mask_t;

template <int n, int m>
struct queens {
	static size_t f(mask_t col, mask_t left, mask_t right) {
		mask_t mask = ~(col | left | right);
		size_t count = 0;
		while (mask) {
			int i = __builtin_ctz(mask);
			if (i >= n) break;
			mask_t j = 1 << i;
			count += queens<n, m-1>::f(col|j, (left|j) >> 1, (right|j) << 1);
			mask &= mask-1;
		}
		return count;
	}
};

template <int n>
struct queens<n, 0> {
	static size_t f(mask_t, mask_t, mask_t) { return 1; }
};

#define N 18
#include <numeric>
int main(int, const char *[])
{
	size_t counts[N] = {0};

	#pragma omp parallel for
	for (int i=0; i<(N+1)/2; ++i) {
		mask_t j = 1 << i;
		counts[i] = queens<N, N-1>::f(j, j >> 1, j << 1);
	}

	for (int i=(N+1)/2; i < N; ++i) counts[i] = counts[N - 1 - i];
	printf("%lu\n", std::accumulate(counts, counts + N, 0));
	return 0;
}