Using recursion and backtracking, write a program in Java to solve the Eight Que
ID: 3691404 • Letter: U
Question
Using recursion and backtracking, write a program in Java to solve the Eight Queens problem. The output of your program should include the display of a board that solves the puzzle.
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.
// -------------------------------------------------
// To be implemented
} // 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
} // 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.
// --------------------------------------------------
// To be implemented
} // 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.
// --------------------------------------------------
// To be implemented
} // 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
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.
// --------------------------------------------------
// To be implemented
return 0;
} // end index
} // end Queens
Explanation / Answer
There is a simple solution which i had solved in college
give input as 8
save using QueenProblem.java and run either using eclipse or netbeans
-----------------------------------------------------------------------
import java.io.InputStreamReader;
import java.util.Scanner;
public class QueenProblem {
public static boolean isconst(int[] p, int n) {
for (int i = 0; i < n; i++) {
if (p[i] == p[n]) return false; // same column
if ((p[i] - p[n]) == (n - i)) return false; // same major diagonal
if ((p[n] - p[i]) == (n - i)) return false; // same minor diagonal
}
return true;
}
public static void Queensprinting(int[] q) {
int N = q.length;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (q[i] == j) System.out.print("Q ");
else System.out.print("* ");
}
System.out.println();
}
System.out.println();
}
public static void enumerate(int N) {
int[] a = new int[N];
enumerate(a, 0);
}
public static void enumerate(int[] p, int n) {
int N = p.length;
if (n == N) Queensprinting(p);
else {
for (int i = 0; i < N; i++) {
p[n] = i;
if (isconst(p, n)) enumerate(p, n+1);
}
}
}
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int N=sc.nextInt();
enumerate(N);
}
}
--------------------------
output for input 8
8
Q * * * * * * *
* * * * Q * * *
* * * * * * * Q
* * * * * Q * *
* * Q * * * * *
* * * * * * Q *
* Q * * * * * *
* * * Q * * * *
Q * * * * * * *
* * * * * Q * *
* * * * * * * Q
* * Q * * * * *
* * * * * * Q *
* * * Q * * * *
* Q * * * * * *
* * * * Q * * *
Q * * * * * * *
* * * * * * Q *
* * * Q * * * *
* * * * * Q * *
* * * * * * * Q
* Q * * * * * *
* * * * Q * * *
* * Q * * * * *
Q * * * * * * *
* * * * * * Q *
* * * * Q * * *
* * * * * * * Q
* Q * * * * * *
* * * Q * * * *
* * * * * Q * *
* * Q * * * * *
* Q * * * * * *
* * * Q * * * *
* * * * * Q * *
* * * * * * * Q
* * Q * * * * *
Q * * * * * * *
* * * * * * Q *
* * * * Q * * *
* Q * * * * * *
* * * * Q * * *
* * * * * * Q *
Q * * * * * * *
* * Q * * * * *
* * * * * * * Q
* * * * * Q * *
* * * Q * * * *
* Q * * * * * *
* * * * Q * * *
* * * * * * Q *
* * * Q * * * *
Q * * * * * * *
* * * * * * * Q
* * * * * Q * *
* * Q * * * * *
* Q * * * * * *
* * * * * Q * *
Q * * * * * * *
* * * * * * Q *
* * * Q * * * *
* * * * * * * Q
* * Q * * * * *
* * * * Q * * *
* Q * * * * * *
* * * * * Q * *
* * * * * * * Q
* * Q * * * * *
Q * * * * * * *
* * * Q * * * *
* * * * * * Q *
* * * * Q * * *
* Q * * * * * *
* * * * * * Q *
* * Q * * * * *
* * * * * Q * *
* * * * * * * Q
* * * * Q * * *
Q * * * * * * *
* * * Q * * * *
* Q * * * * * *
* * * * * * Q *
* * * * Q * * *
* * * * * * * Q
Q * * * * * * *
* * * Q * * * *
* * * * * Q * *
* * Q * * * * *
* Q * * * * * *
* * * * * * * Q
* * * * * Q * *
Q * * * * * * *
* * Q * * * * *
* * * * Q * * *
* * * * * * Q *
* * * Q * * * *
* * Q * * * * *
Q * * * * * * *
* * * * * * Q *
* * * * Q * * *
* * * * * * * Q
* Q * * * * * *
* * * Q * * * *
* * * * * Q * *
* * Q * * * * *
* * * * Q * * *
* Q * * * * * *
* * * * * * * Q
Q * * * * * * *
* * * * * * Q *
* * * Q * * * *
* * * * * Q * *
* * Q * * * * *
* * * * Q * * *
* Q * * * * * *
* * * * * * * Q
* * * * * Q * *
* * * Q * * * *
* * * * * * Q *
Q * * * * * * *
* * Q * * * * *
* * * * Q * * *
* * * * * * Q *
Q * * * * * * *
* * * Q * * * *
* Q * * * * * *
* * * * * * * Q
* * * * * Q * *
* * Q * * * * *
* * * * Q * * *
* * * * * * * Q
* * * Q * * * *
Q * * * * * * *
* * * * * * Q *
* Q * * * * * *
* * * * * Q * *
* * Q * * * * *
* * * * * Q * *
* Q * * * * * *
* * * * Q * * *
* * * * * * * Q
Q * * * * * * *
* * * * * * Q *
* * * Q * * * *
* * Q * * * * *
* * * * * Q * *
* Q * * * * * *
* * * * * * Q *
Q * * * * * * *
* * * Q * * * *
* * * * * * * Q
* * * * Q * * *
* * Q * * * * *
* * * * * Q * *
* Q * * * * * *
* * * * * * Q *
* * * * Q * * *
Q * * * * * * *
* * * * * * * Q
* * * Q * * * *
* * Q * * * * *
* * * * * Q * *
* * * Q * * * *
Q * * * * * * *
* * * * * * * Q
* * * * Q * * *
* * * * * * Q *
* Q * * * * * *
* * Q * * * * *
* * * * * Q * *
* * * Q * * * *
* Q * * * * * *
* * * * * * * Q
* * * * Q * * *
* * * * * * Q *
Q * * * * * * *
* * Q * * * * *
* * * * * Q * *
* * * * * * * Q
Q * * * * * * *
* * * Q * * * *
* * * * * * Q *
* * * * Q * * *
* Q * * * * * *
* * Q * * * * *
* * * * * Q * *
* * * * * * * Q
Q * * * * * * *
* * * * Q * * *
* * * * * * Q *
* Q * * * * * *
* * * Q * * * *
* * Q * * * * *
* * * * * Q * *
* * * * * * * Q
* Q * * * * * *
* * * Q * * * *
Q * * * * * * *
* * * * * * Q *
* * * * Q * * *
* * Q * * * * *
* * * * * * Q *
* Q * * * * * *
* * * * * * * Q
* * * * Q * * *
Q * * * * * * *
* * * Q * * * *
* * * * * Q * *
* * Q * * * * *
* * * * * * Q *
* Q * * * * * *
* * * * * * * Q
* * * * * Q * *
* * * Q * * * *
Q * * * * * * *
* * * * Q * * *
* * Q * * * * *
* * * * * * * Q
* * * Q * * * *
* * * * * * Q *
Q * * * * * * *
* * * * * Q * *
* Q * * * * * *
* * * * Q * * *
* * * Q * * * *
Q * * * * * * *
* * * * Q * * *
* * * * * * * Q
* Q * * * * * *
* * * * * * Q *
* * Q * * * * *
* * * * * Q * *
* * * Q * * * *
Q * * * * * * *
* * * * Q * * *
* * * * * * * Q
* * * * * Q * *
* * Q * * * * *
* * * * * * Q *
* Q * * * * * *
* * * Q * * * *
* Q * * * * * *
* * * * Q * * *
* * * * * * * Q
* * * * * Q * *
Q * * * * * * *
* * Q * * * * *
* * * * * * Q *
* * * Q * * * *
* Q * * * * * *
* * * * * * Q *
* * Q * * * * *
* * * * * Q * *
* * * * * * * Q
Q * * * * * * *
* * * * Q * * *
* * * Q * * * *
* Q * * * * * *
* * * * * * Q *
* * Q * * * * *
* * * * * Q * *
* * * * * * * Q
* * * * Q * * *
Q * * * * * * *
* * * Q * * * *
* Q * * * * * *
* * * * * * Q *
* * * * Q * * *
Q * * * * * * *
* * * * * * * Q
* * * * * Q * *
* * Q * * * * *
* * * Q * * * *
* Q * * * * * *
* * * * * * * Q
* * * * Q * * *
* * * * * * Q *
Q * * * * * * *
* * Q * * * * *
* * * * * Q * *
* * * Q * * * *
* Q * * * * * *
* * * * * * * Q
* * * * * Q * *
Q * * * * * * *
* * Q * * * * *
* * * * Q * * *
* * * * * * Q *
* * * Q * * * *
* * * * * Q * *
Q * * * * * * *
* * * * Q * * *
* Q * * * * * *
* * * * * * * Q
* * Q * * * * *
* * * * * * Q *
* * * Q * * * *
* * * * * Q * *
* * * * * * * Q
* Q * * * * * *
* * * * * * Q *
Q * * * * * * *
* * Q * * * * *
* * * * Q * * *
* * * Q * * * *
* * * * * Q * *
* * * * * * * Q
* * Q * * * * *
Q * * * * * * *
* * * * * * Q *
* * * * Q * * *
* Q * * * * * *
* * * Q * * * *
* * * * * * Q *
Q * * * * * * *
* * * * * * * Q
* * * * Q * * *
* Q * * * * * *
* * * * * Q * *
* * Q * * * * *
* * * Q * * * *
* * * * * * Q *
* * Q * * * * *
* * * * * * * Q
* Q * * * * * *
* * * * Q * * *
Q * * * * * * *
* * * * * Q * *
* * * Q * * * *
* * * * * * Q *
* * * * Q * * *
* Q * * * * * *
* * * * * Q * *
Q * * * * * * *
* * Q * * * * *
* * * * * * * Q
* * * Q * * * *
* * * * * * Q *
* * * * Q * * *
* * Q * * * * *
Q * * * * * * *
* * * * * Q * *
* * * * * * * Q
* Q * * * * * *
* * * Q * * * *
* * * * * * * Q
Q * * * * * * *
* * Q * * * * *
* * * * * Q * *
* Q * * * * * *
* * * * * * Q *
* * * * Q * * *
* * * Q * * * *
* * * * * * * Q
Q * * * * * * *
* * * * Q * * *
* * * * * * Q *
* Q * * * * * *
* * * * * Q * *
* * Q * * * * *
* * * Q * * * *
* * * * * * * Q
* * * * Q * * *
* * Q * * * * *
Q * * * * * * *
* * * * * * Q *
* Q * * * * * *
* * * * * Q * *
* * * * Q * * *
Q * * * * * * *
* * * Q * * * *
* * * * * Q * *
* * * * * * * Q
* Q * * * * * *
* * * * * * Q *
* * Q * * * * *
* * * * Q * * *
Q * * * * * * *
* * * * * * * Q
* * * Q * * * *
* Q * * * * * *
* * * * * * Q *
* * Q * * * * *
* * * * * Q * *
* * * * Q * * *
Q * * * * * * *
* * * * * * * Q
* * * * * Q * *
* * Q * * * * *
* * * * * * Q *
* Q * * * * * *
* * * Q * * * *
* * * * Q * * *
* Q * * * * * *
* * * Q * * * *
* * * * * Q * *
* * * * * * * Q
* * Q * * * * *
Q * * * * * * *
* * * * * * Q *
* * * * Q * * *
* Q * * * * * *
* * * Q * * * *
* * * * * * Q *
* * Q * * * * *
* * * * * * * Q
* * * * * Q * *
Q * * * * * * *
* * * * Q * * *
* Q * * * * * *
* * * * * Q * *
Q * * * * * * *
* * * * * * Q *
* * * Q * * * *
* * * * * * * Q
* * Q * * * * *
* * * * Q * * *
* Q * * * * * *
* * * * * * * Q
Q * * * * * * *
* * * Q * * * *
* * * * * * Q *
* * Q * * * * *
* * * * * Q * *
* * * * Q * * *
* * Q * * * * *
Q * * * * * * *
* * * * * Q * *
* * * * * * * Q
* Q * * * * * *
* * * Q * * * *
* * * * * * Q *
* * * * Q * * *
* * Q * * * * *
Q * * * * * * *
* * * * * * Q *
* Q * * * * * *
* * * * * * * Q
* * * * * Q * *
* * * Q * * * *
* * * * Q * * *
* * Q * * * * *
* * * * * * * Q
* * * Q * * * *
* * * * * * Q *
Q * * * * * * *
* * * * * Q * *
* Q * * * * * *
* * * * Q * * *
* * * * * * Q *
Q * * * * * * *
* * Q * * * * *
* * * * * * * Q
* * * * * Q * *
* * * Q * * * *
* Q * * * * * *
* * * * Q * * *
* * * * * * Q *
Q * * * * * * *
* * * Q * * * *
* Q * * * * * *
* * * * * * * Q
* * * * * Q * *
* * Q * * * * *
* * * * Q * * *
* * * * * * Q *
* Q * * * * * *
* * * Q * * * *
* * * * * * * Q
Q * * * * * * *
* * Q * * * * *
* * * * * Q * *
* * * * Q * * *
* * * * * * Q *
* Q * * * * * *
* * * * * Q * *
* * Q * * * * *
Q * * * * * * *
* * * Q * * * *
* * * * * * * Q
* * * * Q * * *
* * * * * * Q *
* Q * * * * * *
* * * * * Q * *
* * Q * * * * *
Q * * * * * * *
* * * * * * * Q
* * * Q * * * *
* * * * Q * * *
* * * * * * Q *
* * * Q * * * *
Q * * * * * * *
* * Q * * * * *
* * * * * * * Q
* * * * * Q * *
* Q * * * * * *
* * * * Q * * *
* * * * * * * Q
* * * Q * * * *
Q * * * * * * *
* * Q * * * * *
* * * * * Q * *
* Q * * * * * *
* * * * * * Q *
* * * * Q * * *
* * * * * * * Q
* * * Q * * * *
Q * * * * * * *
* * * * * * Q *
* Q * * * * * *
* * * * * Q * *
* * Q * * * * *
* * * * * Q * *
Q * * * * * * *
* * * * Q * * *
* Q * * * * * *
* * * * * * * Q
* * Q * * * * *
* * * * * * Q *
* * * Q * * * *
* * * * * Q * *
* Q * * * * * *
* * * * * * Q *
Q * * * * * * *
* * Q * * * * *
* * * * Q * * *
* * * * * * * Q
* * * Q * * * *
* * * * * Q * *
* Q * * * * * *
* * * * * * Q *
Q * * * * * * *
* * * Q * * * *
* * * * * * * Q
* * * * Q * * *
* * Q * * * * *
* * * * * Q * *
* * Q * * * * *
Q * * * * * * *
* * * * * * Q *
* * * * Q * * *
* * * * * * * Q
* Q * * * * * *
* * * Q * * * *
* * * * * Q * *
* * Q * * * * *
Q * * * * * * *
* * * * * * * Q
* * * Q * * * *
* Q * * * * * *
* * * * * * Q *
* * * * Q * * *
* * * * * Q * *
* * Q * * * * *
Q * * * * * * *
* * * * * * * Q
* * * * Q * * *
* Q * * * * * *
* * * Q * * * *
* * * * * * Q *
* * * * * Q * *
* * Q * * * * *
* * * * Q * * *
* * * * * * Q *
Q * * * * * * *
* * * Q * * * *
* Q * * * * * *
* * * * * * * Q
* * * * * Q * *
* * Q * * * * *
* * * * Q * * *
* * * * * * * Q
Q * * * * * * *
* * * Q * * * *
* Q * * * * * *
* * * * * * Q *
* * * * * Q * *
* * Q * * * * *
* * * * * * Q *
* Q * * * * * *
* * * Q * * * *
* * * * * * * Q
Q * * * * * * *
* * * * Q * * *
* * * * * Q * *
* * Q * * * * *
* * * * * * Q *
* Q * * * * * *
* * * * * * * Q
* * * * Q * * *
Q * * * * * * *
* * * Q * * * *
* * * * * Q * *
* * Q * * * * *
* * * * * * Q *
* * * Q * * * *
Q * * * * * * *
* * * * * * * Q
* Q * * * * * *
* * * * Q * * *
* * * * * Q * *
* * * Q * * * *
Q * * * * * * *
* * * * Q * * *
* * * * * * * Q
* Q * * * * * *
* * * * * * Q *
* * Q * * * * *
* * * * * Q * *
* * * Q * * * *
* Q * * * * * *
* * * * * * * Q
* * * * Q * * *
* * * * * * Q *
Q * * * * * * *
* * Q * * * * *
* * * * * Q * *
* * * Q * * * *
* * * * * * Q *
Q * * * * * * *
* * Q * * * * *
* * * * Q * * *
* Q * * * * * *
* * * * * * * Q
* * * * * Q * *
* * * Q * * * *
* * * * * * Q *
Q * * * * * * *
* * * * * * * Q
* Q * * * * * *
* * * * Q * * *
* * Q * * * * *
* * * * * Q * *
* * * * * * * Q
* Q * * * * * *
* * * Q * * * *
Q * * * * * * *
* * * * * * Q *
* * * * Q * * *
* * Q * * * * *
* * * * * * Q *
Q * * * * * * *
* * Q * * * * *
* * * * * * * Q
* * * * * Q * *
* * * Q * * * *
* Q * * * * * *
* * * * Q * * *
* * * * * * Q *
* Q * * * * * *
* * * Q * * * *
Q * * * * * * *
* * * * * * * Q
* * * * Q * * *
* * Q * * * * *
* * * * * Q * *
* * * * * * Q *
* Q * * * * * *
* * * * * Q * *
* * Q * * * * *
Q * * * * * * *
* * * Q * * * *
* * * * * * * Q
* * * * Q * * *
* * * * * * Q *
* * Q * * * * *
Q * * * * * * *
* * * * * Q * *
* * * * * * * Q
* * * * Q * * *
* Q * * * * * *
* * * Q * * * *
* * * * * * Q *
* * Q * * * * *
* * * * * * * Q
* Q * * * * * *
* * * * Q * * *
Q * * * * * * *
* * * * * Q * *
* * * Q * * * *
* * * * * * Q *
* * * Q * * * *
* Q * * * * * *
* * * * Q * * *
* * * * * * * Q
Q * * * * * * *
* * Q * * * * *
* * * * * Q * *
* * * * * * Q *
* * * Q * * * *
* Q * * * * * *
* * * * * * * Q
* * * * * Q * *
Q * * * * * * *
* * Q * * * * *
* * * * Q * * *
* * * * * * Q *
* * * * Q * * *
* * Q * * * * *
Q * * * * * * *
* * * * * Q * *
* * * * * * * Q
* Q * * * * * *
* * * Q * * * *
* * * * * * * Q
* Q * * * * * *
* * * Q * * * *
Q * * * * * * *
* * * * * * Q *
* * * * Q * * *
* * Q * * * * *
* * * * * Q * *
* * * * * * * Q
* Q * * * * * *
* * * * Q * * *
* * Q * * * * *
Q * * * * * * *
* * * * * * Q *
* * * Q * * * *
* * * * * Q * *
* * * * * * * Q
* * Q * * * * *
Q * * * * * * *
* * * * * Q * *
* Q * * * * * *
* * * * Q * * *
* * * * * * Q *
* * * Q * * * *
* * * * * * * Q
* * * Q * * * *
Q * * * * * * *
* * 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.