Complete the program that solves the Eight Queens problem (pages 318 through 320
ID: 3704296 • Letter: C
Question
Complete the program that solves the Eight Queens problem (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|
Use the Queens class given on pages 318 through 321 of your textbook. In your implementation of the Queens class, complete the body of all methods marked as “ To be implemented in Programming Problem 1. ” Do not change any of the global variable declarations, constructor or placeQueens methods.
public class Queen {
//squares per row or column
public static final int BOARD_SIZE = 8;
//used to indicate an empty square
public static final int EMPTY = 0;
//used to indicate square conains a queen
public static final int QUEEN = 1;
private int board[][];
public void Queens(){
//Constructor: Creates an empty square board
board = new int [BOARD_SIZE][BOARD_SIZE];
} //end constructor
public void clearBoard(){
//clears board
// preconditon: none
//postcondition:set all squares to empty
} //End clearBoard
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
} //end displayBoard
public boolean placeQueens(in column){
//places queens in columns of the board beginning at column specified
//Precondition: Queens 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 returns true;
//otherwise, returns false
if(column > BOARD_SIZE){
return true;
}
else{
boolean queenPlaced =false;
int row = 1;
while(!queenPlaced && (row <= BOARD_SIZE)){
if (isUnderAttack(row, column)){
row++;
}
else {
setQueen(row, column);
queenPlaced = placeQueens(column+1);
if(!queenPlaced){
removeQueen(row, column);
++row;
}
}
}
return queenPlaced;
}
}
private void setQueen(int row, int column){
//sets 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
} //end setQueen
private void removeQueen(int row, int column){
//removes a queen at square indicated by row and column
//preconditon: none
//postcondition: sets the square indicated by row and column to EMPTY
} //end removeQueen
private boolean isUnderAttack(int row, int column){
//determines wether the square on the board ar a fiven row and column is under attack by any queens in the columns 1 through column - 1
//precondition: each column is under attack by any queen placed in a square at a specific row. None of these queens can be attacked by any other queen
/postcondition: if the designated square is under attack, return true; otherwise return false
} //end isUnderAttack
private int index(int number){
//returns the array index that corresponds to a row or column number
//precondition: 1 <= number <= BOARD_SIZE
//postcondtion: returns adjusted index value
} //end Index
} //end Queens
Explanation / Answer
public class Queen
{
// squares per row or column
public static final int BOARD_SIZE = 8;
public static final int EMPTY = 0;
// used to indicate square contains a queen
public static final int QUEEN = 1;
//------------------------------instance variables
private int board[][]; // chess board
// --------------------------constructor
public Queen()
{
// -------------------------------------------------
// Constructor: Creates an empty square board.
// -------------------------------------------------
board = new int[BOARD_SIZE][BOARD_SIZE];
} // end constructor
//------------------------------instance methods
public void clearBoard()
{
// -------------------------------------------------
// Clears the board.
// Precondition: None.
// Postcondition: Sets all squares to EMPTY.
// -------------------------------------------------
// To be implemented in Programming Problem 1
board = new int[BOARD_SIZE][BOARD_SIZE]; // brute force
} // end clearBoard
//---------------------------
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 be implemented in Programming Problem 1
for ( int i = 0; i < BOARD_SIZE; i++)
{
for( int j = 0; j < BOARD_SIZE; j++)
if (board[i][j] == QUEEN)
System.out.println("Queen at row " + (i+1) + " col " + (j +1));
}
// print out board
for ( int i = 0; i < BOARD_SIZE; i++)
{
System.out.println(" ");
for( int j = 0; j < BOARD_SIZE; j++)
if (board[i][j] == QUEEN)System.out.print(" Q ");
else System.out.print(" . ");
}
} // end displayBoard
//------------------------------------
public boolean placeQueens(int column)
{
System.out.println("placeQueens- trying column " + column);
// -------------------------------------------------
// Places queens in columns of the board beginning
// at the column specified.
// Precondition: Queens 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
// returns true; otherwise, returns false (no
// solution exists for a queen anywhere in column
// specified).
// -------------------------------------------------
if (column >= BOARD_SIZE)
{
return true; // base case
}
else
{
boolean queenPlaced = false;
int row = 0; // number of square in column
while ( !queenPlaced && (row < BOARD_SIZE) )
{
// 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 next column,
if (!queenPlaced)
{
// backtrack: remove queen placed earlier
// 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)
{
// --------------------------------------------------
// Sets 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.
// --------------------------------------------------
// To be implemented in Programming Problem 1
board[row][column] = QUEEN;
System.out.println("setQueen - queen placed at Col " + column +" row " + row);
} // end setQueen
//---------------------------------
private void removeQueen(int row, int column)
{
// --------------------------------------------------
// Removes 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][column] = 0;
System.out.println("removeQueen - queen removed from Col " + column +" row " + row);
return ;
} // end removeQueen
//---------------------------------
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 designated square is under
// attack, returns true; otherwise, returns false.
// --------------------------------------------------
// To be implemented in Programming Problem 1
// check rows and column for attack
for ( int i = 0; i < BOARD_SIZE; i++)
{
if (board[i][column] == QUEEN) return true;
}
for ( int i = 0; i < BOARD_SIZE; i++)
{
if (board[row][i] == QUEEN)return true;
}
// now check the diagonals
// from position to upper left
int r = row; int c = column;
while((r >= 0) && (c >= 0))
{
if (board[r][c] == QUEEN)return true;
r--; c--;
}
// from position to lower right
r = row; c = column; // back to position
while((r < BOARD_SIZE) && (c < BOARD_SIZE))
{
if (board[r][c] == QUEEN)return true;
r++; c++;
}
// from position to upper right
r = row; c = column; // back to position
while((r >= 0 ) && (c < BOARD_SIZE))
{
if (board[r][c] == QUEEN)return true;
r--; c++;
}
// from position to lower left
r = row; c = column; // back to position
while((r < BOARD_SIZE) && (c >= 0))
{
if (board[r][c] == QUEEN)return true;
r++; c--;
}
return false;
} // end isUnderAttack
//--------------------------------static method
public static void main (String [] args)
{
Queen q = new Queen();
q.placeQueens(0);
q.displayBoard();
}
//-------------------------------------------
private int index(int number)
{
// --------------------------------------------------
// Returns the array index that corresponds to
// a row or column number.
// Precondition: 1 <= number <= BOARD_SIZE.
// Postcondition: Returns adjusted index value.
// --------------------------------------------------
return (number);
} // end index
}
( or )
public class NQueenProblem
{
final int N = ;
/* A utility function to print solution */
void printSolution(int board[][])
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
System.out.print(" " + board[i][j]
+ " ");
System.out.println();
}
}
/* A utility function to check if a queen can
be placed on board[row][col]. Note that this
function is called when "col" queens are already
placeed in columns from 0 to col -1. So we need
to check only left side for attacking queens */
boolean isSafe(int board[][], int row, int col)
{
int i, j;
/* Check this row on left side */
for (i = 0; i < col; i++)
if (board[row][i] == 1)
return false;
/* Check upper diagonal on left side */
for (i=row, j=col; i>=0 && j>=0; i--, j--)
if (board[i][j] == 1)
return false;
/* Check lower diagonal on left side */
for (i=row, j=col; j>=0 && i<N; i++, j--)
if (board[i][j] == 1)
return false;
return true;
}
/* A recursive utility function to solve N
Queen problem */
boolean solveNQUtil(int board[][], int col)
{
/* base case: If all queens are placed
then return true */
if (col >= N)
return true;
/* Consider this column and try placing
this queen in all rows one by one */
for (int i = 0; i < N; i++)
{
/* Check if queen can be placed on
board[i][col] */
if (isSafe(board, i, col))
{
/* Place this queen in board[i][col] */
board[i][col] = 1;
/* recur to place rest of the queens */
if (solveNQUtil(board, col + 1) == true)
return true;
/* If placing queen in board[i][col]
doesn't lead to a solution then
remove queen from board[i][col] */
board[i][col] = 0; // BACKTRACK
}
}
/* If queen can not be place in any row in
this colum col, then return false */
return false;
}
/* This function solves the N Queen problem using
Backtracking. It mainly uses solveNQUtil() to
solve the problem. It returns false if queens
cannot be placed, otherwise return true and
prints placement of queens in the form of 1s.
Please note that there may be more than one
solutions, this function prints one of the
feasible solutions.*/
boolean solveNQ()
{
int board[][] = {{0, 0, 0, 0,0, 0, 0, 0},
{0, 0, 0, 0,0, 0, 0, 0},
{0, 0, 0, 0,0, 0, 0, 0},
{0, 0, 0, 0,0, 0, 0, 0}
};
if (solveNQUtil(board, 0) == false)
{
System.out.print("Solution does not exist");
return false;
}
printSolution(board);
return true;
}
// driver program to test above function
public static void main(String args[])
{
NQueenProblem Queen = new NQueenProblem();
Queen.solveNQ();
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.