TL;DR
Row-by-row backtracking, counting leaves instead of rendering boards; bitmask state for speed — O(n!) time, O(n) space.
Approach 1 — Brute force: count valid column permutations
One queen per row and per column means every candidate is a permutation of columns; count the permutations with no diagonal clash (rows i and j clash iff their column gap equals i - j).
from itertools import permutations
def totalNQueens(n: int) -> int:
count = 0
for perm in permutations(range(n)):
if all(
abs(perm[i] - perm[j]) != i - j
for i in range(n)
for j in range(i)
):
count += 1
return count
Complexity: O(n! · n²) time, O(n) space.
At n = 9 this checks 362 880 complete permutations, most of which were already doomed by their first two rows — validating finished candidates instead of pruning prefixes is exactly the waste backtracking removes.
Approach 2 — Backtracking with conflict sets, counting only
The search tree is identical to N-Queens I: descend row by row, using an O(1) membership test per column with three sets — c for columns, r - c for ↘ diagonals, r + c for ↙ anti-diagonals. Because only the count matters, carry no path and build no boards; reaching row n contributes 1. Each placement is added, its subtree explored depth-first, then undone before trying the next column.
def totalNQueens(n: int) -> int:
cols: set[int] = set()
diag: set[int] = set() # r - c
anti: set[int] = set() # r + c
def backtrack(r: int) -> int:
if r == n:
return 1
total = 0
for c in range(n):
if c in cols or (r - c) in diag or (r + c) in anti:
continue
cols.add(c)
diag.add(r - c)
anti.add(r + c)
total += backtrack(r + 1)
cols.discard(c)
diag.discard(r - c)
anti.discard(r + c)
return total
return backtrack(0)
Walkthrough on n = 4:
- Row 0, c=0: row 1 admits only c=2 or c=3. Behind c=2, row 2 has no free column (c=1 hits anti
3, c=3 hits diag -1) → 0. Behind c=3, row 2 admits c=1, but then row 3 is fully blocked (c=2 hits diag 1) → 0. Subtree total 0.
- Row 0, c=1: row 1 → c=3 forced, row 2 → c=0 forced, row 3 → c=2 free → row index reaches 4 → +1.
- Row 0, c=2: the mirror of case 2 forces
[2,0,3,1] → +1.
- Row 0, c=3: mirror of case 1 → 0.
Answer: 2.
The recursion tree for n = 4 (each edge picks a column for the next row):
flowchart TD
R["Row 0"] --> A["c=0"]
R --> B["c=1"]
R --> C["c=2"]
R --> D["c=3"]
A --> A1["dead end (0)"]
B --> B1["Row 1: c=3"] --> B2["Row 2: c=0"] --> B3["Row 3: c=2 → +1"]
C --> C1["Row 1: c=0"] --> C2["Row 2: c=3"] --> C3["Row 3: c=1 → +1"]
D --> D1["dead end (0)"]
Complexity: O(n!) time (row r offers at most n - r viable columns; each test O(1)), O(n) space for sets and stack.
Approach 3 — Bitmask backtracking
Because no boards are output, the entire state compresses into three integers. Bit c of each mask means column c of the current row is threatened — by a queen’s column, its ↘ diagonal, or its ↙ diagonal. Descending one row slides ↘ threats one column right (<< 1) and ↙ threats one column left (>> 1), while column threats stay put. full & ~(cols | diag | anti) yields all free squares of the row at once, and free & -free (lowest set bit) enumerates them without scanning.
def totalNQueens(n: int) -> int:
full = (1 << n) - 1
def solve(cols: int, diag: int, anti: int) -> int:
if cols == full:
return 1
count = 0
free = full & ~(cols | diag | anti)
while free:
bit = free & -free
free ^= bit
count += solve(
cols | bit,
((diag | bit) << 1) & full,
(anti | bit) >> 1,
)
return count
return solve(0, 0, 0)
No undo step appears because the masks are passed by value down the recursion — each call gets its own copies, so unwinding the stack is the backtrack.
Walkthrough on n = 4, the counting branch from column 1 (masks written as 4 bits, column 0 = rightmost):
- Row 0 free =
1111; take 0010 (column 1). Child masks: cols 0010, diag 0100 (the ↘ threat has slid right for row 1), anti 0001.
- Row 1 free =
1111 & ~0111 = 1000 → column 3 forced. Child: cols 1010, diag 1000, anti 0100.
- Row 2 free =
0001 → column 0 forced. Child: cols 1011, diag 0010, anti 0010.
- Row 3 free =
0100 → column 2. Now cols = 1111 = full → return 1.
- The branch from column 2 mirrors this (+1); columns 0 and 3 bottom out at 0. Total 2.
Complexity: O(n!) time, O(n) stack — same tree as Approach 2 with word-level operations instead of hash sets; in practice several times faster, which matters since counting visits every solution.
Common pitfalls
- Masking mistakes after the shift —
diag << 1 grows past bit n-1; without & full the mask still works but silently accumulates garbage bits (and in fixed-width languages it overflows).
- Shifting both diagonal masks the same direction — ↘ and ↙ threats move opposite ways per row; same-direction shifts overcount (n=4 would give 4, not 2).
- Counting symmetric boards as one — rotations and reflections are distinct placements here; do not divide by 8.
- Memoizing on
(cols, diag, anti) — tempting, but states virtually never repeat across rows, so the cache only adds overhead.
Pattern takeaway
When a backtracking problem asks for a count rather than the solutions themselves, strip the state to the minimum that determines feasibility and return integers up the tree instead of appending to results. If that minimal state is a few small sets over a bounded universe, pack each into an integer bitmask — immutable mask-passing even deletes the undo step, since backtracking becomes plain stack unwinding.