Eight queens puzzle is a well-known problem. It can be solved by common depth-first backtracking algorithm. However, we can use bit manipulation skills to make the algorithm more efficient. In the following code, row, md and cd reference to the restrictions about row, main diagonal and counter diagonal respectively if we enumerate from 0 column to $(N-1)$ column. Specificialy, row represents all the selected rows. And if we more from the current column to the next column from left to right, namely 0 to $N-1$, the rows md selected on the main diagonal changed to $md << 1$ when it shows in bit level. Similarly, the rows cd selected on the counter diagonal changed to $cd >> 1$. Below the code is the accurate runtime on my machine.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int N, MASK;

ll NQueen(int row, int md, int cd) {
ll count = 0;
if (row != MASK) { // row < MASK
int pos = MASK & (~(row | md | cd)); // all the candinate rows
while (pos) {
int last = pos & (-pos); // = pos & (~pos + 1) // get the last position which is 1
pos = pos - last;
count += NQueen(row | last, (md | last) << 1, (cd | last) >> 1); // select row: last
}
return count;
} else {
return 1;
}
}

int main() {
for (N = 4; N < 20; ++N) {
MASK = (1 << N) - 1;
double start = clock();
ll ans = NQueen(0, 0, 0);
double elapsed = (clock() - start) / CLOCKS_PER_SEC;
printf("%2d queens: %10lld,\t time elapsed: %.3f second(s)\n", N, ans, elapsed);
}
return 0;
}

4 queens: 2, time elapsed: 0.000 second(s)
5 queens: 10, time elapsed: 0.000 second(s)
6 queens: 4, time elapsed: 0.000 second(s)
7 queens: 40, time elapsed: 0.000 second(s)
8 queens: 92, time elapsed: 0.000 second(s)
9 queens: 352, time elapsed: 0.000 second(s)
10 queens: 724, time elapsed: 0.001 second(s)
11 queens: 2680, time elapsed: 0.002 second(s)
12 queens: 14200, time elapsed: 0.012 second(s)
13 queens: 73712, time elapsed: 0.062 second(s)
14 queens: 365596, time elapsed: 0.351 second(s)
15 queens: 2279184, time elapsed: 2.203 second(s)
16 queens: 14772512, time elapsed: 14.722 second(s)
17 queens: 95815104, time elapsed: 104.691 second(s)
18 queens: 666090624, time elapsed: 767.495 second(s)