N-QUEENS PROJECT
By Alyce Brady • Edited by Sandino Vargas-Pérez

PROBLEM DESCRIPTION

In this lab you will implement the N Queens Problem, placing N queens on an N x N board (like a chess board) in such a way that no queen can attack another queen. The N x N board will be represented by a BoundedGrid.

Implementation

1. Download the starting code files for the N Queens Lab:
   • NQueensApp.java (contains the main method)
   • Queen.java (represents a queen on the board)
   • NQueens.java (the partially-written class where you will implement the solution to the N Queens Problem)
   • Two image files, GoldCrown.gif and SilverCrown.gif (images of crowns).
   • The grid.jar Java archive (jar) file, which contains a library of classes that can be used to model a two-dimensional grid, including:
     • BoundedGrid (class that represents the two-dimensional grid)‡
     • Location (class that represents the row and column positions of a location in the grid)‡
     • ColorBlock (class whose objects represent blocks of color put in a grid)
     • ValidatedInputReader (class with static methods that can prompt users for numeric or string input)

     Throughout this lab you may want to have access to the class documentation for the Grid, GridObject, and Location classes. This documentation can be found at www.cs.kzoo.edu/GridPkg/GridPkgClassDocumentation/.

2. Compile and run the program. You should be prompted for the value of N, where N is the number of queens to try to place in an N x N "chess board". (The default value for N is 8, since a typical chess board is an 8 x 8 grid.) An empty N x N grid should appear.

   Before compiling your program, you will have to make sure your project knows about the grid.jar library. If you are using BlueJ, you can create a +libs folder under the folder containing your source files and put the jar file there, or you can specify its location in the Libraries tab of the Preferences or Properties dialog box (under BlueJ->Preferences, Tools->Preferences, or File->Properties, depending on the version of BlueJ you are using). Then within BlueJ, open your folder as a Non-BlueJ Project and compile it.

3. In the NQueens class, 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.

   If you want to use an image to represent a queen rather than a color block, put the image in the same folder as your Java source files and name it queen.gif, queen.jpg, or queen.png, as appropriate.

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. Don't remove queens that have been successfully placed.
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. You may want to test this on small boards, such as a 4 x 4 or 5 x 5 board, before going on to begger boards, especially if you add debugging messages while you are working on it..

Testing

You should test your program several times, including with several different values for N. What would be some good test cases to include? Document the test cases you ran in the documentation comments in the test driver or in a README.TXT file.

Clean and Refactor

Follow this link to clean and refactor your comments and code.

Submission

Submit your completed program through Kit, under N-Queens Project.

Have fun! And if you have any questions remember I am available during office hours and the Collaboration Center folks are here for you as well!