BacktrackingAlgorithmaka eight queens, queens puzzle

N-Queens

Place n queens on an n×n board so none attack each other, by filling one row at a time and pruning columns and diagonals already under attack.

▶ VisualizePattern: BacktrackingPractice (2)
Progress

Overview

N-Queens is the canonical constraint-satisfaction backtracking problem. Queens attack along rows, columns, and both diagonals. Because exactly one queen must sit in each row, the search places a queen in row 0, then row 1, and so on; the only decision per row is the column.

Three boolean arrays (or bitmasks) make the attack check O(1): cols[c], diag1[r − c + n − 1] (↘ diagonals have constant r − c), and diag2[r + c] (↙ diagonals have constant r + c). A row is never re-checked because the row index is the recursion depth.

backtrackingconstraint satisfactionpruningdiagonalsbitmask

Intuition

A mental model before the formal terms.

Walk down the board row by row, sliding a queen along each row until it lands on a square nobody attacks. If a row has no safe square, the previous queen must move — you go back up one row and slide it further right.

Every ↘ diagonal is a line where row − col stays the same; every ↙ diagonal keeps row + col constant. So "is this diagonal taken?" is one array lookup, not a scan of the board.

How it works

  1. State: queens[row] = col for placed rows, plus cols, diag1, diag2 occupancy sets.
  2. Base case: row == n — every row has a queen; record the board.
  3. For each col in 0..n-1: if cols[col], diag1[row−col+n−1], or diag2[row+col] is taken, skip (prune).
  4. Otherwise mark all three, set queens[row] = col, recurse with row + 1, then unmark all three.
  5. Bitmask version: cols, d1, d2 are integers; available squares are ~(cols | d1 | d2) & fullMask; shifting d1 << 1 and d2 >> 1 when moving to the next row keeps them aligned.

Why it works

Any valid solution has exactly one queen per row (n queens, n rows, no shared row), so restricting to one-queen-per-row loses nothing.

Attack constraints are monotone: a conflict between two placed queens cannot be undone by placing more queens, so pruning on the first conflict is safe.

The three arrays exactly encode the four attack lines (row is implicit), so the O(1) check is equivalent to scanning all previously placed queens.

Recognition

How to tell a problem wants this.

  • Placing items on a grid subject to pairwise "cannot share a line" constraints.
  • n ≤ 9..14 and the output is all valid boards or their count.
  • Any "assign one value per row/slot with conflict rules" problem — the same skeleton solves graph coloring and Sudoku Solver.
“all combinations” → Backtracking

Interactive visualization

Play, step, change the input. ← → and space work too.

Solutions (0)
empty
1/25Place 5 queens on a 5×5 board so none share a row, column or diagonal. One queen per row, tried column by column.
QueenAttacked by a queenRow being tried / queen removedSolution
PseudocodeLearn N-Queens →
1solve(row):
2  if row == n: record(board); return
3  for col in 0 .. n-1:
4    if attacked(row, col): continue
5    place(row, col)
6    solve(row + 1)
7    remove(row, col)        // backtrack
Variables
n5
Complexity
worst O(n!)
space O(n)
Speed

Pseudocode

1solve(row):
2  if row == n: record(queens); return
3  for col in 0..n-1:
4    if cols[col] or d1[row-col+n-1] or d2[row+col]: continue
5    place(row, col)   # mark cols, d1, d2; queens[row] = col
6    solve(row + 1)
7    remove(row, col)  # unmark
8solve(0)

Implementations

1def solve_n_queens(n: int) -> list[list[str]]:
21 · Attack-line bookkeeping arrays
3    cols = [False] * n
4    d1 = [False] * (2 * n - 1)   # row - col + n - 1
5    d2 = [False] * (2 * n - 1)   # row + col
6    queens = [-1] * n
7    out: list[list[str]] = []
8 
9    def solve(row: int) -> None:
102 · Base case: build the board
11        if row == n:
12            out.append(["." * c + "Q" + "." * (n - c - 1) for c in queens])
13            return
14        for col in range(n):
15            a, b = row - col + n - 1, row + col
163 · Prune attacked squares
17            if cols[col] or d1[a] or d2[b]:
18                continue
194 · Place / recurse / remove
20            cols[col] = d1[a] = d2[b] = True
21            queens[row] = col
22            solve(row + 1)
23            cols[col] = d1[a] = d2[b] = False
24 
25    solve(0)
26    return out
27 
28 
295 · Bitmask counter (solutions only)
30def count_n_queens(n: int) -> int:
31    full = (1 << n) - 1
32 
33    def go(cols: int, d1: int, d2: int) -> int:
34        if cols == full:
35            return 1
36        total = 0
37        avail = full & ~(cols | d1 | d2)
38        while avail:
39            bit = avail & -avail             # lowest set bit
40            avail ^= bit
41            total += go(cols | bit, (d1 | bit) << 1 & full, (d2 | bit) >> 1)
42        return total
43 
44    return go(0, 0, 0)
Walkthrough
  1. [False] * (2 * n - 1) allocates each diagonal marker list; queens stores the column per row.
  2. The board is rendered with a list comprehension only when row == n.
  3. The prune if cols[col] or d1[a] or d2[b]: continue is O(1) per square.
  4. Chained assignment cols[col] = d1[a] = d2[b] = True assigns the same value to all three targets.
  5. The bitmask counter relies on Python ints being unbounded, so & full is needed to drop bits shifted past n.
Complexity (this implementation)
time O(n!) worst case with pruning · space O(n) recursion depth plus O(n^2) per stored board

The bitmask version is several times faster in CPython because it avoids list indexing.

Language notes
  • Python has no fixed-width ints, so avail & -avail works for any n, but masks grow unless masked with full.
  • Sets (set() of used columns/diagonals) are a readable alternative to boolean lists with similar speed.
  • Depth n recursion is far below the default limit.
Common mistakes in this language
  • Appending queens (the shared list) to results instead of rendering it or copying it.
  • Forgetting the + n - 1 offset for the anti-diagonal.
  • Omitting & full in the bitmask variant so the left-shifted diagonal keeps growing.
Language differences that matter here
  • Bitmask limits: C++ int and JS/TS bitwise ops are 32-bit (n <= 30 practical); Python ints are unbounded, so & full is what keeps masks small, not a hard limit.
  • C++ groups state in a class; the others use closures over local arrays.
  • C++ vector<bool> is bit-packed with proxy references; the chained assignment still works but bool& bindings do not.

Complexity

Best
—
Average
—
Worst
O(n!)
Space
O(n)

Upper bound: row r has at most n − r safe columns. In practice pruning makes it far faster; n = 8 has 92 solutions and visits about 2,000 nodes. Building each output board costs O(n²).

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • Constraint satisfaction with one decision per row/slot and cheap conflict checks.
  • Counting or listing all solutions for n ≤ 14; the bitmask variant handles n = 15..16 in seconds.
Avoid it when
  • You only need one solution for large n — an explicit construction places n queens in O(n) for every n ≥ 4.
  • Constraints are not monotone (a conflict can be fixed by later moves) — then pruning is unsound and you need a different search.

Alternatives

Recursion & BacktrackingPermutationsBitmask DP

Common mistakes

  • Using row − col directly as an index without the + n − 1 offset (negative index).
  • Checking the column but forgetting one of the two diagonal families.
  • Mutating a shared board array and pushing it into results without copying.
  • Restoring only some of the marks on the way back (e.g. cols but not d1).

Interview patterns

  • N-Queens I (list boards) and II (count only, ideal for the bitmask version).
  • Same skeleton for graph coloring, Latin squares, and knight/bishop placement variants.
  • Ask which constraints are monotone before choosing the prune — the interviewer wants to hear the soundness argument.
Interview questions on this
Mock interviews

Example problems

N-QueenshardSudoku Solverhard