[racket] Checking (on) queens | Concerns about HtDP exercise 28.2.4

Dear readers,

After several false starts (mainly underestimating just how much
computation is needed), I've managed to come to a solution for this
exercise. For reasons I probably shouldn't mention, for the sake of
other students, I believe I've found the solution the authors were
looking for, but there are three concerns I have.

The first concern is speed. I found a page on the Internet that
claimed to be able to compute /all/ solutions to the case N=8 in less
than 0 seconds[1]. The author of the page also claims his program
beats the "world record" for speed, but here is the result for my
program (and I'm using backtracking, so I bomb out as soon as I've
found a solution; i.e. I don't generate them all.)

(define test-board (build-board 8 (lambda (i j) false)))
(time (placement 8 test-board))
cpu time: 23345 real time: 23408 gc time: 148
(list
 (list true false false false false false false false)
 (list false false false false false false true false)
 (list false false false false true false false false)
 (list false false false false false false false true)
 (list false true false false false false false false)
 (list false false false true false false false false)
 (list false false false false false true false false)
 (list false false true false false false false false))

And attempting the following computation, well, I've yet to have
enough patience to wait long enough to see the result (which I know is
false anyway!)
(placement 9 test-board)
zzzzzzzzzzzzzzzzz.....

I figure my poor little design has to check all of 64C8 = 4426165368
configurations before it can finally draw breath and tell me the
answer is false. But such a number seems so small for a computer :P

I'm taking a stab in the dark here that most of the frequenters of
this list have implemented such a solution. How does mine compare to
yours? Is it so slow that perhaps I'm doing it all wrong?

My second concern is the behavior in the case when the input board
contains queens[2]. For (it seems anyway, see concern 3) N<=4, my
design outputs the expected boards. That is, it will try to place
however many queens you give it on a board that may itself contain
queens.

However, when (approx) N >= 7, the design outputs legitimate boards,
in terms of N queens being placed (along with any initially on the
board) and none of them in check from each other, but the positions of
the original queens appear to have been shuffled! This is magic to me,
because I see no way that my solution could be doing this :$. I
realise this all very difficult to talk about without your being able
to see my solution, but maybe others have noticed this with their
solutions? Maybe my solution isn't so wrong?

And finally, my third concern is testing. How am I to test with any
assurance that I have a sane design? I've thought about generating
lots of random boards, running placement over them, and then running a
checker procedure over that to make sure none of the queens are in
check. But thats hardly bullet proof either. How would the experienced
designers test a procedure such as this?

Thank you for your time,

Horace.

[1] This is the Internet site of the "world record breaking queens
procedure", I have no idea how to use the program, but I found the
discussion frightening : http://jsomers.com/nqueen_demo/nqueens.html
[2]  David Yreta has already brought this issue up with Matthias. The
book does suggest the following contract for placement,
;; placement : N board -> board or false
But Matthias tells us that the intended interpretation is that the
input board /does not/ contain any queens. He admits the book is
misleading. To me however, it seems that the only way to solve this
problem is to keep checking for threats, so who cares if the input
board contains queens?