Queens


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 .
 

Questions

  1. Does these algorithms work? Check it for 4 queens.
  2. How many solutions are there for n queens, where 1 <= n <= 8?
  3. For finding all the solutions to 8 queens, which method seems faster?
  4. For finding 1 solution with 20 queens, which method is faster?  See what happens with 22 queens.
  5. How fast does it find a solution for 50 queens, trying to put 40 random queens on the board?  In the FastQueens case, if there is no solution, about how many more positions does it have to look at?
  6. For 100 queens, what is a good choice for the number of random queens, so that you have a good shot at finding a quick answer.  Which algorithm is faster?
  7. What does all of this say about "intelligent searching"?

 
Carl E. Bredlau
bredlauc@mail.montclair.edu