n-queens, checking for a valid board

Question

So I'm trying to solve the n-queens problem. I think I have a valid backtracking implementation, but I think my method for checking if a board is valid is off(as well as wildly inefficient), but I can't see why. Can anyone see why / offer a better method?

/** Given an N x N chess board, find placements for N queens on the board such that
* none of them are attacking another queen (two queens are attacking each other if
* they occupy the same row, column, or diagonal).
* Print out the row, col coordinates for each queen on a separate line, where the
* row and column numbers are separated by a single space. */
static void solveQueens(int n) {
    boolean[][] board = new boolean[n][n];
    board = solveQueens(board, n);
    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);
            }
        }
    }
}
/** Returns a solved board for the n-queens problem, given an empty board. */
static boolean[][] solveQueens(boolean[][] board, int queensLeft) {
    if (queensLeft == 0) {
        return board;
    }
    for (int i = 0; i < board.length; i++) {
        for (int j = 0; j < board.length; j++) {
            if (board[i][j]) { continue; }
            board[i][j] = true;
            if (isValid(board)) {
                return solveQueens(board, queensLeft - 1);
            } else {
                board[i][j] = false;
            }
        }
    }
    return null;
}
/** True iff BOARD is a valid solution, with no queens attacking each other. */
static boolean isValid(boolean[][] board) {
    boolean occupied = false;
    //Horizontal
    for (int i = 0; i < board.length; i++) {
        for (boolean queen : board[i]) {
            if (queen && occupied) {
                return false;
            }
            if (queen) {
                occupied = true;
            }
        }
        occupied = false;
    }
    //Vertical
    for (int i = 0; i < board.length; i++) {
        for (int j = board.length - 1; j >= 0; j--) {
            boolean queen = board[j][i];
            if (queen && occupied) {
                return false;
            }
            if (queen) {
                occupied = true;
            }
        }
        occupied = false;
    }
    //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;
}

Answer 1

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!