Recursion Lab: N Queens Problem
In this lab you will implement the N Queens Problem, using the
class from the AP® Marine Biology Simulation case study.†
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 and look in the
folder, you will see several files that contain classes you will be
viewing and modifying, and two
jar files (
genericEnv.jar) that contain additional classes the
program needs in order to run. You will also find a
folder that contains documentation for the classes you will use in
this lab. The core classes in the application are:
All classes are covered by the GNU General
NQueensLab (contains the
NQueens (the class that implements the solution
to the N Queens Problem)
Queen (represents a queen on the board)
Location from the AP®
Marine Biology Simulation case study.‡ (These
classes are provided in the
jar files and are documented
- 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.