I once wrote a very short program to solve the
n queens puzzle
. This is it:
Version 3 (2008) Reduced size with 1 character
Version 2 (1996) Fixed the undefined behavior of d=(e-=d)&-e.
Version 1 (1994-10-14?) Original version posted to Usenet
The program has inspired some people to proof it's correctness
using formal methods:
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
David A. Wheeler
requested me to make the copyright status
of the program more explicit.
I agreed to do so in this reply.
The program appears in Frans Faase's interesting collection of C signature programs.
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.
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.
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 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)
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