Question

Complete the program that solves the Eight Queens problem. 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. 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.

Here is what I have so far with notes of what is needed.

public class Queens {

public static final int BOARD_SIZE = 8;
//squares per row and column

public static final int EMPTY = 0;
//used to indicate an empty square

public static final int QUEEN = 1;
//used to indicate sqaure contains a queen

private int board[][];//board
  
public Queens() {
//---------------------------------------------------
//Constructor: creates an empty square borad.
//---------------------------------------------------
board = new int[BOARD_SIZE][BOARD_SIZE];
}//end constructor

public void clearBoard() {
//-----------------------------------------------
// clears the board

// Precondition: None

//postcondition: sets all sqaures to empty
//------------------------------------------------

//To be implemented in Program Problem 1

}//end clearBoard

public void displayBoard() {
//------------------------------------------------
// display the board

//Precondition: None

//Postcondition: Board is written to standard
//output; zero is an EMPTY sqaure
//one is a square containing a queen (QUEEN)
//-------------------------------------------------

//To be implemented in Program Problem 1
}//end displayBoard

public boolean placeQueens(int column) {
//----------------------------------------------
//Places queens in column of the board beginning
//at the column specified.

//Precondition: queens are placed correctly in column 1 to through clumn -1

//Postcondition: If a solution is found, each column of the board contains one queen
//and method returns true; otherwise, return 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 sqaure can be attacked
if (isUnderAttack(row, column)) {
  
++row;//consider next column
} 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 end if
}//end while
  
return queenPlaced;
}//end if
}//end placeQueens

private void setQueen(int row, int column){
//-------------------------------------
//sets a queen at aquare indicated by row and column
  
//Precondition: Mone
//Postcondition: sets the sqaure on the board in a given rose and column to QUEEN.
//--------------------------------------
//To be implemented in Program Problem 1
}//end setQueen

private void removeQueen(int row, int column){
//-----------------------------------------------------
//Removes a qiueen at square indicated by row and cliumn
  
//Precondition: None
//Postcondition: Sets a sqaure on the board in a given row and column to EMPTY.
//---------------------------------------------------
//To be implemented in Program Problem 1
}//end removeQueen

private boolean isUnderAttack(int row, int column){
//------------------------------------------------------
//Determimne whether a square on the board at a given row and column
//is under attack by any queens.
//in the columns 1 thorugh -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, return true otherwise
//return false.
//------------------------------------------------------------
//To be implemented in Program Problem 1
}//end isUnderAttack ERROR

private int index(int number){
  
//----------------------------------------------------
//Returns the array index that corresponds to a row or colum numnber.
  
//Precondtion: 1 <= number <= BOARD_SIZE
  
//Postcondition: Returns adjusted index value
//--------------------------------------------------------
//To be implemented in Program Problem 1
}//end index ERROR
}//Queens

Thank you

Answer 1

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.
                // -------------------------------------------------
                board = new int[BOARD_SIZE][BOARD_SIZE];
                for (int i = 0; i < BOARD_SIZE; i++) {
                        for (int j = 0; j < BOARD_SIZE; j++) {
                                removeQueen(i, j);
                        }
                }
        } // 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).
                // -------------------------------------------------
                for (int i = 0; i < BOARD_SIZE; i++) {
                        for (int j = 0; j < BOARD_SIZE; j++) {
                                if (board[i][j] == QUEEN) {
                                        System.out.print("|1|");
                                } else {
                                        System.out.print("|0|");
                                }
                        }
                        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.
                // --------------------------------------------------
                board[index(row)][index(column)] = QUEEN;
        } // 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[index(row)][index(column)] = EMPTY;
        } // 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.
                // --------------------------------------------------
                // check column
                for (int i = 0; i < index(row); i++) {
                        if (board[i][index(column)] == 1) {
                                return true;
                        }
                }
                // check row
                for (int i = 0; i < index(column); i++) {
                        if (board[index(row)][i] == 1) {
                                return true;
                        }
                }

                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
} // end Queens