QUEENS N PROBLEM USING THE METHODS GIVEN FINISH THE PROGRAM, I ALREADY DID IT HO
ID: 3690924 • Letter: Q
Question
QUEENS N PROBLEM
USING THE METHODS GIVEN FINISH THE PROGRAM, I ALREADY DID IT HOWEVER IT ONLY PRINTS ONE SOLUTION AND I WOULD LIKE IT TO PRINT ALL, CAN YOU EDIT MY CODE TO PRINT ALL SOLUTIONS? I WILL COMPARE IT TO MY ORIGINAL CODE TO UNDERSTAND WHAT WAS DONE!
/**
* Solves the 8 Queens on an 8x8 chessboard problem. (either 1 or all solutions are fine)
*
* @author (Potato-San)
* @version (1/1/1111)
*/
import java.util.Scanner;
public class Queens
{
// 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 contains a queen
public static final int QUEEN = 1;
private int board[][]; // chess board
public Queens() {
// -------------------------------------------------
// Constructor: Creates 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.
// -------------------------------------------------
for(int j = 1; j < 8; j++)
{
for(int k = 1; k < 8; k++) //Sets every column in this row to 0
{
board[j][k] = 0;
}
//moves on to next row and repeats
}
} // 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).
// -------------------------------------------------
placeQueens(1);
int N = board.length;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (board[i][j] == 1)
{
System.out.print("Q ");
}
else
{
System.out.print("_|");
}
}
System.out.println();
}
} // end displayBoard
public boolean placeQueens(int 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 = 1; // 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.
// --------------------------------------------------
row = index(row);
column = index(column);
board[row][column] = 1; //Queen placed on square
} // 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.
// --------------------------------------------------
column = index(column);
for(int x = 0; x < 8 ; x++)
{
if(board[x][column] == 1)
{
board[x][column] = 0;
x = 8;
}
}
} // 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.
// --------------------------------------------------
//Taking 1-8 & returning 0-7 to suite array
row = index(row);
column = index(column);
//Checks the rows & columns
//Rows
for(int i = 0; i < column && i < 8 && row < 8; i++)
{
//If there's a queen in that row, the queen is under attack
if(board[row][i] == 1)
{
return true;
}
}
//Column
for(int j = 0; j < row && j < 8 && column < 8; j++)
{
//If there's a queen in that column, the queen is under attack
if(board[j][column] == 1)
{
return true;
}
}
//Check diagonals
for(int i = row, j = column; i >= 0 && j >= 0 && i < 8 && j < 8; i--, j--)
{
//checks upper diagonal
if(board[i][j] == 1)
{
return true;
}
}
for(int i = row, j = column; i < board.length && j >= 0 && i < 8 && j < 8; i++, j--)
{
//checks lower diagonal
if(board[i][j] == 1)
{
return true;
}
}
//At this point the Queen is not being attacked
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.
// Postcondition: Returns adjusted index value.
// --------------------------------------------------
return number - 1;
}// end index
public static void main(String[] args)
{
Queens eight = new Queens();
eight.displayBoard();
}
} // end Queens
Explanation / Answer
public class Queens {
public static final int BOARD_SIZE = 8;
public static final int EMPTY = 0;
public static final int QUEEN = 1;
private int board[][];
public static void main(String[] args) {
Queens q = new Queens();
q.placeQueens(0);
q.displayBoard();
}
public Queens(){
this.board = new int[BOARD_SIZE][BOARD_SIZE];
}
public void clearBoard(){
for(int i = 0; i < BOARD_SIZE; i++){
for(int j = 0; j < BOARD_SIZE; j++){
removeQueen(i, j);
}
}
}
public void displayBoard(){
for(int i = 0; i < BOARD_SIZE; i++){
for(int j = 0; j < BOARD_SIZE; j++){
System.out.print("[");
if(board[i][j] == QUEEN) System.out.print("Q");
else if(!this.isUnderAttack(i, j)) System.out.print("x");
else System.out.print(" ");
System.out.print("]");
}
System.out.println();
}
}
public boolean placeQueens(int column){
this.displayBoard();
System.out.println();
if (column >= BOARD_SIZE){
return true;
} else {
boolean queenPlaced = false;
int row = 0;
while ( !queenPlaced && (row < BOARD_SIZE) ) {
if (isUnderAttack(row,column)) {
++row;
} else {
setQueen(row, column);
queenPlaced = placeQueens(column+1);
if(!queenPlaced) {
// BACKTRACK
System.out.println("Backtrack");
removeQueen(row,column);
++row;
}
}
}
return queenPlaced;
}
}
private void removeQueen(int row, int column) {
this.board[row][column] = EMPTY;
}
private void setQueen(int row, int column) {
this.board[row][column] = QUEEN;
}
private boolean isUnderAttack(int row, int column) {
// Checking horizontal and vertical
for(int i = 0; i < BOARD_SIZE; i++){
if ( (this.board[row][i] == QUEEN) || (this.board[i][column] == QUEEN)) return true;
}
// Checking diagonal (down - right)
for(int i = 0; row+i < BOARD_SIZE && column+i < BOARD_SIZE; i++){
int tile = this.board[row+i][column+i];
if ( tile == QUEEN ) return true;
}
// Checking diagonal (up - left)
for(int i = 0; row-i >= 0 && column-i >= 0; i++){
if ( this.board[row-i][column-i] == QUEEN ) return true;
}
// Checking diagonal (down - left)
for(int i = 0; row+i < BOARD_SIZE && column-i >= 0; i++){
if ( this.board[row+i][column-i] == QUEEN ) return true;
}
// Checking diagonal (up - right)
for(int i = 0; row-i >= 0 && column+i < BOARD_SIZE; i++){
if ( this.board[row-i][column+i] == QUEEN ) return true;
}
return false;
}
}
sample output
[ ][ ][ ][ ][ ][ ][ ][Q]
[ ][Q][ ][ ][ ][ ][ ][ ]
[ ][ ][ ][Q][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][Q][ ][ ]
[ ][ ][Q][ ][ ][ ][ ][ ]
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.