51. N-Queens

Intuition

We need to place n queens such that none of them attack each other. A queen can attack any other queen in the same row, column, or diagonal. We solve this using backtracking — trying all possible placements row-by-row and undoing invalid ones. If we reach the last row with valid placements, we record the solution.

Complexity

Space Complexity	Time Complexity
$\text{O}(N^2)$	$\text{O}(N!)$

Code

List<List<String>> allValidArrangements = new LinkedList<>();

// Check if a queen can be placed at (row, col)
public boolean isSafe(boolean[][] board, int row, int col, int n) {
    // Check the column
    for (int i = 0; i < n; ++i) {
        if (board[i][col]) return false;
    }

    // Check top-left diagonal
    for (int i = col - 1, j = row - 1; i >= 0 && j >= 0; --i, --j) {
        if (board[j][i]) return false;
    }

    // Check bottom-right diagonal
    for (int i = col + 1, j = row + 1; i < n && j < n; ++i, ++j) {
        if (board[j][i]) return false;
    }

    // Check top-right diagonal
    for (int i = col + 1, j = row - 1; i < n && j >= 0; ++i, --j) {
        if (board[j][i]) return false;
    }

    // Check bottom-left diagonal
    for (int i = col - 1, j = row + 1; i >= 0 && j < n; --i, ++j) {
        if (board[j][i]) return false;
    }

    return true;
}

// Backtracking function to place queens row-by-row
public void solveQueens(boolean[][] board, int currentRow, int n) {
    // All queens placed successfully
    if (currentRow == n) {
        List<String> currentBoard = new ArrayList<>();
        for (int i = 0; i < n; ++i) {
            StringBuilder rowRepresentation = new StringBuilder();
            for (int j = 0; j < n; ++j) {
                rowRepresentation.append(board[i][j] ? "Q" : ".");
            }
            currentBoard.add(rowRepresentation.toString());
        }
        allValidArrangements.add(currentBoard);
        return;
    }

    // Try placing a queen in each column of the current row
    for (int col = 0; col < n; ++col) {
        if (isSafe(board, currentRow, col, n)) {
            board[currentRow][col] = true;
            solveQueens(board, currentRow + 1, n);
            board[currentRow][col] = false; // Backtrack
        }
    }
}

// Entry function
public List<List<String>> solveNQueens(int n) {
    boolean[][] board = new boolean[n][n];
    solveQueens(board, 0, n);
    return allValidArrangements;
}