15 queens

[tryit1]

Any hints how to solve 15 queens in less than 2 secs ?
Not precalculating answer. I could do this only in 3 secs.basic brute force with bitmasks.

something like

Code: Select all

 while (poss != 0) {
        poss^=place = poss & -poss;
        dotry(row|place, (left|place)<<1, (right|place)>>1);
}


.

I do also cut down the time using only first half of the board for the first row. Can you tell me any pruning strategies or counting techniques so that i can reduce the time to less than 2 s. Can you tell me how to cut down symmetric solutions ?
i heard that you can count fundamental solutions and then build up the final solutions . Any algorithms on counting only fundamental solutions.

Code: Select all

time echo 15 | ./a.exe
There are 2279184 solutions.

real    0m2.974s
user    0m2.954s
sys     0m0.010s


[Tomato]

I think you can try implementing dancing links technique proposed by Knuth. Look at his paper:
http://www.google.com/url?q=http://www- ... RaBKlw6o4w

Hope that helps.