vault

N-Queens

17 min read

N-Queens

The N-Queens problem asks: place n chess queens on an n × n board so that no two queens attack each other (no two share a row, column, or diagonal). The original “eight queens” puzzle was posed by Max Bezzel in 1848 and has 92 solutions (12 unique up to symmetry). For general n, the count grows superexponentially — sequence OEIS A000170 — and exact counts are known up to n = 27 (computed in 2016 with massive parallelism). The problem is the canonical exemplar of backtracking with constraint propagation: assign one queen per row, prune any column already attacked, and recurse. With three boolean arrays tracking used columns, anti-diagonals (r + c), and main diagonals (r − c), each constraint check is O(1). A bitmask encoding makes the inner loop one word-AND instruction, and on modern hardware the n = 14 problem solves in milliseconds. The problem appears as LeetCode 51 (return all configurations) and LeetCode 52 (just count) and is the introductory case study for backtracking in CLRS, Knuth TAOCP Vol. 4A §7.2.2, and Russell-Norvig Ch. 6.

1. Intuition — One Queen Per Row, Skip Bad Columns

A queen attacks along its row, column, and both diagonals. So if we want n non-attacking queens on an n × n board:

  • They must be in n different rows. (If two were in the same row, they’d attack along that row.) So we may as well assign one queen to each row — row r gets the queen with index r.
  • The remaining decision is: in row r, which column does the queen go in?
  • The constraints are: that column hasn’t been used in any earlier row, AND no earlier queen is on the same diagonal.

Two diagonals matter: the anti-diagonal (top-left to bottom-right, where row + col is constant) and the main diagonal (top-right to bottom-left, where row − col is constant). If two queens have the same row + col, they share an anti-diagonal; if they have the same row − col, they share a main diagonal.

So: try each column c in row r. If c is unused and the diagonals r + c and r − c are both unused, place the queen and recurse to row r + 1. If we reach row n without conflicts, we have a valid arrangement — record it. On the way back up, undo the placement so the next iteration starts fresh.

The “constraint encoding” — three boolean arrays for columns / anti-diagonals / main-diagonals — is what makes this fast. Without it, every placement would scan up to O(n) to verify no attack — turning the algorithm from O(n!)-ish into O(n · n!)-ish per placement, much slower in practice.

2. Tiny Worked Example — n = 4

For n = 4, the only two solutions are:

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

(columns [1, 3, 0, 2] and [2, 0, 3, 1])

Let’s trace the backtracker on n = 4:

Row 0:
  try col=0:  cols={0}, diag1={0+0=0}, diag2={0-0+3=3}
    Row 1:
      try col=0: cols∋0, skip.
      try col=1: diag1={1+1=2}? not in {0}; diag2={1-1+3=3}? IN {3}, skip (attacks diagonal).
      try col=2: diag1={1+2=3}? not in {0}; diag2={1-2+3=2}? not in {3}. Place. cols={0,2}, diag1={0,3}, diag2={3,2}
        Row 2:
          try col=0: cols∋0, skip.
          try col=1: diag1={2+1=3}? IN {0,3}, skip.
          try col=2: cols∋2, skip.
          try col=3: diag1={2+3=5}? not in; diag2={2-3+3=2}? IN {3,2}, skip.
        all 4 cols fail → backtrack.
        Undo: cols={0}, diag1={0}, diag2={3}.
      try col=3: diag1={1+3=4}; diag2={1-3+3=1}. Place. cols={0,3}, diag1={0,4}, diag2={3,1}.
        Row 2:
          try col=0: cols∋0.
          try col=1: diag1={2+1=3}? not in; diag2={2-1+3=4}? not in. Place. cols={0,3,1}, diag1={0,4,3}, diag2={3,1,4}.
            Row 3:
              try col=0: cols∋0.
              try col=1: cols∋1.
              try col=2: diag1={3+2=5}? not in; diag2={3-2+3=4}? IN {3,1,4}, skip.
              try col=3: cols∋3.
            all fail → backtrack.
            Undo.
          try col=2: diag1={2+2=4}? IN {0,4}, skip.
          try col=3: cols∋3.
        backtrack. Undo.
      Undo (col=3).
    Undo (col=0).
  try col=1: cols={1}, diag1={1}, diag2={2}.
    Row 1:
      try col=3: diag1={1+3=4}; diag2={1-3+3=1}. Place. cols={1,3}, diag1={1,4}, diag2={2,1}.
        Row 2:
          try col=0: diag1={2+0=2}? not in; diag2={2-0+3=5}? not in. Place. cols={1,3,0}, diag1={1,4,2}, diag2={2,1,5}.
            Row 3:
              try col=2: diag1={3+2=5}? not in; diag2={3-2+3=4}? not in. Place. cols={1,3,0,2}.
              ✓ row 4 reached → record [1,3,0,2]
              Undo.
            Undo. (no more cols)
          Undo.
          ... etc.

Without expanding further: solution 1 is found via (0,1), (1,3), (2,0), (3,2). The trace shows pruning at work — most attempted (row, col) pairs fail constraint checks immediately and the search tree is exponentially smaller than 4⁴ = 256. The algorithm visits only a few dozen nodes before finding both solutions.

3. Pseudocode

3.1 Set-Based Constraint Encoding

solve_n_queens(n):
    results := []
    queens  := []                       # queens[r] = column of queen in row r
    cols    := empty set
    diag1   := empty set                # anti-diagonal: r + c constant
    diag2   := empty set                # main diagonal: r − c constant

    define backtrack(r):
        if r == n:
            results.append(render(queens, n))
            return
        for c := 0 to n − 1:
            if c in cols or (r + c) in diag1 or (r − c) in diag2:
                continue                            # PRUNE: attacks an existing queen
            cols.add(c); diag1.add(r + c); diag2.add(r − c)
            queens.append(c)
            backtrack(r + 1)
            queens.pop()
            cols.remove(c); diag1.remove(r + c); diag2.remove(r − c)

    backtrack(0)
    return results

The five Backtracking Framework primitives map exactly:

PrimitiveThis problem
is_solution(state)r == n (filled all rows)
choices(state)c in 0..n-1 (each column for the current row)
valid(choice)c not in cols and r+c not in diag1 and r-c not in diag2
apply(choice)add c to cols, r+c to diag1, r-c to diag2; push c onto queens
undo(choice)exact mirror of apply

The three sets together give O(1) constraint check (hash-set lookup) and O(1) apply/undo.

3.2 Bitmask Encoding (Faster)

For n ≤ 32 (or 64), the three sets fit in single integers and the constraint check is one bitwise-AND.

solve_n_queens_bitmask(n):
    results := []
    full := (1 << n) − 1                # all-bits mask

    define backtrack(r, queens, cols_mask, diag1_mask, diag2_mask):
        if r == n:
            results.append(render(queens, n))
            return
        # All squares attacked by existing queens in this row:
        attacked := cols_mask | diag1_mask | diag2_mask
        free     := full & ~attacked      # bit set for each free column

        while free != 0:
            c_bit := free & −free          # lowest set bit
            c     := bit_index(c_bit)
            free  ^= c_bit                 # mark as tried
            backtrack(
                r + 1, queens + [c],
                cols_mask  | c_bit,
                (diag1_mask | c_bit) << 1,    # diag1 shifts left by 1 per row
                (diag2_mask | c_bit) >> 1)    # diag2 shifts right by 1 per row

    backtrack(0, [], 0, 0, 0)
    return results

The diagonal trick is elegant: when we descend from row r to r + 1, every previously-set anti-diagonal “moves” one column to the right (on the next row). So we can encode diagonals positionally on the current row and just shift the mask by 1 each level. No need to track absolute r + c indices.

This is the bit-trick that makes counting solutions for n = 14 (365,596 solutions) take milliseconds.

4. Python Implementation

4.1 Set-Based Version (Clearest)

from typing import List
 
 
def solve_n_queens(n: int) -> List[List[str]]:
    """
    Return all distinct solutions to the n-queens puzzle.
    Each solution is a list of strings, where 'Q' marks a queen and '.' marks empty.
    """
    results: list[list[str]] = []
    queens: list[int] = []                       # queens[r] = column of queen in row r
    cols: set[int] = set()
    diag1: set[int] = set()                      # r + c (anti-diagonal)
    diag2: set[int] = set()                      # r - c (main diagonal)
 
    def backtrack(r: int) -> None:
        if r == n:
            results.append(_render(queens, n))
            return
        for c in range(n):
            if c in cols or (r + c) in diag1 or (r - c) in diag2:
                continue                          # prune: attacks an existing queen
            # apply
            cols.add(c)
            diag1.add(r + c)
            diag2.add(r - c)
            queens.append(c)
            # recurse
            backtrack(r + 1)
            # undo (mirror of apply)
            queens.pop()
            cols.remove(c)
            diag1.remove(r + c)
            diag2.remove(r - c)
 
    backtrack(0)
    return results
 
 
def _render(queens: list[int], n: int) -> list[str]:
    """Convert a list of column indices to the string-grid format LC expects."""
    rows = []
    for c in queens:
        rows.append('.' * c + 'Q' + '.' * (n - c - 1))
    return rows
 
 
def count_n_queens(n: int) -> int:
    """LeetCode 52: just count solutions, don't render them."""
    count = 0
    cols: set[int] = set()
    diag1: set[int] = set()
    diag2: set[int] = set()
 
    def backtrack(r: int) -> None:
        nonlocal count
        if r == n:
            count += 1
            return
        for c in range(n):
            if c in cols or (r + c) in diag1 or (r - c) in diag2:
                continue
            cols.add(c); diag1.add(r + c); diag2.add(r - c)
            backtrack(r + 1)
            cols.remove(c); diag1.remove(r + c); diag2.remove(r - c)
 
    backtrack(0)
    return count

4.2 Bitmask Version (Fastest)

def count_n_queens_fast(n: int) -> int:
    """
    Count solutions using bitmask encoding.
    Roughly 5-10x faster than the set-based version for n ≥ 10.
    """
    full = (1 << n) - 1
 
    def go(cols: int, d1: int, d2: int) -> int:
        if cols == full:
            return 1
        free = full & ~(cols | d1 | d2)
        total = 0
        while free:
            bit = free & -free                    # lowest set bit
            free ^= bit                           # remove from free
            total += go(
                cols | bit,
                (d1   | bit) << 1 & full,         # shift left, keep within board
                (d2   | bit) >> 1)
        return total
 
    return go(0, 0, 0)

The bitmask version is ~5-10× faster than the set version for n ≥ 10. For n = 14 (365,596 solutions) the bitmask version finishes in ~50 ms in pure Python; the set version takes ~500 ms.

5. Complexity

5.1 Worst Case

The unpruned search tree has n^n nodes (each row has n choices independently). With the “different column” prune alone, it shrinks to n! nodes (one queen per row, columns form a permutation). With diagonal pruning, the empirically observed tree is much smaller — for n = 8 only 2,057 nodes are visited (compare to 8! = 40,320 permutations, a ~20× pruning factor).

n# solutionsEmpirical search-tree nodes (set version)
4217
51041
64119
740469
8922,057
93529,945
1072453,973
1214,200~2,000,000
14365,596~46,000,000

(Counts of solutions from OEIS A000170; empirical node counts are approximate and depend on the implementation.)

5.2 Worst-Case Bound

The provable worst case is O(n!) time (the permutation bound), since with diagonal pruning the algorithm cannot exceed enumerating all n! row-column assignments. Per-node work is O(1) for set / bitmask operations, plus O(n) to render at the leaves. So total is O(n · n!) for the version that returns full configurations, O(n!) for the count-only version.

No tight closed-form for the pruned tree size

The “actually visited” tree size grows roughly as Θ(c^n) for some c < n, but no closed-form is known. Knuth (TAOCP Vol. 4A §7.2.2) discusses this as the canonical example of a backtracking algorithm whose runtime is “estimable but not provable in tight form.” Empirically, the number of valid configurations grows as roughly n! / c₁^n for some constant c₁ ≈ 2.5, but this is a conjecture not a theorem.

5.3 Space

Recursion depth is exactly n. The three sets (or bitmasks) collectively store at most n elements each. So auxiliary space is O(n) (excluding the output). The output for “return all configurations” is O(n²) per configuration × number of configurations.

6. Bitmask Optimisation — Why It Works

Encoding the three “is this column / diagonal attacked” sets as integers (bitmasks) gives several wins:

  1. O(1) constraint check is now one CPU instruction. cols | diag1 | diag2 followed by & full and ~. The whole “is column c attacked?” question is (attacked >> c) & 1. Single-cycle on modern CPUs.
  2. Diagonal shift trick. When the algorithm descends from row r to row r + 1, the “anti-diagonal” attack pattern moves one column to the right (because (r+1) + c = (r + (c-1)) + 1 + 1 — wait, that's not quite right. The actual identity: a queen at (r, c) blocks anti-diagonals at column c + (Δr) for future rows r + Δr. So when we increment the row, we should shift the diag1 mask left by one column. The (diag1 | c_bit) << 1 does this in one instruction. Symmetrically for diag2 >> 1.
  3. Iterating free columns: bit = free & -free extracts the lowest set bit. This is the Bit Manipulation Tricks for “find lowest set bit” — single cycle on modern CPUs (BLSI instruction). Then free ^= bit clears it. The iteration touches each free column exactly once, no for c in range(n) scan.

For n ≤ 64, the masks fit in a single uint64. For larger n, you’d need bignum or block-based representation. In practice, all interview-relevant n (≤ 30) fit easily.

7. Symmetry-Reduction Optimisation

The chessboard has 8-fold symmetry (4 rotations × 2 reflections). Of the 92 solutions for n = 8, only 12 are unique up to symmetry. So you can cut the search space by ~8× by fixing the first queen to a specific quarter of the board and expanding by symmetry afterwards.

The simplest symmetry break: in row 0, only place the queen in columns 0 .. ⌊n/2⌋. After finding all such solutions, mirror them. (This requires care: solutions that are self-symmetric under reflection should not be doubled.)

For competitive performance benchmarks (e.g., the famous “n = 27” record set in 2016 using GPU symmetry-reduced backtracking), this is a 4-8× speedup.

8. Comparison with O(n) Construction Heuristics

For finding any one solution (not all), there are explicit construction methods:

  • For n ≥ 4 and n mod 6 ∉ {2, 3}: queens at columns (2, 4, 6, ..., n, 1, 3, 5, ..., n-1) (even-then-odd) form a valid arrangement.
  • For n mod 6 = 2: a more elaborate pattern.
  • For n mod 6 = 3: another pattern.

These give O(n) solutions for “find one” but tell you nothing about the count or about all solutions — backtracking remains the algorithm of choice for those.

9. Diagram — The Constraint Encoding

flowchart TD
    Q["Queen at (r=2, c=3)"]
    Q --> ROW["Attacks row 2: same r"]
    Q --> COL["Attacks col 3: cols.add(3)"]
    Q --> D1["Attacks anti-diagonal: r+c=5: diag1.add(5)"]
    Q --> D2["Attacks main diagonal: r-c=-1: diag2.add(-1)"]
    ROW -.->|"unused: we place 1 queen per row"| INFO["row constraint is implicit"]

    Q2["Future queen at (r=4, c=6) — does it conflict?"]
    Q2 --> CHECK1["Same col? 6 in cols={3}? No"]
    Q2 --> CHECK2["Same anti-diag? 4+6=10 in diag1={5}? No"]
    Q2 --> CHECK3["Same main-diag? 4-6=-2 in diag2={-1}? No"]
    CHECK1 --> OK["all clear → place"]
    CHECK2 --> OK
    CHECK3 --> OK

    style Q fill:#fed
    style Q2 fill:#dfe
    style OK fill:#cfc

What this diagram shows. The top node is a queen placed at row 2, column 3. It attacks: its column (3), its anti-diagonal (where r + c = 5 is constant), and its main diagonal (where r − c = −1 is constant). The row attack is implicit because the algorithm places exactly one queen per row. The bottom subgraph illustrates how a future queen placement at (4, 6) is checked: three constant-time set-membership tests, one per attack direction. If all three checks pass, the queen can be placed and the constraint sets are extended. If any one fails, the algorithm immediately moves to the next column. This is the constraint-encoding insight that turns N-Queens from Θ(n^n) brute force into a tractable backtracking algorithm.

10. Pitfalls

  1. Forgetting to undo all three constraint sets. The most common bug. If apply modifies cols, diag1, diag2, then undo must reverse all three. Forgetting any one corrupts later branches and produces missing or extra “solutions”. Test on n = 4 (only 2 solutions) — anything else means the undo is broken.
  2. Using r + c for both diagonals. It’s r + c for one and r − c for the other. Reversing them or using only one (e.g., r + c for both) silently fails to detect attacks along one diagonal direction, producing many false positives. Easy to debug: n = 4 should give exactly 2 solutions, not more.
  3. Off-by-one in diagonal indices. If you use a fixed-size array instead of a hashset, indices are r + c ∈ [0, 2n−2] (size 2n−1) and r − c ∈ [−(n−1), n−1]. Common shift: r − c + (n − 1) to get a non-negative index. Forgetting the shift indexes negative, which Python handles by wrapping (set/list[-1]) — silently wrong.
  4. Recursing on r + 1 but checking r >= n instead of r == n. Equivalent for the base case but inconsistent — once r > n, you’ve gone too far. r == n is the canonical termination.
  5. Mutating queens instead of snapshotting at the leaf. results.append(queens) (without [:]) appends the reference to the shared list. By recursion’s end, queens is empty and every result aliases it. Use _render(queens, n) (which builds a new list) or queens[:].
  6. Using list.remove(c) instead of discard / index-based removal. list.remove(c) is O(n) and finds the first matching value — for a list, this is fine but wasteful. With a set, remove(c) is O(1) (hash). Confusion between data structures sneaks in.
  7. Not handling n = 0 or n = 1 correctly. n = 0 should return [[]] (one trivial solution: no queens). n = 1 should return [["Q"]]. n = 2 and n = 3 should return [] (no solutions).
  8. Counting solutions but recursing into solve_n_queens and discarding the output. That works but allocates a giant results list. For n ≥ 13, allocate-as-you-go for the count-only version (LC 52) is much faster.
  9. Bitmask version: forgetting & full after the left-shift. (diag1 | bit) << 1 can grow beyond n bits. The & full mask keeps the diagonal pattern within the board. Without it, “fake” attacks creep in from off-board positions and cause wrong answers for n ≥ 4.
  10. Treating it as “row-by-row” but using r from a closure. If you use a recursive helper with r as parameter (correct), you get clean recursion. If you store r in a closure variable and increment manually, the increment-then-undo dance must mirror the apply. Just use the parameter.
  11. Believing O(n!) is achievable in the worst case. It’s the bound; the actual visited tree is much smaller for moderate n thanks to pruning. But for any polynomial-time algorithm to exist would imply P = NP for the related “find a satisfying assignment” decision problem (which is harder); see Knuth’s discussion in TAOCP 4A.

11. Common Interview Problems

ProblemLeetCodeDifficultyNotes
N-Queens (return all configs)51HardThe classic; this note’s main subject
N-Queens II (count only)52HardSame algorithm; skip the rendering. Bitmask shines here
Place K Knights (variant)—MediumKnights’ attack pattern is more local; same backtracking schema
Place K Bishops Non-Attacking—MediumBishops only attack diagonals; can be split into “white squares” and “black squares” subproblems
Sudoku Solver37HardSibling backtracking; row/col/box constraints. See Sudoku Solver
Word Search79MediumDifferent state-space (grid path) but same backtracking schema. See Word Search
Combinations77MediumBacktracking-101. See Combinations
Permutations46MediumBacktracking-101. See Permutations

12. Open Questions

  • What’s the asymptotic growth rate of the number of solutions Q(n)? OEIS A000170 conjectures Q(n) ~ n! / c^n for some c ≈ e^{1.5}, but no proven closed form. Bell-Shanks 2009 give the best current upper bound.
  • Q27, the count for n = 27, was computed in 2016 via massively parallel backtracking on FPGAs. Q28 remains uncomputed as of 2026. What’s the practical limit with current hardware? c^n growth means each Δn = 1 is c ≈ 4.5× more work.
  • Constraint propagation: if you maintain “remaining legal columns per future row” and propagate when a queen is placed, can you prune more than just the diagonal/column check? AC-3 arc-consistency in CSP literature can shrink the tree but adds overhead. Practical win unclear for N-Queens specifically.
  • How does N-Queens generalise to m queens on an n × n board? The “can m queens be placed?” decision problem is NP-complete (Gent et al. 2017), so the search-time scaling is fundamentally exponential.

13. See Also

Graph View

Backlinks