Suppose that you have n queens from a chess game, and that you also have an n-by-n chess board. Is it possible to place all n queen on the board so that no two queens are in the same row, no two queens are in the same column, and no two queens are on the same diagonal? For example, a solution with n = 5 is shown here:

This problem is called the n-queens problem. For this project, you are to write a method that has one integer parameter, n, and determines whether there is a solution to the n-queens problem. If a solution is found, then the procedure prints the row and column of each queen (or displays the result graphically in an applet). Your program should solve the problem by making a sequence of choices such as “Try placing the row 1 queen in column 1” or “Try placing the row 7 queen in column 3.” Each time a choice is made, the choice is pushed onto a stack that already contains all the previously made choices. The purpose of the stack is to make it easy to fix incorrect choices, as shown in this pseudocode:

Push information onto the stack indicating the first choice is a queen in row 1, column 1.

This technique is called backtracking since we keep our choices on a stack and back up to correct any mistakes that are made. Notice that when youcheck for a conflict, you will need access to the entire stack (not just the top), so you should use the itemAt method from Programming Project 2 on page 356.

Programming Project 2 

Choose one of the stack implementations and implement a method with this specification:

Object itemAt(int n)
// Precondition: 0 <= n and n < size( ).
// Postcondition: The return value is the
// item that is n from the top (with the top at
// n = 0, the next at n = 1, and so on). The
// stack is not changed.

Throw a NoSuchElementException if the precondition is violated (from java.util.NoSuchElementException).

Transcribed Image Text:

Solution to the 5-queens problem