N Queens Problem (N <= 16)

queens.cc

//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;
}