N-Queens number for large boards.
Truman Collins
Several weeks ago Jouni Tolonen posted a question about what the
largest nxn board was where the number of ways of placing n queens so
the don't attack each other had been calculated. I got out a program
I had written some time ago, did some optimization on it and managed
to calculate the number for boards up to 19x19. I thought I might as
well post them in case anyone was interested. Has anyone found the
number for a 20x20 board?
Total solutions for a 1x1 board: 1
Total solutions for a 2x2 board: 0
Total solutions for a 3x3 board: 0
Total solutions for a 4x4 board: 2
Total solutions for a 5x5 board: 10
Total solutions for a 6x6 board: 4
Total solutions for a 7x7 board: 40
Total solutions for a 8x8 board: 92
Total solutions for a 9x9 board: 352
Total solutions for a 10x10 board: 724
Total solutions for a 11x11 board: 2680
Total solutions for a 12x12 board: 14200
Total solutions for a 13x13 board: 73712
Total solutions for a 14x14 board: 365596
Total solutions for a 15x15 board: 2279184
Total solutions for a 16x16 board: 14772512
Total solutions for a 17x17 board: 95815104
Total solutions for a 18x18 board: 666090624
Total solutions for a 19x19 board: 4968057848
-Truman
--
tcol...@teleport.COM Public Access User --- Not affiliated with TECHbooks
Public Access UNIX and Internet at (503) 220-1016 (2400-14400, N81)
Marcel van Kervinck
Truman Collins (tcol...@teleport.com) wrote:
> Several weeks ago Jouni Tolonen posted a question about what the
> largest nxn board was where the number of ways of placing n queens so
> the don't attack each other had been calculated. I got out a program
> I had written some time ago, did some optimization on it and managed
> to calculate the number for boards up to 19x19. I thought I might as
> well post them in case anyone was interested. Has anyone found the
> number for a 20x20 board?
> Total solutions for a 1x1 board: 1
> Total solutions for a 2x2 board: 0
...
> Total solutions for a 18x18 board: 666090624
> Total solutions for a 19x19 board: 4968057848
I computed 18x18 last year on an idle geminix (68020 12 MHz)
It took ~7 weeks. I'll do a 20x20 attack real soon now, I guess.
It seems that you failed to compute 0x0. It has 1 solution :)
BTW: here's my program, enter the size on stdin:
t(a,b,c){int d=0,e=a&~b&~c,f=1;if(a)for(f=0;e-=d,d=e&-e;f+=t(a-d,(b+d)*2,(
c+d)/2));return f;}main(q){scanf("%d",&q);printf("%d\n",t(~(~0<<q),0,0));}
Marcel
-- _ _
_| |_|_|
|_ |_ Marcel van Kervinck
|_| mar...@stack.nl