Recursion Lab: N Queens Problem
In this lab you will implement the N Queens Problem, using the
In this lab you will implement an algorithm that places N queens on an N x N
board (like a chess board) in such a way that no queen can attack another queen.
- Download the zip file that contains the starting code files for
the N Queens Lab (
and unzip it. When you unzip the file you will see the
following files and folders.
- The file
NQueensLab.shtml contains this
- Two image files,
SilverCrown.gif (images of crowns).
grid.jar Java archive
contains a library of classes that can be used to
model a two-dimensional grid as described above.
The documentation for these files can be found by
BoundedGrid (class that represents
the two-dimensional grid)‡
Location (class that represents the
row and column positions of a location in the
ColorBlock (class whose objects
represent blocks of color put in a grid)
JavaSourceFiles folder contains the
source files for the NQueens Lab.
NQueensLab (contains the
NQueens (the class that will implement the solution
to the N Queens Problem)
Queen (represents a queen on the board)
Note: All of the
classes in the
JavaSourceFiles folder and the
grid.jar Java archive file are covered by the GNU General Public License.
- Compile and run the program. You should see an 8 x 8 "chess
board" with no queens.
- Complete the
methods, without adding any additional instance variables. To
removeQueen method, modify the
method to add a queen to any arbitrary column (your choice) of the
correct row for that queen, display the environment, and then remove
the queen and redisplay the environment. Modify the
method to place one queen. Run the program. You should
see one queen (or color block) appear and then disappear from the
- Modify the
placeQueen method to recursively place all
the queens in arbitrary columns (or the same arbitrary column).
Think about where you should place the recursive call if you want
to see the queens appear in each row, one-by-one, and then disappear
in reverse order. Make sure you remember to include a base case.
Do you need to modify the
solve method to place all the
queens? If so, do it.
- Fully implement the
placeQueen method so that it checks
column by column to find an OK location to place this queen, until
the queen has been successfully placed in a column and all the queens
after her have been successfully placed also. Since the
method always returns
true, the queens should fill in
the first column.
- Modify the
locationIsOK method to return
if any queens have already be placed in the same column as the location
parameter. When you have this working you should see the queens
fill in the diagonal from location (0, 0) to location (n-1, n-1).
- Modify the
locationIsOK method again to also return
false if any queens have already been placed on the board
in locations that are on the diagonal from the location parameter.