N-Queens — The Classic Backtracking Interview Puzzle Decoded

Problem Statement#

LC 51 — N-Queens. Place n queens on an n x n chessboard so that no two queens attack each other. Return all distinct configurations as boards (each row is a string of length n made of Q and .).

LC 52 — N-Queens II. Same setup, but only return the COUNT of distinct solutions.

Constraints: 1 <= n <= 9 (LC 51), up to n = 9 for LC 52 too — but the bitmask version routinely solves n = 15 in under a second and powers research-grade enumeration.

Example:

Input:  n = 4
Output:
[[".Q..","...Q","Q...","..Q."],
 ["..Q.","Q...","...Q",".Q.."]]
 
Input:  n = 1  -> [["Q"]]
Input:  n = 2  -> []        (impossible)
Input:  n = 3  -> []        (impossible)

Why This Problem Matters#

N-Queens is the most cited backtracking tutorial in computer science, dating back to Carl Friedrich Gauss in 1850 and formalized as a backtracking exemplar by Niklaus Wirth in 1971. Top tier companies including Google, Meta, Microsoft, and Apple use it in interviews because solving it well requires four skills layered on top of each other: recursion, constraint formulation, pruning via shared state, and (for bonus points) bit manipulation.

Constraint satisfaction problems like Sudoku, graph coloring, register allocation, exam scheduling, and Boolean satisfiability all share the N-Queens template: enumerate decisions in a fixed order, propagate constraints to prune, and unwind on conflict. If you can write N-Queens in a clean 25 lines, you can write a Sudoku solver, a CSP framework, and a SAT prototype.

The bitmask version is also a favorite at competitive programming finals and FAANG senior screens because it shows you understand that a board state is really three integer bitsets and that "find lowest set bit" is one CPU instruction.

The Core Insight#

The decision tree is structured by ROW: place exactly one queen per row, deciding which column it occupies. This eliminates row conflicts by construction (each row gets exactly one queen) and lets you process rows in order, so a partial board after row r is described entirely by the columns chosen in rows 0 through r - 1.

Three constraint sets are then sufficient to detect attack:

• cols: occupied columns.
• diag1 (down-right diagonals): cells where row - col is constant. The value row - col uniquely identifies each NW-to-SE diagonal.
• diag2 (down-left diagonals): cells where row + col is constant — uniquely identifies each NE-to-SW diagonal.

When trying column c in row r, the placement is legal exactly when c is not in cols, r - c is not in diag1, and r + c is not in diag2. After placing, add to all three sets and recurse to row r + 1. On return, remove from all three (the choose / explore / unchoose triad).

The bitmask optimization replaces the three sets with three integers. Bit i of cols is set if column i is taken. The available-columns mask is computed in one expression: available = ~(cols | diag1 | diag2) and ((1 less-than-less-than n) - 1). The trick lowbit = available and -available extracts the lowest available column in one instruction, and the recursive call shifts diag1 left by 1 and diag2 right by 1 to slide diagonals as we descend rows. The result is a constant-factor speedup of 5x to 10x over set-based versions and the dominant approach in competitive programming.

Visual Dry Run#

n = 4. Rows fill top to bottom.

Row 0: try col 0 -> place (0,0)
  Row 1: col 0 blocked (cols), col 1 blocked (diag1), col 2 free
       -> place (1,2)
    Row 2: col 0 blocked, col 1 blocked, col 2 blocked, col 3 blocked
       -> dead end, backtrack
    Backtrack (1,2)
  Row 1: col 3 free -> place (1,3)
    Row 2: col 1 free -> place (2,1)
      Row 3: col 0 blocked, col 2 blocked, col 3 blocked
        -> dead end
    Backtrack (2,1)
    ...
Row 0: try col 1 -> place (0,1)
  Row 1: col 3 -> place (1,3)
    Row 2: col 0 -> place (2,0)
      Row 3: col 2 free -> RECORD board
            .Q..
            ...Q
            Q...
            ..Q.

A second symmetric solution is found starting from (0, 2). Final answer: 2 boards.

Solution (Optimal)#

Python — set-based, very readable#

def solveNQueens(n: int) -> list[list[str]]:
    result = []
    cols, diag1, diag2 = set(), set(), set()
    queens = [-1] * n  # queens[r] = column of the queen on row r
 
    def bt(r: int) -> None:
        # Base case: placed n queens (one per row) -> snapshot board
        if r == n:
            board = ['.' * q + 'Q' + '.' * (n - q - 1) for q in queens]
            result.append(board)
            return
 
        for c in range(n):
            # Three pruning checks: column, NW-SE diag, NE-SW diag
            if c in cols or (r - c) in diag1 or (r + c) in diag2:
                continue
            # Choose: mark all three constraint sets
            queens[r] = c
            cols.add(c); diag1.add(r - c); diag2.add(r + c)
            # Explore: place next row
            bt(r + 1)
            # Unchoose: undo for sibling branches
            cols.remove(c); diag1.remove(r - c); diag2.remove(r + c)
 
    bt(0)
    return result
 
 
# LC 52 — count only, no board materialization
def totalNQueens(n: int) -> int:
    count = 0
 
    def bt(r: int, cols: int, d1: int, d2: int) -> None:
        nonlocal count
        if r == n:
            count += 1
            return
        # available bits = positions where no constraint is active
        available = ((1 << n) - 1) & ~(cols | d1 | d2)
        while available:
            bit = available & -available  # extract lowest set bit
            available ^= bit
            # Recurse: diag1 shifts left, diag2 shifts right as we go down
            bt(r + 1, cols | bit, (d1 | bit) << 1, (d2 | bit) >> 1)
 
    bt(0, 0, 0, 0)
    return count

JavaScript#

function solveNQueens(n) {
    const result = [];
    const queens = new Array(n).fill(-1);
    const cols = new Set();
    const d1 = new Set();   // r - c
    const d2 = new Set();   // r + c
 
    function bt(r) {
        if (r === n) {
            const board = queens.map(q =>
                '.'.repeat(q) + 'Q' + '.'.repeat(n - q - 1)
            );
            result.push(board);
            return;
        }
        for (let c = 0; c < n; c++) {
            if (cols.has(c) || d1.has(r - c) || d2.has(r + c)) continue;
            queens[r] = c;
            cols.add(c); d1.add(r - c); d2.add(r + c);
            bt(r + 1);
            cols.delete(c); d1.delete(r - c); d2.delete(r + c);
        }
    }
    bt(0);
    return result;
}
 
// LC 52 — bitmask count
function totalNQueens(n) {
    const FULL = (1 << n) - 1;
    let count = 0;
    function bt(cols, dl, dr) {
        if (cols === FULL) { count++; return; }
        let avail = FULL & ~(cols | dl | dr);
        while (avail) {
            const bit = avail & -avail;
            avail ^= bit;
            bt(cols | bit, (dl | bit) << 1, (dr | bit) >> 1);
        }
    }
    bt(0, 0, 0);
    return count;
}

Complexity#

The branching factor at row r is at most n - r, so the upper bound on leaves is N!, but pruning shrinks the explored tree dramatically — for n = 14 only 365596 solutions exist out of 14! arrangements.

Common Mistakes#

1. Using abs(row - col) for diagonals. Two cells share a diagonal when EITHER r1 - c1 == r2 - c2 OR r1 + c1 == r2 + c2. The absolute-value form conflates them and misses attacks.
2. Iterating columns AND rows in the for-loop. Place by row only — the row index is the recursion depth. Iterating rows reintroduces row conflicts and slows you down.
3. Forgetting to remove from sets on backtrack. Without the unchoose step, sibling branches see phantom queens. This is the most common subtle bug — add a unit test that enumerates n = 4 and expects 2.
4. Returning before r == n. Some candidates record on every recursive call. Only record when ALL n queens are placed, never partway.
5. Mutable default board. Building the board string each time you record is fine; mutating a shared 2D grid and forgetting to reset characters loses the row information.
6. Off-by-one in bitmask shift. (d1 | bit) less-than-less-than 1 — the shift happens AFTER OR-ing, not before. Reversing this corrupts the diagonal tracking.

Interview Tips#

• Sketch the board on the whiteboard before coding. Draw the two diagonal families and label them with the r - c and r + c invariants — it sells the insight in 30 seconds.
• Default to the set-based version, then offer the bitmask version as a follow-up. "I would normally start here for clarity; if you want the optimized version I can show the bitmask trick." That single sentence hits two skill bars at once.
• Mention CSP terminology. Calling cols, diag1, diag2 "constraint propagation state" shows you have AI / OR background. Bonus points if you mention that arc consistency would be the next step in a SAT solver.
• Test on n = 4 aloud. Hand-trace the first solution [1, 3, 0, 2] to convince the interviewer your code is right.
• Discuss symmetry. Many follow-ups ask you to count only canonical solutions (12 for n = 8 instead of 92) by exploiting reflection / rotation symmetries.

Follow-up Questions#

• Generate ALL boards (LC 51) versus count only (LC 52) — LC 52 unlocks the bitmask path because there is nothing to materialize.
• N-Rooks problem — drop the diagonal constraints, just n! placements. Useful warmup.
• K-Queens variant — place at most k queens; record every legal partial. Slight base-case tweak.
• Symmetric N-Queens — count only fundamental solutions, divide-by-symmetry-group post-processing.
• Generalized constraint problems — Sudoku (LC 37), word search, graph coloring use the exact same backbone.

Key Takeaways#

• Place queens row by row to eliminate row attacks for free, then track three constraint sets: columns, r - c diagonals, r + c diagonals.
• Set-based code is the readable version; bitmask code is the fast version, and converting between them is purely mechanical.
• The bitmask trick available and -available extracts the lowest set bit in one operation and powers the fastest published N-Queens solvers.
• Pruning with shared state outside the recursive call is the foundation pattern for Sudoku, graph coloring, exam scheduling, and SAT.
• Always pair every set add with a corresponding remove on backtrack — the most common bug is a missing unchoose.
• N-Queens and the start-index pattern are the two backtracking templates every FAANG interviewer expects you to recognize on sight.