p40 — N-Queens

Source: LeetCode 51 · Hard · Topics: Array, Backtracking Companies (2024–2025 frequency): Google (medium-high), Meta (medium), Amazon (medium), Microsoft (medium), Apple (low-medium) Loop position: classic Hard, often the algorithm round closer. Tests pure pattern execution — no clever insight, just disciplined backtracking with the right invariants.

1. Quick Context

Place N queens on an N×N board so no two attack each other. Return all distinct solutions.

The pattern: row-by-row placement. For each row, try each column; check that the column, the / diagonal (r+c), and the \ diagonal (r-c) are all unattacked. Recurse to next row. Backtrack on return.

def backtrack(r):
    if r == n:
        record(board); return
    for c in range(n):
        if c in cols or (r+c) in diag1 or (r-c) in diag2: continue
        choose(r, c); backtrack(r+1); un_choose(r, c)

Time: bounded by O(N!) — pruning is extremely aggressive in practice. For N=8 → 92 solutions; N=14 → 365596; the classic recursion-tree visualization. Space: O(N) recursion + O(N) per attacker set.

The discriminators:

1. Three attacker sets (cols, diag = r+c, anti_diag = r-c) — O(1) check.
2. Row-by-row recursion — eliminates the “queens-on-same-row” check entirely (one queen per row by construction).
3. Bitmask variant — three ints replace the three sets; ~3× faster.

2. LeetCode Link + Attempt Gate

🔗 https://leetcode.com/problems/n-queens/ (LC 51 — return boards) 🔗 https://leetcode.com/problems/n-queens-ii/ (LC 52 — count only)

STOP. 25-min timer.

3. Prerequisite Concepts

• Backtracking template (p36, p38).
• Set-membership invariants.
• For the bitmask variant: bitwise AND/OR/NOT, bit & -bit (lowest set bit), bits &= bits - 1 (clear lowest).

4. How to Approach (FRAMEWORK Steps 1–9)

Step 1 — Restate: “Place N non-attacking queens on N×N; return all solutions as a list of boards.”

Step 2 — Clarify:

• “How are solutions formatted?” (LC: list of list-of-strings, each string a row, ‘.’ empty, ‘Q’ queen.)
• “Are reflections/rotations distinct?” (LC: yes, all distinct placements.)
• “Bound on N?” (LC: N ≤ 9; pure brute is fine.)
• “Just count?” (That’s LC 52.)
• “Memory budget?” (LC 51 returns all boards — fine for N ≤ 9 since solutions ≤ 352.)

Step 3 — Constraints: N ≤ 9, solutions explode at ~O(N!) — N=8 gives 92, N=9 gives 352.

Step 4 — Examples:

• N=1 → [["Q"]].
• N=2 → [] (no solutions).
• N=3 → [].
• N=4 → 2 solutions.

Step 5 — Brute Force: Place queens in all N² choose N positions, check attacks. O(C(N², N) · N²) = death past N=4.

Step 6 — Complexity: With row-by-row + three-set pruning: bounded above by N! but practical runtime grows much slower. With bitmask: same big-O, smaller constants.

Step 7 — Pattern: Constraint-satisfaction backtracking. The three attacker invariants are the canonical example.

Step 8 — Develop: see solution.py.

Step 9 — Test: N=1, 2, 3, 4, 5, 8 (count = 92), 9 (count = 352).

5. Progressive Hints

If stuck for 5 min, open hints.md.

6. Deeper Insight — The three attacker invariants

6.1 Why row-by-row recursion

If you place row-by-row, you never have to check the row attacker — there’s exactly one queen per row by construction. This eliminates one constraint and one set, and structures the search neatly.

6.2 The three sets

cols       : set of columns already occupied
diag       : set of values r+c (the '/' diagonals — constant along this direction)
anti_diag  : set of values r-c (the '\' diagonals — constant along this direction)

A position (r, c) is safe iff c not in cols and (r+c) not in diag and (r-c) not in anti_diag.

Why these are correct:

• Two squares are on the same / diagonal iff r1 + c1 == r2 + c2. Proof: / runs from bottom-left to top-right; one step along it is (r-1, c+1), preserving r+c.
• Two squares are on the same \ diagonal iff r1 - c1 == r2 - c2. Proof: \ runs from top-left to bottom-right; one step is (r+1, c+1), preserving r-c.

Two queens on the same / or \ attack each other. Done.

6.3 The bitmask variant — O(N) → 3 int operations

For N ≤ 32, replace each set with a single int whose bits represent occupancy. The “is c safe in row r” check becomes:

occupied = cols_mask | (diag_mask >> r) | (anti_mask << r) ... (with proper shifts)

Cleaner formulation (from Knuth):

def solve(n):
    count = 0
    def rec(cols, diag, anti):
        nonlocal count
        if cols == (1 << n) - 1:
            count += 1; return
        free = ~(cols | diag | anti) & ((1 << n) - 1)
        while free:
            bit = free & -free          # lowest set bit
            free ^= bit                 # clear it
            rec(cols | bit, (diag | bit) << 1, (anti | bit) >> 1)
    rec(0, 0, 0)
    return count

The trick: shift diag left and anti right BETWEEN rows. The diagonals naturally propagate.

This is 2-3× faster than the set version. Fastest known classical N-Queens algorithm.

6.4 Iterative variants and why they don’t help here

For competitive search problems you sometimes convert recursion to an explicit stack. For N-Queens, recursion depth is N (≤ 9 in LC), so there’s no stack-overflow concern; iterative version offers no benefit.

6.5 Symmetry pruning

The board has reflection symmetry: any solution mirrored is also a solution. You can search only “first row column ≤ N/2” and double the count (subtracting the middle-column solutions for odd N). Cuts the search ~half.

LC 51 wants ALL distinct solutions — so apply symmetry to find canonical solutions, then expand by reflection. More code, ~2× speedup. Not usually worth it for N ≤ 9.

7. Anti-Pattern Analysis

1. Check by walking the board (for each placed queen, check row/col/diag distance). O(N) check per placement × N! placements. Slow + ugly + bug-prone vs the three-set O(1) check.
2. Use a 2D n×n “attacked” matrix and mark all attacked squares on placement. O(N) marks per placement, O(N) unmarks on backtrack. Wastes memory and time vs the three-set approach.
3. Recurse over (row, col) BOTH (for r, c in product(range(n), repeat=2)). Loses the “one queen per row” structure; explodes.
4. Off-by-one in diag/anti formulas. Use (r+c, r-c) — NOT (c-r) or (r+c, c-r). Verify with a 4×4 by hand.
5. Return shared list reference. Path is shared mutable state; must snapshot (e.g., result.append([row[:] for row in board]) OR build strings fresh).
6. Build board string by index manipulation each call. Cleaner: store queens[r] = c (a list of column indices); build board strings only on success.
7. For LC 52 (count only), build and discard full boards. Waste — increment a counter.
8. Bitmask version with wrong shift direction. diag << 1 vs diag >> 1 swaps the two diagonals; trace by hand on N=4.

8. Skills & Takeaways

• Three attacker invariants: cols, r+c, r-c.
• Row-by-row recursion structures the search and eliminates row-check.
• Bitmask variant with bit & -bit / bits ^= bit for hottest performance.
• Board reconstruction: store queens[r] = c, build strings only on success.
• Snapshot pattern for backtracking (deep copy on record).
• Symmetry pruning for theoretical halving.

9. When to Move On

Move on when:

• You can write the three-set version in under 12 min, bug-free.
• You can sketch the bitmask version in under 15 min.
• You explain WHY r+c and r-c characterize the two diagonals.
• N=8 gives 92 solutions (instant verification: total_n_queens(8) == 92).

10. Company Context

Google:

• Common in L4/L5 algorithm rounds. The interviewer expects the three-set version cleanly; bonus for bitmask.
• Scorecard phrase: “Algorithm — clean backtracking with the right invariants; articulated diagonal characterization.”

Meta:

• Less frequent than LC 79, but appears for L5 senior loops. Often paired with LC 52 follow-up.

Amazon:

• L5+. The bar raiser test: “now write LC 52 efficiently” → expects bitmask.

Microsoft:

• L63/L64. Sometimes asked as a system-design-adjacent: “extend to a rectangular board” (no formula change for rows × cols — same three sets).

Apple:

• Less common; appears in algo-research-heavy teams.

11. Interviewer’s Lens

12. Level Delta

Mid (L4):

• Three-set version works.
• Builds boards correctly with snapshot.
• Hand-verifies N=4 = 2 solutions.

Senior (L5):

• Articulates the three-set invariants cleanly.
• Stores queens[r] = c and constructs boards once.
• LC 52 with counter (no board build).

Staff (L6):

• Bitmask version.
• Discusses symmetry pruning.
• Connects to constraint satisfaction (SAT) and exact cover (dancing links).

Principal (L7+):

• Discusses production: schedule/seating optimization, FPGA placement, classroom assignment — N-Queens as a constraint-satisfaction archetype.
• Discusses parallel search: sharding first-row choices across workers.
• Discusses DLX (Dancing Links / Algorithm X) for solving general exact-cover problems including N-Queens.
• Discusses probabilistic / Las Vegas algorithms for large-N: Min-Conflicts heuristic solves N=1,000,000 in seconds (with restarts), whereas backtracking falls over past N=30.

13. Follow-up Q&A

Q1: LC 52 — just count. A: Same recursion, replace result.append(board) with count += 1. Don’t build boards. Bitmask version is fastest.

Q2: Why r+c and r-c? A: A / diagonal (bottom-left to top-right) has constant r+c (one step is (-1, +1)). A \ diagonal (top-left to bottom-right) has constant r-c (one step is (+1, +1)). Two queens attack along a diagonal iff they share r+c or r-c.

Q3: Solve N=1,000,000? A: Backtracking dies past N≈30. Use Min-Conflicts: random initial placement (one queen per row), repeatedly move the most-conflicted queen to its least-conflicting column, restart on local minimum. Solves N=10^6 in seconds. Las Vegas (random restarts), not deterministic.

Q4: Generalize to K-attackers (king/rook/bishop mix)? A: Replace the attacker check with a generalized “any piece attacks this square?” Each piece type contributes its own set/mask; otherwise structure is identical.

Q5: Track only “fundamentally distinct” solutions (modulo D₄ symmetry)? A: Generate all solutions, canonicalize each (e.g., apply all 8 symmetries and take min), dedupe. For N=8: 92 → 12 fundamental solutions.

14. Solution Walkthrough

See solution.py:

• solve_n_queens(n) — three-set backtracking; returns boards.
• total_n_queens(n) — LC 52 count-only with three sets.
• solve_n_queens_bitmask(n) — bitmask version; returns count (fastest).
• solve_n_queens_brute(n) — exhaustive C(N², N) for tiny N (oracle).

Run: python3 solution.py.

15. Beyond the Problem

Principal-engineer code review comment:

“Three things. (1) The bitmask version is gorgeous but make sure your reader understands the shift direction — leave a worked 4×4 trace in the comments because future-you will not remember why diag << 1 vs >>. (2) For LC 52 we’re calling this fresh each time; consider memoizing on (row, cols_mask, diag_mask, anti_mask) — BUT note that anti/diag masks vary per row, so the key space is huge and the cache won’t pay off. The classical result is that N-Queens has no known good DP because the state-space lacks reusable subproblems; this is a teachable moment in the docstring. (3) For production solver applications (seating, scheduling), don’t write a custom backtracker — use an SMT solver (Z3) or a CSP library (OR-Tools). Hand-rolled backtracking is the algorithmic exercise; mature CSP solvers crush it on real workloads with conflict-driven clause learning, restart heuristics, and parallel search.”

Connections forward:

• p36, p37, p38, p39 — backtracking siblings.
• Constraint satisfaction (CSP) — N-Queens is the textbook example.
• SAT solvers — N-Queens encodable in propositional logic.
• Dancing Links (Knuth’s Algorithm X) — exact cover formulation.
• Min-Conflicts heuristic — local-search alternative.
• Production: classroom/exam seating, FPGA placement, frequency assignment, scheduling.