Java examples

So far, I have only one Java example on-line for this course: the eight-queens puzzle in Chapter 5 of the Budd book. I didn't quite understand (or believe in) Budd's solution, so I tried writing it myself from scratch. After much gnashing of teeth, I got it to run, but it was incredibly slow: it took c. 75 seconds (on a DEC 3000 Alphastation) to find the first solution. Then I realized that even if the leftmost two queens were attacking one another, I was wasting my time moving the rightmost in hopes that they would eventually kiss and make up. I added an optimization: when the current queen runs out of rows to try, she doesn't just ask her neighbor to advance; rather, she asks her neighbor to keep advancing until said neighbor and all the queens to her left constitute a partial solution, because there's no point in moving the current queen until they do. This improved speed by at least a factor of 100. Finally I realized that I had re-discovered the algorithm in Budd's book.

I've implemented both the slow version and the fast version. They differ in one line of code; indeed, I've written things in such a way that you can switch from one to the other by redefining the compile-time constant SLOW to either "true" or "false".