PROJECT #3 N-QUEENS PROBLEM
By Alyce Brady • Edited by Sandino Vargas-Pérez
PROBLEM DESCRIPTION
In this lab you will implement the N Queens Problem, using the BoundedGrid
class.‡ 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
-
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 you will see the following files and folders.- The file
NQueensLab.shtml
contains an older version of this write-up. - Two image files,
GoldCrown.gif
andSilverCrown.gif
(images of crowns). - The
grid.jar
Java archive (jar
) file contains a library of classes that can be used to model a two-dimensional grid as described above.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)
Throughout this lab you may want to have access to the class documentation for the
Grid
,GridObject
, andLocation
classes. This documentation can be found at www.cs.kzoo.edu/GridPkg/GridPkgClassDocumentation/. -
The
JavaSourceFiles
folder contains the source files for the NQueens Lab.NQueensLab
(contains themain
method)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 thegrid.jar
Java archive file are covered by the GNU General Public License.
- The file
- Compile and run the program. You should see an 8 x 8 "chess board" with no queens.
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 theJavaSourcesFiles
folder and put thejar
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). The within BlueJ, open theJavaSourcesFiles
folder as a Non-BlueJ Project and compile it. -
Complete the
numQueens
andremoveQueen
methods, without adding any additional instance variables. To test theremoveQueen
method, modify theplaceQueen
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 thesolve
method to place one queen. Run the program. You should see one queen (or color block) appear and then disappear from the environment. -
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 thesolve
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 thelocationIsOK
method always returnstrue
, the queens should fill in the first column. -
Modify the
locationIsOK
method to returnfalse
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 returnfalse
if any queens have already been placed on the board in locations that are on the diagonal from the location parameter.
Location
class comes directly from the AP® Marine Biology Simulation case study; BoundedGrid
was inspired by the MBS BoundedEnv
class. AP is a registered trademark of the College Entrance Examination Board. The Marine Biology Simulation case study was copyrighted in 2002 by the College Entrance Examination Board. It is available on the web from the College Board web site (www.collegeboard.com and apcentral.collegeboard.com). Copyright Alyce Brady, 2002.
EVALUATION
Project #3 is worth 20 points. This project will be submitted in groups of 2 students. The following items describe the criteria we will use to evaluate your project:
- Implementation (17 points):
- Correct implementation of the
solve()
method 2 pts. - Correct implementation of the
numQueens()
method 2 pts. - Correct implementation of the
placeQueen()
method 6 pts. - Correct implementation of the
locationIsOK()
method 5 pts. - Correct implementation of the
removeQueen()
method 2 pts.
- Correct implementation of the
- Internal Documentation & Style (3 points):
- Appropriate internal documentation at top of all files 1 pts.
- Appropriate internal comments, variable names, indentation in all files 2 pts.
- Note: Make sure these classes are properly implemented, you have clean code, and the appropriate amount of comments.
Submit your completed program through Kit, under Project 3: N-Queens Problem.
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!
← back to the schedule