CMPU 102 - Assignment 4
NQueens Problem
Assigned: Mon, Feb. 25
Due (by 5 PM): Fri, Mar.  7

In this assignment you will:

  1. Have fun studying an example of a recursive backtracking algorithm
  2. Finish the implementation of a more general version of the Eight Queens Problem: NQueens
  3. Implement one of the methods outlined in the description of the 8-Queens problem in the text: isUnderAttack() 
  4. Gain more practice using recursion
  5. use the submit102 script from the Linux prompt to hand in your project.

Summary: We have provided the GUI and most of the recursive backtracking solution to the NQueens problem--a more general version of the Eight Queens problem presented in section 6.1 of the text (p. 294). You will complete the implementation of NQueens by providing the missing code for method isUnderAttack() in class NQueensGame. 

Download the starter project

  1. Click here to download the starter project: NQueens.zip. 
  2. Save it in your cs102 directory.
  3. Unzip the file.
  4. You should be able to Open this as an existing project in NetBeans (described next)

Launch NetBeans and Open Project

  1. From NetBeans, go to the File menu and select "Open Project" -- or click on the third button from the left on the button bar.
  2. Navigate to your cs102 folder and select the folder named "NQueens" 
  3. The "Open Project Folder" button should be enabled. Click it to open the starter project.
  4. The only file you need to modify is NQueensGame.java.

The NQueensGame Class

In this class we've provided the code for everything but the isUnderAttack() method. You shouldn't change any other code in the class; just provide the missing code for this method. You should study the placeQueens() method to understand how it works, and what it expects of isUnderAttack() when it invokes this method. 

We would have asked you to implement the placeQueens() method, but the book pretty much gives the solution away. To make it a little more interesting, we've enhanced the code to find random solutions, rather than the same solution each time. You should test your solution by running the program from the GUI many times, visually verifying the solutions on the chess board. 

To determine if a queen is under attack, your isUnderAttack() method should check all prior columns to verify there is no queen in the same row, or along one of the diagonals, of where the queen is being placed in the current column. One more stipulation: you must implement this method recursively--no loops. We recommend you consider using three recursive helper methods, one to check each possible threat direction. While there is some thought involved in how you accomplish this task, you should find this week's assignment to be very straight-forward. 

Good luck!

Submitting your solution

From a terminal window, type the following commands: 

cd
cd cs102 
submit102 NQueens