N-Queens

HardBacktracking · Constraint Pruning🧩 Backtracking LeetCode #51 ↗Updated Oct 30, 2026

Problem

Place n chess queens on an n × n board so that no two attack each other (no shared row, column or diagonal). Return every distinct arrangement, each drawn as n strings where 'Q' is a queen and '.' is an empty square.

Inputn=4Output[[".Q..","...Q","Q...","..Q."], ["..Q.","Q...","...Q",".Q.."]]

Inputn=1Output[["Q"]]

1 ≤ n ≤ 9

Try it yourself

Java

class Solution {
    public List<List<String>> solveNQueens(int n) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

One queen per row → fill the board row by row, trying only safe columns. A square's attack lines are its column, row - col and row + col; mark those three and each safety check is O(1).

PatternBacktracking

Instinct Return ALL combinations, permutations, partitions or placements - or ask if any arrangement works - build a candidate step by step and undo each choice.

Memory hack Choose, explore, un-choose - walk the decision tree and snip a branch the moment it can no longer succeed.

Open the Backtracking guide →

Approaches

Brute ForceAll Permutations, then Validate

Time O(n! · n²)Space O(n)

Try every column permutation q (rows/columns can't clash) and keep those with no diagonal pair, i.e. |q[i]-q[j]| == j-i.

Java

public List<List<String>> solveNQueens(int n) {
    List<List<String>> res = new ArrayList<>();
    permute(new int[n], 0, new boolean[n], res);
    return res;
}
private void permute(int[] q, int row, boolean[] used, List<List<String>> res) {
    if (row == q.length) { if (valid(q)) res.add(draw(q)); return; }
    for (int c = 0; c < q.length; c++) {
        if (used[c]) continue;
        used[c] = true; q[row] = c;
        permute(q, row + 1, used, res);
        used[c] = false;
    }
}
private boolean valid(int[] q) {
    for (int i = 0; i < q.length; i++)
        for (int j = i + 1; j < q.length; j++)
            if (Math.abs(q[i] - q[j]) == j - i) return false; // same diagonal
    return true;
}
private List<String> draw(int[] q) {
    List<String> board = new ArrayList<>();
    for (int c : q) board.add(".".repeat(c) + "Q" + ".".repeat(q.length - c - 1));
    return board;
}

Correct but blind: it builds every full permutation before checking diagonals.

BetterBacktracking + Column/Diagonal Arrays

Time O(n!)Space O(n²)

Check safety while placing: flags for columns, row-col+n-1 diagonals and row+col anti-diagonals; place, recurse, undo.

Java

public List<List<String>> solveNQueens(int n) {
    List<List<String>> res = new ArrayList<>();
    char[][] board = new char[n][n];
    for (char[] row : board) Arrays.fill(row, '.');
    backtrack(0, n, board, new boolean[n], new boolean[2 * n - 1], new boolean[2 * n - 1], res);
    return res;
}
private void backtrack(int row, int n, char[][] board, boolean[] cols, boolean[] diag,
                       boolean[] anti, List<List<String>> res) {
    if (row == n) { res.add(Arrays.stream(board).map(String::new).toList()); return; }
    for (int col = 0; col < n; col++) {
        int d = row - col + n - 1, a = row + col;
        if (cols[col] || diag[d] || anti[a]) continue; // square is attacked
        cols[col] = diag[d] = anti[a] = true; board[row][col] = 'Q';
        backtrack(row + 1, n, board, cols, diag, anti, res);
        cols[col] = diag[d] = anti[a] = false; board[row][col] = '.'; // undo
    }
}

Prunes dead branches early with O(1) checks; the char board costs O(n²).

OptimalBitmask Backtracking

Time O(n!)Space O(n)

Attacked columns live as bits in three ints. Going down a row shifts the diagonal masks (<<1, >>1), and free & -free jumps straight to the next safe column.

Java

public List<List<String>> solveNQueens(int n) {
    List<List<String>> res = new ArrayList<>();
    solve(n, 0, 0, 0, 0, new int[n], res);
    return res;
}
// cols / ld / rd: bitmasks of columns attacked in the current row
private void solve(int n, int row, int cols, int ld, int rd, int[] q,
                   List<List<String>> res) {
    if (row == n) { res.add(draw(q)); return; }
    int free = ~(cols | ld | rd) & ((1 << n) - 1);
    while (free != 0) {
        int bit = free & -free; // lowest safe column
        free -= bit;
        q[row] = Integer.numberOfTrailingZeros(bit);
        solve(n, row + 1, cols | bit, (ld | bit) << 1, (rd | bit) >> 1, q, res);
    }
}
private List<String> draw(int[] q) {
    List<String> board = new ArrayList<>();
    for (int c : q) board.add(".".repeat(c) + "Q" + ".".repeat(q.length - c - 1));
    return board;
}

Same search tree, far smaller constant, and only O(n) state (q[] + recursion).

At a glance

Level	Approach	Time	Space
Brute Force	All Permutations, then Validate	`O(n! · n²)`	`O(n)`
Better	Backtracking + Column/Diagonal Arrays	`O(n!)`	`O(n²)`
Optimal	Bitmask Backtracking	`O(n!)`	`O(n)`

Common pitfalls

Diagonal index row - col is negative — offset it by n - 1.
Forgetting to undo the marks / board cell after the recursive call.
Bitmask: not masking with (1 << n) - 1, so shifted bits leak out.

Interview tips

Say up front: one queen per row turns 2-D placement into choosing a column per row.
Explain the diagonal identities r-c and r+c before coding.
Mention the bitmask version as the follow-up optimisation once sets work.

Pattern

Backtracking with constraint sets → place items one slot at a time, prune as soon as a constraint breaks (Sudoku, N-Queens, combinations).

My notes saved in this browser