leonardo - N-Queens problem
View:Recent Entries.
View:Archive.
View:Friends.
View:Profile.
View:Website (My Website).

Tags:, , ,
Security:
Subject:N-Queens problem
Time:06:38 pm
This page shows various algorithms to solve the N-Queens problem:
http://c2.com/cgi/wiki?EightQueensInManyProgrammingLanguages

This is the shorter solver written in C that I have composed (from the original C code of that page), it's 195 bytes long:
typedef unsigned u;u s(u L,u C,u R,u N){u b;if(~C)for(u
S=L|C|R;~0U!=S;b=~S&(S+1),S|=b,N=s((L|b)<<1,C|b,(R|b)>>
1,N));else N++;return N;}main(int n,char**v){printf("%u"
,s(0,~0U>>atoi(v[1]),0,0));}
It accepts the board size in input, and outputs the number of queens.
Using GCC you can compile it with this (ignoring the warnings):
  gcc -O3 -s -std=c99 -fprofile-generate nq.c -o nq
Followed by a run with n for example 16, followed by:
  gcc -O3 -s -std=c99 -fprofile-use nq.c -o nq

Beside being very short it's pretty fast too. You have to work a lot to write a faster solver. For example, with N=16 finds the correct result 14_772_512 in 17.85 seconds on a 2 GHz Dual Core CPU, using 1 core, 32 bit compiled.

The program as is works up to N=18, finding the 666_090_624 solutions. The result for N=19 requires more than 32 bits to be represented, so you have to replace the 0U with 0UL, atoi() with atol(), the u with typedef unsigned long logn (and maybe a litte more, it may need around 2 hours of time to compute the result with N=19 because each times N grows by one, it requires about 8.1 times more time to run, so I haven't tested it much for sych inputs), this makes the code a little longer.

The same algorithm for the Python Psyco runs about 100 times slower (but it's fast still for being a Python program), but you need to add a & 0xFFFFFFFF to reduce the precision of the numbers (note that on 32-bit Python version 2.x the value 0xFFFFFFFF is a long):
import psyco, sys
def search(lb, cb, rb, cnt):
    if cb == 0xFFFFFFFF:
            cnt += 1
    else:
        bs = lb | cb | rb
        while bs != 0xFFFFFFFF:
            b = ~bs & (bs + 1)
            bs |= b
            cnt = search(((lb | b) << 1) & 0xFFFFFFFF,
                         cb | b, (rb | b) >> 1, cnt)
    return cnt
psyco.full()
print search(0, 0xFFFFFFFF >> int(sys.argv[1]), 0, 0)
The faster C program I have found (http://jsomers.com/nqueen_demo/nqueens.html ) needs about 8 seconds with N=16, so it's just a little more then two times faster (but it's more complex and much longer, around 400 lines with comments).
comments: Leave a comment Previous Entry Share Next Entry

leonardo - N-Queens problem
View:Recent Entries.
View:Archive.
View:Friends.
View:Profile.
View:Website (My Website).