Purpose: This lab will give you experience harnessing an existing backtracking algorithm for the eight queens problem, and seeing its results displayed on your console window (that is, the location of standard output).

Lab

A mostly complete version of the eight queens problem has been provided for you to download. This version has the class Queens nearly completed (the class comes from your textbook starting on page 318).

You are to provide missing logic for the class Queens that will enable it to create a two-dimensional array that will represent a chess board with eight rows and eight columns. You are also to modify logic to display the chess board such that the display uses a nested loop to print the rows and columns of the chessboard. To do this, you must write logic for:

+clearBoard()

and modify logic for:

+displayBoard()

After this is done, you are to write a new program driver class that has a main() method responsible for making an object from the Queens class. The main() method must also use that Queens object to start the first queen of the chess board in the first column of the chess board. Once the first queen has been placed on the chess board, you must use its displayBoard() method to show you the solution to the eight queens problem

(Actually, the eight queens problem has many solutions, but the solution you will be displaying is based on the queen being placed in a specific position the first column of the chess board based on logic already programmed into the Queens class).

You are to submit for this lab:

(1) The modified Queens class with clearBoard() and displayBoard() properly working

(2) The new program driver class that has the main() method fully implemented as described previously.

The Queens class is available in this file for you to download: Queens.java

Once you are done getting the lab to work, just as an exercise of understanding backtracking, pay particular attention to the logic in the placeQueens() method. There are comments indicating how backtracking is used. See how the recursive call is used in the case that a queen is determined to be placed, and how backtracking occurs in the case that a queen has been found to have to be taken back from a position where it was placed. See that backtracking is a way of using decisions to determine if a current state of logic should be allowed, or if the logic should be undone since the logic does not lead to a solution. Understanding this is the essence of understanding how backtracking algorithms are implemented.

*queens.java

public class Queens {

// squares per row or per column

public static final int BOARD_SIZE = 8;

//used to indicate empty square

public static final int EMPTY = 0;

//used to indicate square contains a queen

public static final int QUEEN = 1;

private int board[][]; // chess board

public Queens() {

// --------------------------------------------------

// Constructor: Create an empty square board.

// --------------------------------------------------

board = new int[BOARD_SIZE][BOARD_SIZE];

} // end constructor

public void clearBoard(){

// --------------------------------------------------

// Clears the board.

// Precondition: None.

// Postcondition: Sets all squares to EMPTY

// --------------------------------------------------

// place your logic to implement this method here

} // end clearBoard

public void displayBoard(){

// --------------------------------------------------

// Displays the board.

// Precondition: None.

// Postcondition: Board is written to standartd

// output; zero is an EMPTY square, one is a square

// containing a queen (QUEEN)

// --------------------------------------------------

for (int i=0; i

for (int j=0; j

// place your logic to implement this method here

// that prints a single row of the chess board

// to the console window (i.e., standard output)

}

System.out.print(" ");

// this newline prints after a row

// of the chess board has been printed

}

} // end displayBoard

public boolean placeQueens(int column) {

// --------------------------------------------------

// Place queens in columns of the board beginning

// at the column specified.

// Precondition: Queens are placed correctly in

// columns 1 thro coulumn-1.

// Postcondition: If a solution is found, each

// column of the board contains one queen and method

// returns true; otherwise retruns false (no

// solution existis for a queen anywhere in column

// specified).

// --------------------------------------------------

if (column > BOARD_SIZE) {

return true; // base case

}

else {

boolean queenPlaced = false;

int row = 1; // number of square in column

while ( !queenPlaced && (row

// if square can be attacked

if (isUnderAttack(row, column)) {

++row; // consider next square in column

} // end if

else { // place queen and consider next column

setQueen(row, column);

queenPlaced = placeQueens(column+1);

// if no queen is possible in the next column,

if (!queenPlaced) {

// backtrack: remove queen placed earliers

// and try next square in column

removeQueen(row, column);

++row;

} // end if

} // end if

} // end while

return queenPlaced;

} // end if

} // end placeQueens

private void setQueen(int row, int column) {

// --------------------------------------------------

// Set a queen at square indicated by row and

// column.

// Precondition: None.

// Postcondition: Sets the square on the board in a

// given row and column to QUEEN.

// --------------------------------------------------

board[row-1][column-1] = QUEEN;

} // end setQueen

private void removeQueen(int row, int column) {

// --------------------------------------------------

// Remove a queen at square indicated by row and

// column.

// Precondition: None.

// Postcondition: Sets the square on the board in a

// given row and column to EMPTY.

// --------------------------------------------------

board[row-1][column-1] = EMPTY;

} // end setQueen

private boolean isUnderAttack(int row, int column) {

// --------------------------------------------------

// Determines whether the square on the board at a

// given row and column is under attack by any queens

// in the columns 1 through column-1.

// Precondition: Each column between 1 and column-1

// has a queen placed in a square at a specific row.

// None of these queens can be attacked by any other

// queen.

// Postcondition: If the deignated square is under

// attack, returns true; otherwise, returns false.

// --------------------------------------------------

// check column

for (int i=0; i

if (board[i][column-1]==1){

return true;

}

}

// check row

for (int i=0; i

if (board[row-1][i] == 1){

return true;

}

}

// check lower diagnal

int lower_dir_row = row-2;

int lower_dir_column = column-2;

while (lower_dir_row>=0 && lower_dir_column>=0){

if

(board[lower_dir_row][lower_dir_column]==1){

return true;

} else {

lower_dir_row = lower_dir_row -1;

lower_dir_column = lower_dir_column -1;

}

}

// check upper diagnal

int upper_dir_row = row;

int upper_dir_column = column-2;

while (upper_dir_row=0){

if(board[upper_dir_row][upper_dir_column] ==1){

return true;

}else{

upper_dir_row = upper_dir_row +1;

upper_dir_column = upper_dir_column -1;

}

}

return false;

} // end isUnderAttack

} // end Queens