Queens (DRAFT)

I once wrote a very short program to solve the n queens puzzle . This is it:

Version 3 (2008) Reduced size with 1 character

t(a,b,c){int d=0,e=a&~b&~c,f=1;if(a)for(f=0;d=e&-e;f+=t(a-d,(b+d)*2,(c+d)/
2))e-=d;return f;}main(q){scanf("%d",&q);printf("%d\n",t(~(~0<<q),0,0));}
Version 2 (1996) Fixed the undefined behavior of d=(e-=d)&-e.
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));}
Version 1 (1994-10-14?) Original version posted to Usenet
t(a,b,c){int d=0,e=a&~b&~c,f=1;if(a)for(f=0;d=(e-=d)&-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));}
The program has inspired some people to proof it's correctness using formal methods:

Origin

The 2-line version is mine. The idea of using integers to represent bit arrays in solving this problem is older. There was a similar program in the rec.puzzles FAQ archive. The FAQ attributes Tony Lezard as the author. I can trace it back to November 19, 1991 in Google Groups.

Public domain

David A. Wheeler requested me to make the copyright status of the program more explicit. I agreed to do so in this reply.

Signature programs

The program appears in Frans Faase's interesting collection of C signature programs.

Assembly versions

An 68k assembly version of the inner loop. Marijn kindly translated it into x86 assembly.

The Geminix runs

gem.stack.urc.tue.nl was a 'Geminix', a dual M68020-based Unix system running at, I believe, 12MHz with 2MB of memory. One of the CPU's was dedicated for I/O and not available for user programs. It was Stack's first Unix system, probably donated by the university. It handled usenet and e-mail connections until phased out by a more modern Sun. It was so ancient and slow, sometimes when there was a power dip, it was too slow to notice and simply kept running while the Sun and BSD boxes went down.

The assembly version was small enough to run entirely in the 020's instruction cache of 256 bytes.

Q(19)

This ran for almost a month. Each subresult was off by one, so the shown number was 19 too high. I realized that and fixed it for a rerun of Q(18). The assembly version computed Q(18) = 666090624 in 3 days and 5 hours. Much improvement over the earlier run of 7 weeks.

Q(20)

Later that year I made a run for Q(20). This occupied the Geminix for 6 months, or the best part of 1997. I had to manually restart the computation once during that time. Most of the intermediate results overflowed the 32-bit signed integers so the result had to be adjusted manually afterwards as well.

False

False is a nice little programming language designed by Wouter van Oortmerssen. False is remarkable in that it combines a smaller than 1 kilobyte compiler with a languege that is still more or less usuable. It thought me a lot about programming. I wrote a version of the queens program in False, which became part of the distribution. (possibly every False program ever made is included in the distribution) queens.f The False version dates from June 1994. The C version must be older than that, so the October 1994 posting can't be the first one. But maybe the C version wasn't at 2 lines at that time of creating the False program yet.

Unrolled C version

Parallel queens

Lucas' version

Results