This is a very nice N-Queens demo written
by Matt Taylor (student in 472 AI class).
It's an excellent demo to show the difference between
backtracking and local search. (It also has a randomized
backtrack option, which behaves a bit like local search.)
Known issue: (1) Board needs to be larger.
update: set display to 800x600 then fills full screen
(2) 32K upperbound on backtracks / flips.
(too low for current machines)
update: the noCutoff actually works but it's "fickle".
after resizing the board, slide the cutoff
again to "none". In the code, this re-asserts
noCutoff = True
so, now and then, the program resets the cutoff to 32K.
There are many options, e.g.:
You can resize the board.
You can slow down and speed up the simulation.
You can preplace queens.
Remember to hit "end setup".
You can recall the prepacement using the "restore button".
In a demo, I normally start with backtracking:
do 8 x 8 slow
10 x 10
20 x 20 full speed
30 x 30 .... talk about how many years this might take
then: local search
30 x 30
50 x 50
100 x 100 (or something big; it's fun to see the board)
I also so local search on 6x6 and 4x4. You can see
it hit a cycle now and then! (Large N Queens boards
are in a sense easier than small ones.)
Minor complexity question that, as far as I know, remains unresolved:
When given an N by N board and a pre-placement of k (< N) non-attacking queens,
can the remaining N-k be placed in a non-attacking manner?
This problem may NP-complete but I haven't seen a proof or a poly-time
algorithm. Let me know if you figure this one out!