CSC 205 Program Assignment 4

40 points

Problem & Requirements

Develop and validate a program to place eight queens on a chessboard in such a way that no queen is under attack from any other queen.

A chessboard has eight rows and eight columns. In the game of chess, the queen is the most powerful piece: she can attack any piece in her row, in her column, or in either of her diagonals.

Your application should allow users to specify the location (row, column) of the first queen through the command-line arguments. The default location (0, 0) will be used if no row and column values specified.

The minimal requirement is to place the first queen in column 0, and display your result using console output as illustrated below, showing that only one queen in any given row, column, and diagonal. You may get up to 10 points as bonus by implementing a graphical interface that can simulate the backtracking process and/or allowing for placing the first queen in any valid column. You also need to keep track of locations validated (using the valid method) and tried (using the undo method).

Analysis & Design – Implementing the Application Interface

You can modify the GUI component for Project 3 (or the maze application that is available with Lab 7) for the need in this project. The logic here is much simpler than that for the maze: you don’t have to mark the tried(or undone) positions in the eightqueens’ application. You simply draw a queen on each of the positions which are considered as on the path to your goal. In addition, the position of the first queen is of more interest in this application, as is the case of the finish position in the maze application.

Your EightQueens class should implement the Application interface. Here are some hints to the detailed design of the methods your class needs to implement.

The valid method. In addition to the constraint of being on the board, the new locationneeds to be not under attack from any one of the queens already on board. A helper method (e.g., isUnderAttack(Locationlocation)) can be used here which returns true only when pos is not in a row, column, or diagonal on which another queen already exists.

The done method. To meet the minimum requirement, the problem is solved when a queen is placed on column 7. One way to get some bonus points is to allow for placing the first queen in any column. Thus, the problem is solved when a queen is in the column right prior to the column the first queen is in. For instance, if the first queen is placed on column 3, then the done method should return true if a queen is placed in column 2.

The toString method. As illustrated on page 1, this method should return a string with 17 lines, and the odd-numbered lines contain the following pattern.

+---+---+---+---+---+---+---+---+

Each of the eight even-numbered lines contains exactly one queen and seven emptysquares. The queen is represented by | Q |, i.e. bar, space, capital Q, space, bar; while anemptysquare is represented by| |, i.e. bar, space, space, space, bar.

The undo method. It is a good idea to keep track of the number of queens currently on board. When you have to retrace, remember to decrement this number.

The EightQueensIterator class. This class can be implemented as an inner class of your EightQueens class. The constructor should start from row 0 of the new column. The next method should advance to the next row in the same column. The hasNext method should return true until the row number is greater than 7. You don’t have to implement the remove method.