Recursion Lab: N Queens Problem

Alyce Brady
Kalamazoo College

In this lab you will implement the N Queens Problem, using the BoundedEnv 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.

Exercise Set

  1. Download the zip file that contains the starting code files for the N Queens Lab (NQueens.zip) and unzip it. When you unzip the file and look in the Code folder, you will see several files that contain classes you will be viewing and modifying, and two jar files (mbsbb.jar and genericEnv.jar) that contain additional classes the program needs in order to run. You will also find a Documentation folder that contains documentation for the classes you will use in this lab.  The core classes in the application are:
    • NQueensLab (contains the main method)
    • NQueens (the class that implements the solution to the N Queens Problem)
    • Queen (represents a queen on the board)
    • BoundedEnv and Location from the AP® Marine Biology Simulation case study.‡ (These classes are provided in the jar files and are documented in the Documentation folder.)
    All classes are covered by the GNU General Public License.

  2. Compile and run the program. You should see an 8 x 8 "chess board" with no queens.

  3. Complete the numQueens and removeQueen methods, without adding any additional instance variables.  To test the removeQueen method, modify the placeQueen 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 solve method to place one queen.  Run the program.  You should see one queen (or color block) appear and then disappear from the environment.

  4. 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.

  5. 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 locationIsOK method always returns true, the queens should fill in the first column.

  6. Modify the locationIsOK method to return false 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).

  7. 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.