The N-Queens Problem: Backtracking, Bitmasks, and Why Brute Force Never Stood a Chance

The Core Idea and the Invariant

A queen attacks along its row, column, and both diagonals. The task: place N queens on an N×N board so that no two attack each other. The first structural insight collapses the search space: since no two queens may share a row, every solution places exactly one queen per row. So a candidate solution is a function from rows to columns — an array pos[0..N-1] where pos[r] is the column of the queen in row r. Because no two share a column either, that array must be a permutation of 0..N-1.

That reduces the space from C(N², N) to N! permutations — for N = 8, from 4.4 billion down to 40,320. The remaining constraint is diagonals. Two queens at (r₁, c₁) and (r₂, c₂) share a diagonal iff r₁ + c₁ = r₂ + c₂ (anti-diagonal, ╱) or r₁ − c₁ = r₂ − c₂ (main diagonal, ╲). So the loop invariant maintained at every step of the search is:

• All placed queens occupy distinct columns,
• distinct values of r + c (distinct ╱ diagonals), and
• distinct values of r − c (distinct ╲ diagonals).

Backtracking builds a partial permutation row by row, extending only into columns that preserve this invariant, and abandons a branch the moment no legal column exists.

How Backtracking Works, Step by Step

The algorithm is a depth-first traversal of a search tree whose nodes are partial placements. At depth r we decide the column for the queen in row r:

• Try each column c from 0 to N−1 for row r.
• Check whether c is free of column, ╱, and ╲ conflicts against all rows placed so far.
• Place it (mark the column and both diagonals occupied) and recurse to row r+1.
• If the recursion returns without a full solution, undo the marks (backtrack) and try the next column.
• Base case: when r == N, all rows are placed — record a solution.

The key optimization is O(1) conflict checking using three boolean sets instead of scanning prior rows. Because r + c ∈ [0, 2N−2] and r − c ∈ [−(N−1), N−1], we index the anti-diagonal by r + c and the main diagonal by r − c + N − 1 to keep it non-negative:

solve(r, cols, diag1, diag2, pos):
  if r == N: record(pos); return
  for c in 0..N-1:
    d1 = r + c
    d2 = r - c + N - 1
    if c in cols or d1 in diag1 or d2 in diag2:
      continue                 # prune
    cols.add(c); diag1.add(d1); diag2.add(d2); pos[r]=c
    solve(r+1, cols, diag1, diag2, pos)
    cols.remove(c); diag1.remove(d1); diag2.remove(d2)  # undo

The prune line is where the billions vanish: if placing the first three queens blocks every column in row 3, the entire subtree beneath that partial board — which could be N! / (something) leaves — is never generated.

Complexity Analysis: Where O(N!) Comes From

Time. Ignore pruning for the upper bound. Row 0 has N column choices, row 1 has at most N−1 remaining columns (column-distinctness), row 2 at most N−2, and so on — giving O(N!) leaf explorations. Each leaf/node does O(1) work with the set-based conflict check (or O(N) with naive scanning, yielding a looser O(N · N!)). So the worst-case bound is O(N!), and this is essentially tight for enumerating all solutions because the number of nodes visited is Θ of the permutation tree that survives column pruning.

Pruning changes the constant, not the class. Diagonal pruning removes a large fraction of the N! permutation tree — empirically the branching factor is far below N — but no polynomial bound is known, and none is expected: counting N-Queens solutions is #P-hard-adjacent in difficulty, and the exact count is unknown beyond n = 27. The practical effect is dramatic: for N = 8 the pruned tree has ≈ 2,057 nodes versus 40,320 permutation leaves; for finding just the first solution, the cost is empirically near-linear for the tractable range.

• Space: O(N) for recursion depth plus O(N) for the three occupancy sets and pos array → Θ(N) total. Recording all solutions costs O(N · S) where S is the solution count.
• Solution count growth: 8→92, 10→724, 12→14,200, 15→2,279,184 — super-exponential, so enumerating everything is inherently expensive regardless of algorithm.

The Bitmask Trick: Making It Fly

The set operations can be replaced by bitwise arithmetic on machine integers, an optimization popularized by Rivin, Vardi, and Zimmermann and by competitive-programming folklore. Represent columns, ╱ diagonals, and ╲ diagonals each as a single integer whose set bits mark occupied lines. At each row, the available columns are computed in a few instructions:

solve(cols, d1, d2):        # bits set = occupied
  if cols == FULL: count++; return
  free = FULL & ~(cols | d1 | d2)
  while free:
    bit  = free & (-free)   # lowest set bit = pick a column
    free ^= bit
    solve(cols|bit, (d1|bit)<<1, (d2|bit)>>1)

Here free & (-free) isolates the lowest available column in one operation; shifting d1 left and d2 right each recursion automatically slides the diagonal masks to the next row (a queen's diagonal influence moves one file per rank). This eliminates the explicit r+c / r−c index math and array marking:

• State is three integers — no arrays to push/pop, so no memory traffic.
• Conflict detection, candidate generation, and the undo are all register operations.
• The lowest-set-bit iteration (free &= free − 1 to clear) visits exactly the legal columns, skipping conflicts without a per-column branch.

This is the workhorse behind record-setting counts: the n = 27 result (234,907,967,154,122,528 solutions) used a symmetry-reduced, FPGA-and-CPU bitmask search. On a laptop the bitmask version counts n = 15 in well under a second where the naive array version takes many times longer.

When to Reach for Backtracking (and When Not To)

Backtracking wins precisely when the problem is a constraint-satisfaction search whose constraints let you reject partial assignments early. N-Queens is the poster child: a single conflicting placement invalidates an exponential subtree. The same machinery solves Sudoku, graph coloring, the knight's tour, subset-sum/partition, crossword filling, and constraint solvers' core loops. The design questions are always: what is the partial state, what makes it invalid, and how cheaply can I detect invalidity?

• Use it when constraints prune hard and you need all solutions or a certified answer (SAT/CSP solvers are industrial backtracking with clause learning).
• Add heuristics for hard instances: minimum-remaining-values (place in the most-constrained row first) and forward checking / constraint propagation can cut the tree by orders of magnitude — this is how real Sudoku and scheduling solvers work.
• Don't use it to merely count N-Queens at large N — counting is intractable; use it to find a solution or enumerate small N.
• Prefer the closed form if you need only one solution: an explicit O(N) construction (Hoffman–Loessi–Moore, 1969, with cases on N mod 6) places all queens directly with no search at all.

Backtracking is a strategy, not a data structure — its speed lives entirely in the pruning predicate and the variable/value ordering.

Pitfalls, Edge Cases, and Variants

Small-N surprises. There are no solutions for N = 2 and N = 3 — a correct solver must return an empty set, not loop or error. N = 1 trivially has one solution. A frequent bug is assuming a solution always exists.

• Diagonal index off-by-one: forgetting the + (N−1) offset on r − c yields negative array indices and silent corruption. The valid ranges are r+c ∈ [0, 2N−2] and r−c+N−1 ∈ [0, 2N−2] — both need 2N−1 slots.
• Forgetting to undo: the backtrack step must clear exactly the column and two diagonals you set; leaking marks pollutes sibling branches and drops valid solutions.
• Symmetry double-counting: the board has 8 symmetries (4 rotations × reflection). The 92 solutions for N = 8 reduce to 12 fundamental ones; if you want distinct solutions you must canonicalize, and record counts differ by a factor of up to 8 (some solutions are self-symmetric, so it isn't a clean ÷8).
• Iterative version: the recursion can overflow the stack for large N in some languages; an explicit stack or the tail-shaped bitmask loop avoids it.

Variants worth knowing: counting (the OEIS A000170 sequence, still open past n = 27); the n-Queens completion problem — given a partial placement, can it be extended? — which was proven NP-complete (Gent, Jefferson, Nightingale, 2017), a sharp reminder that the general constrained version is genuinely hard; the toroidal (modular) queens; and peaceable/coexisting queens. Placing one solution is easy; completing an adversarial partial board is not.

Strategies for the N-Queens problem and their real costs

Approach	Idea	Time	Space	Finds
Brute force	Try all C(N²,N) placements	O(N²ᶜʰᵒᵒˢᵉ N)	O(N)	All, absurdly slow
Permutation search	One queen per row, check diagonals	O(N!)	O(N)	All solutions
Backtracking + pruning	DFS, prune on first conflict	O(N!) worst, far less in practice	O(N)	All / first
Bitmask backtracking	3 ints track col + 2 diagonals	O(N!) w/ tiny constant	O(N)	All / first
Explicit construction	Closed-form formula (n≥4)	O(N)	O(N)	One solution only