Skip to content

Instantly share code, notes, and snippets.

@jdeng
Created December 11, 2013 16:48
Show Gist options
  • Save jdeng/7914070 to your computer and use it in GitHub Desktop.
Save jdeng/7914070 to your computer and use it in GitHub Desktop.
N Queens Problem (N <= 16)
//compile with -Ofast -march=native -funroll-loops
#include <stdio.h>
typedef unsigned short uint16_t;
template <int n, int m>
struct queens {
static void f(uint16_t col, uint16_t left, uint16_t right, size_t& count) {
uint16_t mask = ~(col | left | right);
for (int i = 0; i < n; ++i, mask >>= 1) {
if (! mask) return;
if (mask & 1) {
queens<n, m-1>::f(col | (1 << i), (left >> 1) | (1 << (i-1)), (right << 1) | (1 << (i + 1)), count);
}
}
}
};
template <int n>
struct queens<n, 0> {
static void f(uint16_t, uint16_t, uint16_t, size_t& count) { ++count; }
};
int main(int, const char *[])
{
size_t count = 0;
queens<16, 16>::f(0, 0, 0, count);
printf("%lu\n", count);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment