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:
- 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.
- 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):
- integers n, displayBoard, numSolsFound
- a two dimensional boolean array board
- a boolean variable findAll.
- a string solutions
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:
- A method to display the current configuration of board.
- A method legal as in Homework 3, eventually modified for efficiency
as mentioned below.
- 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.
- A method that returns the integer numSolsFound.
- 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.