Question: Complete the program that solves the Eight Queens problem in java only please (pages 318 through 320). The programs output should look similar to: |1|0|0|0|0|0|0|0|
Complete the program that solves the Eight Queens problem in java only please (pages 318 through
320). The programs 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.
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help