It's that old problem: put down queens on a chessboard so
that no queen threatens another.
For this Java implementation, 'N' is for the number of queens, 'random' is the number of random queens that will be placed first. If it has trouble, it will try placing 5 fewer queens on the board until it succeeds.
Backtracking is the traditional method. FastQueens will keep track of which squares are not covered. It will choose the next row based upon which positions have the best potential for solution. With some random queens, backtracking will find all solutions starting from that position. FastQueens will quit after finding all the possible solutions with the random queens.
Clicking the mouse in the applet will stop and start the animation after a solution is found.
Warning: The applet has a thread for finding
the solution. Some attempt has been made to end this thread if you
change the input. However, this applet will chew up CPU cycles and
memory, especially if you search for a solution with more than 100 queens
and don't put down at least 80% of random queens. It has the potential
of hanging your browser.
Board.java keeps track of the board
and has the algorithms for testing if a square is free. Queens.java
contains the algorithms for backtracking and fast queens. QueensApp.java
contains the applet.
For historical (or hysterical) interest, the Turbo
Pascal program .