Question

Complete the program that solves the Eight Queens problem in java only please (pages 318 through

320). The program’s output should look similar to:

|1|0|0|0|0|0|0|0|

|0|0|0|0|0|0|1|0|

|0|0|0|0|1|0|0|0|

|0|0|0|0|0|0|0|1|

|0|1|0|0|0|0|0|0|

|0|0|0|1|0|0|0|0|

|0|0|0|0|0|1|0|0|

|0|0|1|0|0|0|0|0|

PlaceQueens(in currColumn:integer)

//places queens in columns numbered currColumn through 8

If (currColumn>8){

The problem is solved }

Else {

While(unconsidered squares exist in curr column and the problem is unsolved ){

Determine the next square in column currColumn that is not under attack by a queen in an earlier column

If (such a square exists){

Place a queen in the square

placeQueens(currColumns+1)//try next column

if (no queen is possible in column and consider the next square in that column

}//end if

}//end if

}//end while

}//end if

The method placeQueens is used in the following context

Clear all squares on the board

Using placeQueens placeQueens(1) //begin with first column

If (asolution exists){

Display solution

}else

Display message //no solution found

}//end if

Public class Queens {

// square per roll or column

Public static final int BOARD_SIZE=8;

//used to indicate an empty square

Public static final int EMPTY=0;

Public static final int QUEEN=1;

Private int board [][]; //chess board

Public Queens (){

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

//Constructor : Creates and empty board.

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

board = new int [BOARD_SIZE] [BOARD_SIZE];

}//end constructor

Public void clearBoard(){

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

//Clears the board.

//precondition: none

//postcondition: sets all squares to EMPTY.

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

//to be implemented in programming problem 1

}// end constructor

Public void displayBoard(){

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

//Displays the board

//precondition: none.

//postcondition: Board is written to standard

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

//containing a queen (QUEEN).

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

To implement programming problem 1

}//end displayBoard

Public boolean placeQueens(int column){

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

//places queens in columns of the board beginning

//at the column specified

//preconditions : Queen are placed correctly

//in columns 1 through column -1.

//postcondition; if a solution is found ,each

//column of the board contains one queen and method

//return true; otherwise ,return false (no

//solutionexists 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 <=BOARD_SIZE){

//if square can be attacked

If (isUnderatttack(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 next column,

If (!queenPlaced){

//backtrack: remove queen placedearlier

//and try next square in column

removeQueen (row, column );

++row;

}//end if

}//end if

}//end while

return queenPlaced;

}//end if

}// end PlaceQueens

Private Void setQueens(int row,int column){

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

Sets a queen at square indicated by rowand column

//precondition:none

//postcondition: sets the square on the board in a given row and column.

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

//to implement be implemented in programming problem 1

}//end removeQueens

private boolean isUnderAtttack (int row ,itn column){

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

//determine whether the square on the board at a

//given row or column is underAttackby any queens

//in the columns 1 through coulumn-1.

Precondition. Each column between 1 and coulumn -1

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

//none of these queens can be attacked by any other queen

Post condition; if the designated square is under attack

//return true; otherwise,return false.

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

To implement programming problem 1

}// end isUnderAttack

Private in index(int number ){

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

Returns the array index that correspond to

//a row or column number

//precondition ; 1<= number <=BOARD_SIZE.

//post condition ; returns adjusted index value.

Answer 1

//places queens in columns numbered currColumn through 8

If (currColumn>8){

The problem is solved }

Else {

While(unconsidered squares exist in curr column and the problem is unsolved ){

Determine the next square in column currColumn that is not under attack by a queen in an earlier column

If (such a square exists){

Place a queen in the square

placeQueens(currColumns+1)//try next column

if (no queen is possible in column and consider the next square in that column

}//end if

}//end if

}//end while

}//end if

The method placeQueens is used in the following context

Clear all squares on the board

Using placeQueens placeQueens(1) //begin with first column

If (asolution exists){

Display solution

}else

Display message //no solution found

}//end if

Public class Queens {

// square per roll or column

Public static final int BOARD_SIZE=8;

//used to indicate an empty square

Public static final int EMPTY=0;

Public static final int QUEEN=1;

Private int board [][]; //chess board

Public Queens (){

...........................................

//Constructor : Creates and empty board.

...........................................

board = new int [BOARD_SIZE] [BOARD_SIZE];

}//end constructor

Public void clearBoard(){

...........................................

//Clears the board.

//precondition: none

//postcondition: sets all squares to EMPTY.

...........................................

//to be implemented in programming problem 1

}// end constructor

Public void displayBoard(){

...........................................

//Displays the board

//precondition: none.

//postcondition: Board is written to standard

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

//containing a queen (QUEEN).

...........................................

To implement programming problem 1

}//end displayBoard

Public boolean placeQueens(int column){

...........................................

//places queens in columns of the board beginning

//at the column specified

//preconditions : Queen are placed correctly

//in columns 1 through column -1.

//postcondition; if a solution is found ,each

//column of the board contains one queen and method

//return true; otherwise ,return false (no

//solutionexists 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 <=BOARD_SIZE){

//if square can be attacked

If (isUnderatttack(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 next column,

If (!queenPlaced){

//backtrack: remove queen placedearlier

//and try next square in column

removeQueen (row, column );

++row;

}//end if

}//end if

}//end while

return queenPlaced;

}//end if

}// end PlaceQueens

Private Void setQueens(int row,int column){

...................................................................

Sets a queen at square indicated by rowand column

//precondition:none

//postcondition: sets the square on the board in a given row and column.

.........................................................

//to implement be implemented in programming problem 1

}//end removeQueens

private boolean isUnderAtttack (int row ,itn column){

..........................................................

//determine whether the square on the board at a

//given row or column is underAttackby any queens

//in the columns 1 through coulumn-1.

Precondition. Each column between 1 and coulumn -1

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

//none of these queens can be attacked by any other queen

Post condition; if the designated square is under attack

//return true; otherwise,return false.

.....................................................

To implement programming problem 1

}// end isUnderAttack

Private in index(int number ){

.................................................

Returns the array index that correspond to
//a row or column number

//precondition ; 1<= number <=BOARD_SIZE.

//post condition ; returns adjusted index value.