150NeetCode 150

79.N-Queens

HardBacktracking · 9/9
LeetCode #51Video

Problem

Place n queens on an n x n chessboard so that no two queens attack each other — no two share a row, a column, or a diagonal. Return all distinct solutions.

Each solution is a board drawn as a list of n strings, where 'Q' marks a queen and '.' an empty square.

Examples

Input:  n = 4
Output: [[".Q..","...Q","Q...","..Q."],
         ["..Q.","Q...","...Q",".Q.."]]
Explanation: There are exactly two ways to place 4 non-attacking queens.
Input:  n = 1
Output: [["Q"]]

Constraints

  • 1 <= n <= 9

💡 Key Insight

Each row holds exactly one queen, so place queens row by row and only choose a column. A square (r, c) is attacked if its column, its main diagonal (r - c constant) or its anti-diagonal (r + c constant) is already taken. Tracking those three sets turns each safety check from an O(n) board scan into O(1); packing them into bitmasks makes it even faster and lets you enumerate free columns directly.

Backtracking with Board Scan

TimeO(n! · n)SpaceO(n²)

Intuition

Put a queen in row r, column c only if no earlier queen attacks it. To check, scan upward in the same column and along both upward diagonals (rows below r are still empty). If a row has no safe column, backtrack.

Algorithm

  1. Initialise a char[n][n] board of '.'.
  2. solve(r): if r == n, convert the board to strings and record it.
  3. For each column c: if isSafe(r, c), set 'Q', solve(r + 1), reset to '.'.
  4. isSafe checks (i, c), (i, c - (r - i)), (i, c + (r - i)) for every i < r.

Visualization

n = 4, first solution

row 0: try c=0 -> later dead end; try c=1
. Q . .
row 1: c=0,1,2 attacked; c=3 safe
. Q . .
. . . Q
row 2: c=0 safe
Q . . .
row 3: c=2 safe -> solution [".Q..","...Q","Q...","..Q."]

Code

java
import java.util.*;

class Solution {
    public List<List<String>> solveNQueens(int n) {
        char[][] board = new char[n][n];
        for (char[] row : board) Arrays.fill(row, '.');
        List<List<String>> result = new ArrayList<>();
        solve(board, 0, result);
        return result;
    }

    private void solve(char[][] board, int r, List<List<String>> result) {
        int n = board.length;
        if (r == n) {
            List<String> snapshot = new ArrayList<>();
            for (char[] row : board) snapshot.add(new String(row));
            result.add(snapshot);
            return;
        }
        for (int c = 0; c < n; c++) {
            if (!isSafe(board, r, c)) continue;
            board[r][c] = 'Q';
            solve(board, r + 1, result);
            board[r][c] = '.'; // backtrack
        }
    }

    // only rows above r can contain queens
    private boolean isSafe(char[][] board, int r, int c) {
        int n = board.length;
        for (int i = r - 1, d = 1; i >= 0; i--, d++) {
            if (board[i][c] == 'Q') return false;                       // same column
            if (c - d >= 0 && board[i][c - d] == 'Q') return false;     // up-left diagonal
            if (c + d < n && board[i][c + d] == 'Q') return false;      // up-right diagonal
        }
        return true;
    }
}

Complexity

  • Time: O(n! · n) — row r has at most n - r safe columns, and each check costs O(n).
  • Space: O(n²) — the board, plus O(n) recursion.

Complexity Comparison

Approach Time Space
Board Scan O(n! · n) O(n²)
Column / Diagonal Sets O(n!) O(n²)
Bitmask O(n!), smallest constant O(n)

Common Pitfalls

  • Using r - c directly as an array index — it is negative for c > r; offset by n - 1.
  • Mixing up which diagonal is r - c and which is r + c in the bitmask shifts (<< vs >>) — the result is still a valid search only if both are consistent.
  • Forgetting to mask with full — ~ sets all 32 bits, so columns >= n would look free.
  • Forgetting to clear the three markers when backtracking.