Instead of trying to place a queen for each square, which is very inefficient (2^(n*n)
), you might want to modify the second solveQueens
function to try placing at most one queen for each row. In other words, the longer solveQueens
function will try every possible column per row, and move on to the next row.
Another point is, the board
variable to the second solveQueens
function is modified in place, so we dont actually have to return it. Instead, we can simply return a true
or false
value to indicate if there is a solution.
So the first solveQueens
function can be changed to:
static void solveQueens(int n) {
boolean[][] board = new boolean[n][n];
// boolean return value from second solveQueens function
boolean solved = solveQueens(board, n);
if (solved) {
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board.length; j++) {
if (board[i][j]) {
System.out.printf("%s %s\n", i, j);
}
}
} else {
System.out.printf("No solution for board of size %d\n", n);
}
}
And the second modified solveQueens
function, which recursively goes down each row, and tries all possible columns for each row:
static boolean solveQueens(boolean[][] board, int row, int n) {
// we have a queen for each row, done
if (row >= n) {
return board;
}
// for the current row, try placing a queen at column 0
// if that fails, try placing a queen at column 1
// if that fails, try placing a queen at column 2, and so on
for (int j = 0; j < board.length; j++) {
board[row][j] = true;
if (isValid(board)) {
// placing at (row, j) is valid, try next row
boolean boardSolved = solveQueens(board, row + 1, n);
if (boardSolved) {
// board is solved, yay
return boardSolved;
}
}
// cannot place queen at (row, j) with current board configuration.
// set board[row][j] back to false
board[i][j] = false;
}
// tried every column in current row and still cant solve, return false
return false;
}
For this portion of the isValid
function:
//Diagonals
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board.length; j++) {
if (board[i][j]) {
for (int k = 0; k < board.length; k++) {
for (int l = 0; l < board.length; l++) {
if (((i - k) == (j - l)) && board[k][l] && !(k == i && l == j)) {
return false;
}
}
}
}
}
}
return true;
In the innermost if
, you will have to use (abs(i - k) == abs(j - l))
instead of (i - k) == (j - l)
. An example where the original code will fail is when i = 0
, j = 3
, k = 3
, l = 0
(a queen is at row 0 column 3, and a second queen is on row 3 column 0), so (i - k) == 0 - 3 == -3
and (j - l) == 3 - 0 == 3
, and even though these 2 queens are diagonal to each other, the innermost if
will fail to detect it. Using abs(i - k) == abs(j - l)
will turn the row distance (i - k
) and column distance (j - l
) into absolute values, and hence will work.
So just change this line:
if (((i - k) == (j - l)) && board[k][l] && !(k == i && l == j)) {
to:
if ((abs(i - k) == abs(j - l)) && board[k][l] && !(k == i && l == j)) {
and the isValid
function should be fine.
Hope that helps!