Due: 9 a.m., Thursday 9 November 2000.

30 points

"N-Queens"

Solve the N-queens problem. The goal is to place N queens on an NxN chessboard so that no two queens can attack each other. Queens can attack from any distance horizontally, vertically, or diagonally.

The file hw7.java contains a main method, a ChessBoard class, and the skeleton of a recursive method to solve the problem. Your solution must use recursion.

Use the following backtracking strategy. Try to fill in the queens one row at a time from top (row 0) to bottom (row N - 1). (Note that there must be exactly one queen in each row.) When trying to put a queen in row r, try all the columns in order starting from 0; if you find an empty square in column c that is not under attack, put a queen there, then recursively try to solve the problem starting at the next row. When you place a queen in the last row, you're done.

The problem is that you will get stuck; you'll get to a point where you can't find a safe square in the current row. Here is the first time this will happen if you follow this strategy for an 8x8 board:

Q . . . . . . . 
. . Q . . . . .
. . . . Q . . .
. Q . . . . . .
. . . Q . . . .
. . . . . . . .    <--- stuck! no safe place for queen in row 5
. . . . . . . .
. . . . . . . .

The call canSolveStartingFromRow(5) should return false, so control goes back to the call canSolveStartingFromRow(4), which must then remove the queen from row 4 column 4 and find the next available spot in row 4. Eventually you find that you can safely put a queen in row 4 column 7, so you put a queen there, and recursively try canSolveStartingFromRow(5) again...

Q . . . . . . .
. . Q . . . . .
. . . . Q . . .
. Q . . . . . .
. . . . . . . Q
. . . . . . . .
. . . . . . . .
. . . . . . . .

Do not modify the main method or ChessBoard class in any way!

Submit hw7.java to your eccentric upload folder.

[ Assignments | CSC 132 | Peter Sanderson | Computer Science | SMSU ]

Peter Sanderson ( PeteSanderson@smsu.edu )