Let us compare some 8queens algorithms with different languages (because we can)..
On Rosetta code I found this as the fastest in C:
Code:
#include <stdio.h>
#define MAXN 31
int nqueens(int n)
{
int q0,q1;
int cols[MAXN], diagl[MAXN], diagr[MAXN], posibs[MAXN]; // Our backtracking 'stack'
int num=0;
//
// The top level is two fors, to save one bit of symmetry in the enumeration by forcing second queen to
// be AFTER the first queen.
//
for (q0=0; q0<n-2; q0++) {
for (q1=q0+2; q1<n; q1++){
int bit0 = 1<<q0;
int bit1 = 1<<q1;
int d=0; // d is our depth in the backtrack stack
cols[0] = bit0 | bit1 | (-1<<n); // The -1 here is used to fill all 'coloumn' bits after n ...
diagl[0]= (bit0<<1 | bit1)<<1;
diagr[0]= (bit0>>1 | bit1)>>1;
// The variable posib contains the bitmask of possibilities we still have to try in a given row ...
int posib = ~(cols[0] | diagl[0] | diagr[0]);
while (d >= 0) {
while(posib) {
int bit = posib & -posib; // The standard trick for getting the rightmost bit in the mask
int ncols= cols[d] | bit;
int ndiagl = (diagl[d] | bit) << 1;
int ndiagr = (diagr[d] | bit) >> 1;
int nposib = ~(ncols | ndiagl | ndiagr);
posib^=bit; // Eliminate the tried possibility.
// The following is the main additional trick here, as recognizing solution can not be done using stack level (d),
// since we save the depth+backtrack time at the end of the enumeration loop. However by noticing all coloumns are
// filled (comparison to -1) we know a solution was reached ...
// Notice also that avoiding an if on the ncols==-1 comparison is more efficient!
num += ncols==-1;
if (nposib) {
if (posib) { // This if saves stack depth + backtrack operations when we passed the last possibility in a row.
posibs[d++] = posib; // Go lower in stack ..
}
cols[d] = ncols;
diagl[d] = ndiagl;
diagr[d] = ndiagr;
posib = nposib;
}
}
posib = posibs[--d]; // backtrack ...
}
}
}
return num*2;
}
main(int ac , char **av)
{
if(ac != 2) {
printf("usage: nq n\n");
return 1;
}
int n = atoi(av[1]);
if(n<1 || n > MAXN) {
printf("n must be between 2 and 31!\n");
}
printf("Number of solution for %d is %d\n",n,nqueens(n));
}
Compiled straight in PellesC and it did
Code:
C:\Users\pito>C:\Users\pito\MyCode\C\8queens\8queens.exe 16
Number of solution for 16 is 14772512
in 8secs on my i5 notebook.
I've mentioned Mecrisp Forth - with rather conservative textbook (slow?) algorithm
Code:
0 variable solutions
0 variable nodes
: bits ( n -- mask ) 1 swap lshift 1- ;
: lowBit ( mask -- bit ) dup negate and ;
: lowBit- ( mask -- bits ) dup 1- and ;
: next3 ( dl dr f files -- dl dr f dl' dr' f' )
not >r
2 pick r@ and 2* 1+
2 pick r@ and 2/
2 pick r> and ;
: try ( dl dr f -- )
dup if
1 nodes +!
dup 2over and and
begin ?dup while
dup >r lowBit next3 recurse r> lowBit-
repeat
else 1 solutions +! then
drop 2drop ;
: queens ( n -- )
0 solutions ! 0 nodes !
-1 -1 rot bits try
solutions @ . ." solutions, " nodes @ . ." nodes" ;
: testQ ( N -- ) millis @ swap queens millis @ swap - ." t= " . ." ms" ;
\ STM32F407, 168MHz clock, serial 115k2:
\ ==============================================
\ 8 testQ 92 solutions, 1965 nodes t= 4 ms ok.
\ 10 testQ 724 solutions, 34815 nodes t= 43 ms ok.
\ 12 testQ 14200 solutions, 841989 nodes t= 1002 ms ok.
\ 13 testQ 73712 solutions, 4601178 nodes t= 5457 ms ok.
\ 14 testQ 365596 solutions, 26992957 nodes t= 31936 ms ok.
\ 16 testQ 14772512 solutions, 1126417791 nodes t= 1331997 ms ok.
from Rosetta Code.
I think we may try with SmallerC and RetroBSD, and with GCC and LiteBSD with above C code.
And with others..