V22.0101 ..... Homework 5 ..... Fall 2006
n Queens

Assigned: Mon Oct 23
Due: Thu Nov 2 at midnight.

The n queens problem is to place n queens on an n by n chessboard, in such a way that no queen threatens another, i.e., no two queens are in the same row, the same column, or on the same diagonal. There is a trivial solution for n=1 and it is easy to see there is no solution for n=2. The purpose of this assignment is to write a program that, given n, finds one or more solutions to the n queens problem, or establishes that there is no solution. This can be done using recursion.

The way in which the recursion works is a little complicated. We cannot solve the n queens problem by first solving the n-1 queens problem and making adjustments, because there may be no solution to the n-1 queens problem even if there is a solution to the n queens problem. Instead, do the following. For a chessboard of a fixed size n, write a recursive method place that attempts to place k queens on the last k rows of the chessboard, in such a way that they do not conflict with the n-k queens that are assumed to have already been placed correctly on the first n-k rows. Remember the two key ideas of recursion:

  1. The base case is k=0. In this case, we assume we have already placed n queens correctly and we want to add k=0 more, so there is nothing more to do: a solution has been found.
  2. Otherwise, we assume that, for all k between 1 and n, our method works for placing k-1 queens on the last k-1 rows, if the first n-(k-1) queens were already placed correctly. Now we want to program it to work so that it will correctly place k queens on the last k rows if n-k queens have already been placed correctly on the first n-k rows. How do we figure out whether we can add k queens on the last k rows? It's not hard: we need to try putting a queen in each position of the (n-k+1)-th row, and, for those cases where this does not lead to a conflict, making a recursive call to place the final k-1 queens.

Here are some more details of how to organize the program. Write a queens class that has the following private data fields (instance variables):

The class should have a constructor that accepts values for n, displayBoard and findAll, assigns these values to the data fields, and constructs the n by n array board. Its elements are initialized to false by default. The data field numSolsFound can be initialized to 0 by default. The data field solutions should be initialized to the empty string (not the default value, which is null). There should also be a no-arg constructor that calls the other one with default values 8, 0 and true.

The class should have the following methods:

  1. A method to display the current configuration of board.
  2. A method legal as in Homework 3, eventually modified for efficiency as mentioned below.
  3. The recursive method place described above. It should have only one parameter, k, and should return a boolean value indicating whether or not it successfully placed k queens on the last k rows. If findAll is true, place should search for all solutions to the problem, and set numSolsFound to the number of solutions found; otherwise, place should quit as soon as one solution is found, setting numSolsFound to one. If there is no solution, numSolsFound should be set to zero. When displayBoard is 2, the board should be displayed every time a queen is legally placed; this is helpful for debugging but generates a lot of output if n is not very small. When displayBoard is 1, the board should be displayed only when a solution is found. When displayBoard is 0, the board should not be displayed at all. But regardless of displayBoard, the solutions that are found should be recorded in the string solutions in an ordered pair format, such as this: "(0,0) (1,2) (2,1) (3,3)", indicating a (wrong) solution for n = 4. If findAll is true, the solutions string should show all solutions, separated by the newline character "\n", so that they can be displayed one per line; if findAll is false, the solutions string should show only one solution.
  4. A method that returns the integer numSolsFound.
  5. A method that returns the string solutions.
The main method should prompt the user for the various input values. It should then construct one queens object, call place once, and print the number of solutions that were found, displaying the boards that were found if the user wishes to see them, and displaying the final string solutions if the user so requests. The user should also be allowed to specify no output except the number of solutions. If the user chooses n to be zero or negative, the program should reject it and demand a positive value for n.

Notice that the recursive method does not construct objects of class queens. All it does is make changes to the one queens object that is constructed by the main method. This is very important for efficiency.

While you are debugging the program, set displayBoard to 1 or 2. Be sure your program is working correctly before you go on to the next part.

An important part of this assignment is to make the program reasonably efficient. There are several ways to do this.

  • Set displayBoard to 0.
  • Modify the legal method so that it only looks at the rows where queens have already been placed, above the row where the new queen is being placed.
  • Set the data field solutions to a java.util.StringBuffer object instead of a String object. String objects are very inefficient when n is not very small because there are a lot of solutions and every time you concatenate a new solution to the existing string, all the existing information must be copied to a newly constructed object - this is because String objects are immutable. If you use StringBuffer you can use its method append: instead of a+b you write a.append(b). The final StringBuffer object can be converted to a String by the toString() method.
  • When findAll is true, so all solutions are found, offer the user the opportunity to only print only one solution (up to the first newline character in solutions); printing the whole string might take longer than finding all the solutions! You can check this, does it?

    With these efficiencies, for how big a value of n can your program find all solutions with a running time of 1 minute or less? What if you only want one solution? Answer these questions by email when you submit your program. Of course, the answer will depend on your computer.