N-Queens

1. Problem & Core Objective

Place n queens on an n × n board so that no two attack each other. Queens attack along rows, columns, and both diagonals. Return all distinct solutions as board drawings.

n = 4  →  2 solutions

. Q . .        . . Q .
. . . Q        Q . . .
Q . . .        . . . Q
. . Q .        . Q . .

Constraints: 1 <= n <= 9

What's actually being tested: the payoff of pruning with an O(1) validity check. The naive board scan makes every placement O(n) to verify; encoding the two diagonals arithmetically makes it O(1). It's the hardest question in the section and the one where the constraint check does the most work.

2. First-Principles Thought Process

One queen per row, by construction

Two queens in the same row always attack. So any solution has exactly one queen per row — which means the search can place them row by row and never check rows at all.

That immediately reduces the problem from "choose n cells out of n²" to "choose a column for each of n rows": from C(81, 9) ≈ 10^11 down to 9^9 ≈ 4 × 10^8, before any pruning.

What still needs checking

Having fixed rows, a new queen at (r, c) conflicts if some earlier queen shares:

• the same column c
• the same ↘ diagonal
• the same ↗ diagonal

Encoding the diagonals

Scanning previously-placed queens is O(n) per check. But diagonals have a closed form:

• On a ↗ diagonal (going up-right), r + c is constant.
• On a ↘ diagonal (going down-right), r − c is constant.

I verified this on a 4×4 board: r + c produces 7 groups and r − c produces 7 groups, and within every group all cells are mutually diagonal.

So three sets answer the whole question in O(1):

if (cols.contains(c) || diag1.contains(r + c) || diag2.contains(r - c)) continue;

Why that matters so much

The validity check runs at every node of the search tree. Making it O(1) instead of O(n) removes a factor of n from the entire search — and because it also prunes earlier, the tree itself shrinks.

That's the general lesson of this section, at its most extreme: the cheaper your constraint check, the more aggressively you can prune.

The search size

Without pruning, n^n = 9^9 ≈ 387 million placements. With the three checks, the actual explored nodes for n = 9 are in the tens of thousands — the constraints cut almost everything.

3. Solution Paths

Approach 1 — Place queens anywhere, validate by scanning (brute force)

public List<List<String>> solveNQueens(int n) {
    List<List<String>> result = new ArrayList<>();
    backtrack(n, 0, new int[n], result);
    return result;
}

private void backtrack(int n, int row, int[] queenCol, List<List<String>> result) {
    if (row == n) { result.add(draw(queenCol, n)); return; }

    for (int c = 0; c < n; c++) {
        if (!isSafe(queenCol, row, c)) continue;
        queenCol[row] = c;
        backtrack(n, row + 1, queenCol, result);
    }
}

private boolean isSafe(int[] queenCol, int row, int c) {
    for (int r = 0; r < row; r++) {                       // scan every earlier queen
        if (queenCol[r] == c) return false;                // same column
        if (Math.abs(queenCol[r] - c) == row - r) return false;   // same diagonal
    }
    return true;
}

• Time O(n! · n) — the n factor is the scan · Space O(n)

Counter-questions on this approach

⭐ "This is already pruning. What's left to improve?"

The cost of the check. isSafe scans every previously-placed queen, so it's O(row) — up to O(n) — and it runs at every node of the search tree.

Replacing it with three set lookups makes it O(1), removing a factor of n from the whole search. At n = 9 that's a 9× improvement on an already large tree.

⭐ "Explain Math.abs(queenCol[r] - c) == row - r."

Two cells are on a common diagonal exactly when the row distance equals the column distance. row - r is the vertical gap (positive, since r < row), and |queenCol[r] - c| is the horizontal gap. Equal means diagonal.

It's correct and it's the intuitive formulation — it just has to be evaluated against each earlier queen individually, which is what makes it O(n).

"Is the n! bound right?"

It's the standard upper bound: n choices for row 0, at most n − 1 distinct columns for row 1, and so on. The column constraint alone gives n!; the diagonal constraints cut far below that in practice. For n = 9 the real node count is orders of magnitude smaller.

Approach 2 — Sets for column and both diagonals (optimal)

public List<List<String>> solveNQueens(int n) {
    List<List<String>> result = new ArrayList<>();
    backtrack(n, 0, new int[n], new HashSet<>(), new HashSet<>(), new HashSet<>(), result);
    return result;
}

private void backtrack(int n, int row, int[] queenCol,
                       Set<Integer> cols, Set<Integer> diag1, Set<Integer> diag2,
                       List<List<String>> result) {
    if (row == n) { result.add(draw(queenCol, n)); return; }

    for (int c = 0; c < n; c++) {
        if (cols.contains(c) || diag1.contains(row + c) || diag2.contains(row - c))
            continue;                                      // O(1) attack test

        queenCol[row] = c;                                 // choose
        cols.add(c); diag1.add(row + c); diag2.add(row - c);

        backtrack(n, row + 1, queenCol, cols, diag1, diag2, result);

        cols.remove(c); diag1.remove(row + c); diag2.remove(row - c);   // un-choose ALL THREE
    }
}

private List<String> draw(int[] queenCol, int n) {
    List<String> board = new ArrayList<>();
    for (int r = 0; r < n; r++) {
        char[] rowChars = new char[n];
        Arrays.fill(rowChars, '.');
        rowChars[queenCol[r]] = 'Q';
        board.add(new String(rowChars));
    }
    return board;
}

Trace — n = 4, first solution:

• Time O(n!) with O(1) checks · Space O(n) for the sets and the stack

Counter-questions on this approach

⭐ "Why is r + c constant along one diagonal and r − c along the other?"

Moving one step down-left increases r by 1 and decreases c by 1, so r + c is unchanged — that's the ↗/↙ diagonal.

Moving one step down-right increases both by 1, so r − c is unchanged — that's the ↘/↖ diagonal.

I verified it exhaustively on a 4×4 board: both encodings produce 7 groups, and within every group all cells are mutually diagonal. So membership in the set is exactly "attacked along that diagonal".

⭐ "Why does this beat the scan if both prune the same branches?"

Because the check itself is cheaper. The scan is O(row) and runs at every node; three hash lookups are O(1). Same tree, n times less work traversing it.

The sets also make the state explicit: cols, diag1, diag2 are the constraint, so adding a fourth attack direction would be a fourth set rather than a more complicated loop.

⭐ "Three sets, three removals. What if you forget one?"

The search is silently over-constrained. A stale entry in diag1 blocks a legal placement on a later branch, so you get too few solutions rather than a crash.

That's the same failure mode as forgetting used[i] = false in Permutations or the board restore in Word Search — and it's why "undo everything you did" belongs in the template rather than being remembered per problem.

"Can row - c be negative? Does that break the set?"

It ranges from -(n-1) to n-1, so yes, negative. A HashSet<Integer> handles that fine.

If I wanted array-backed sets for speed I'd offset the index: diag2[row - c + n - 1], giving a range of 0 to 2n-2. That's the usual optimisation — boolean[] instead of HashSet<Integer> avoids boxing and hashing entirely, which at n = 9 is measurable but not necessary.

"Why no row check?"

Because placing exactly one queen per row is built into the recursion — row advances by one at each level, so two queens can never share a row. The structure enforces the constraint, so it never needs testing.

That's worth noting as its own idea: the cheapest constraint check is the one you design away.

"Why is queenCol not backtracked?"

Because queenCol[row] is overwritten on the next iteration of the loop before being read, and it's only read up to row when drawing. Nothing stale is ever observed.

It would be safer to reset it, and I wouldn't object to that — but it's genuinely unnecessary here, unlike the three sets.

Approach 3 — Bitmask sets

private void backtrack(int n, int row, int cols, int d1, int d2, ...) {
    if (row == n) { record(); return; }
    int available = ~(cols | d1 | d2) & ((1 << n) - 1);    // free columns as set bits

    while (available != 0) {
        int bit = available & -available;                   // lowest set bit
        available -= bit;
        backtrack(n, row + 1, cols | bit, (d1 | bit) << 1, (d2 | bit) >> 1, ...);
    }
}

The three sets become three integers; the diagonal shift happens automatically as the row advances.

• Time O(n!) with O(1) bit operations · Space O(n) stack

Counter-questions on this approach

⭐ "Why do the diagonals shift instead of storing r ± c?"

Because moving to the next row shifts each diagonal's influence by one column. A queen blocking column c on the ↘ diagonal blocks c + 1 in the next row — which is exactly << 1. The ↗ diagonal blocks c - 1, which is >> 1.

So the shifting is the r ± c arithmetic, applied incrementally rather than recomputed. It's elegant, and it's why this formulation needs no offsetting for negative indices.

"Why available & -available?"

Two's complement isolates the lowest set bit — a standard idiom. It lets the loop iterate only the free columns rather than testing all n, which is a genuine saving when most are blocked.

"Would you write this in an interview?"

I'd write the set version and mention this one. It's meaningfully faster — no boxing, no hashing, and iteration skips blocked columns — but it's much harder to explain under pressure, and at n <= 9 the difference is invisible.

It's the right answer if asked to count solutions for n = 15, where the constant factor genuinely matters.

Comparison

4. Why the Optimal Wins

All three explore the same tree — the pruning is identical. The difference is entirely the cost of asking "is this cell attacked?".

The scan answers it by examining every placed queen. The encodings answer it by observing that diagonals have a closed form, so membership in a set replaces a loop. That removes a factor of n from every node of the search.

And the row constraint is handled best of all: by designing it away. Placing one queen per row means rows never need checking.

The framing worth keeping:

Cells on a ↗ diagonal share r + c; cells on a ↘ diagonal share r − c. Two subtractions turn an O(n) scan into an O(1) set lookup — and the validity check runs at every node, so that factor applies to the whole search.

5. Java Prerequisites

The three attack sets

Set<Integer> cols, diag1, diag2;                            // diag1: r+c, diag2: r-c
if (cols.contains(c) || diag1.contains(r+c) || diag2.contains(r-c)) continue;

cols.add(c); diag1.add(r+c); diag2.add(r-c);
...
cols.remove(c); diag1.remove(r+c); diag2.remove(r-c);       // undo ALL THREE

Array-backed alternative — offset the negative range:

boolean[] diag2 = new boolean[2*n - 1];
diag2[r - c + n - 1]                                        // shift into [0, 2n-2]

Building the board rows

char[] row = new char[n];
Arrays.fill(row, '.');
row[queenCol[r]] = 'Q';
board.add(new String(row));

Bit tricks — x & -x isolates the lowest set bit; (1 << n) - 1 is an n-bit mask. See 22.

6. Interview Communication Guide

Clarifying questions: Return all solutions or just the count (all here; LC 52 is the count)? What's the board format (strings with Q and .)? Maximum n (9)? Do rotations count as distinct solutions (yes — no symmetry deduplication)?

The pitch

"First, a structural simplification: two queens in the same row always attack, so every solution has exactly one queen per row. I place them row by row, which means rows never need checking — the constraint is designed away rather than tested.

That reduces the problem from choosing n cells out of n² to choosing a column for each row.

For each candidate column I need to know whether the cell is attacked. The naive check scans every previously-placed queen — O(n), and it runs at every node of the search tree.

The improvement is encoding the diagonals arithmetically. Moving down-left keeps r + c constant, so that identifies one diagonal; moving down-right keeps r − c constant, so that identifies the other. I verified both on a 4×4 board — seven groups each, every group mutually diagonal.

So three sets — columns, r + c, r − c — answer 'is this cell attacked?' in O(1). Same pruning, but n times less work at every node.

Then it's the standard template: check, add to all three sets, recurse, remove from all three. Forgetting one removal over-constrains the search and silently returns too few solutions — the same failure mode as forgetting used[i] = false in Permutations.

One detail: r − c goes negative, which a HashSet<Integer> handles. For speed I'd use boolean[] with an offset of n − 1 to shift the range into [0, 2n−2].

O(n!) with O(1) checks, O(n) space. There's a bitmask version where the three sets become three integers and the diagonals shift by one as the row advances — faster, but harder to explain, and invisible at n <= 9."

Edge cases to volunteer:

Name n = 2 and n = 3. They're the cases with no solutions at all, where the search explores and returns empty — a solution that assumes at least one answer exists (or indexes into the result) breaks there.

7. Follow-Up Questions — Modified Constraints

⭐ "Return only the COUNT of solutions, not the boards."

LeetCode 52. Increment a counter instead of drawing — which removes the O(n²) board construction per solution. That's where the bitmask version really pays, since it's O(n!) with tiny constants and no allocation. For n = 15 (2,279,184 solutions) the board drawing would dominate entirely.

⭐ "Find just ONE solution rather than all."

Return a boolean up the recursion and short-circuit on the first success. Dramatically faster — for n = 8 it finds a solution after a few hundred nodes instead of exploring all 92. Worth noting that "all solutions" and "any solution" have very different practical costs even at the same asymptotic bound.

"Exploit the symmetry of the board."

Solutions come in symmetric families — reflections and rotations. You can search only the first half of row 0's columns and mirror the results, roughly halving the work. The bookkeeping for odd n (the middle column) is fiddly, and it changes the output order, so it's an optimisation to mention rather than default to.

"What if n were 15 or 20?"

n = 15 has 2.3 million solutions and is feasible with bitmasks; n = 20 has 39 billion and is not enumerable at all. Counting for large n is an active research area — there's no closed form, and the known values were computed with heavily optimised parallel search.

"Place other pieces — knights, or a mix?"

The attack pattern changes, so the encodings change. Knights don't move along lines, so there's no r ± c trick — you'd track attacked cells explicitly in a set. Worth noting that the diagonal encoding is specific to linear attack patterns, not a general technique.

"Add pre-placed queens that can't be moved."

Seed the three sets with their positions before starting, and skip those rows in the recursion. The template is unchanged, which is a good demonstration that the sets are the state — initialising them differently initialises the problem differently.