TL;DR
Row-by-row backtracking with O(1) conflict checks via column/diagonal sets — O(n!) time, O(n) space beyond the output.
Approach 1 — Brute force: try every column permutation
Since a valid placement has exactly one queen per row and per column, every candidate is a permutation perm where the queen of row i sits in column perm position i. Generate all n! permutations and keep those with no diagonal conflict: queens in rows i and j clash diagonally iff abs(perm[i] - perm[j]) == i - j (for j < i).
from itertools import permutations
class Solution:
def solveNQueens(self, n: int) -> list[list[str]]:
res: list[list[str]] = []
for perm in permutations(range(n)):
ok = all(
abs(perm[i] - perm[j]) != i - j
for i in range(n)
for j in range(i)
)
if ok:
board = [
"." * col + "Q" + "." * (n - col - 1) for col in perm
]
res.append(board)
return res
Complexity: O(n! · n²) time (n! permutations, O(n²) pair check each), O(n) space beyond the output.
At n = 9 that is 362 880 permutations with a full 36-pair scan each — it survives only because the constraint stops at 9; the flaw is that it validates complete placements instead of abandoning a doomed prefix after its first conflict. (An even blunter brute force — choosing any n of the n² squares — is C(81, 9) ≈ 2.6 × 10^11 candidates, dead on arrival.)
Approach 2 — Backtracking with column and diagonal sets
The insight: prune at the earliest possible moment. Place queens row by row; before committing row r to column c, an O(1) test tells whether any earlier queen attacks it, because all cells of one ↘ diagonal share the value r - c and all cells of one ↙ anti-diagonal share r + c. Keep three hash sets — used columns, used r - c, used r + c — and a doomed prefix is cut off the moment it becomes doomed, never extended. This is classical backtracking: depth-first extension of a partial solution with undo on failure.
class Solution:
def solveNQueens(self, n: int) -> list[list[str]]:
res: list[list[str]] = []
cols: set[int] = set()
diag: set[int] = set() # r - c, the "\" diagonals
anti: set[int] = set() # r + c, the "/" diagonals
placement: list[int] = [] # placement of row r = its queen's column
def backtrack(r: int) -> None:
if r == n:
board = [
"." * c + "Q" + "." * (n - c - 1) for c in placement
]
res.append(board)
return
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)
placement.append(c)
backtrack(r + 1)
placement.pop()
cols.discard(c)
diag.discard(r - c)
anti.discard(r + c)
backtrack(0)
return res
Walkthrough on n = 4:
- Row 0 tries column 0. Sets: cols {0}, diag {0}, anti {0}.
- Row 1: c=0 (column), c=1 (diag: 1-1=0) blocked; c=2 free → place. anti gains 3.
- Row 2: c=1 blocked (anti 2+1=3), c=3 blocked (diag 2-3=-1, same as 1-2) — every column fails → backtrack row 1 to c=3.
- Row 2 now: c=1 free → place. Row 3: c=2 blocked (diag 3-2=1 = 2-1), everything else blocked → dead end. Unwind all of row 0 = 0.
- Row 0 tries c=1: row 1 → c=3, row 2 → c=0, row 3 → c=2:
r == 4, render [1,3,0,2] → .Q.. / ...Q / Q... / ..Q. ✓
- Symmetric search from row 0 c=2 yields
[2,0,3,1]; c=3 yields nothing new. Two boards total.
Complexity: O(n!) time — row r has at most n - r non-conflicting columns, and each placement/test is O(1); rendering adds O(n²) per solution found. O(n) space for the sets, path, and recursion.
Approach 3 — Bitmask backtracking
The insight: the three sets can be three integers, one bit per column. In row r, bit c of diag says “some earlier queen’s ↘ diagonal passes through column c of this row” — and moving down one row shifts every ↘ threat one column right (<< 1) and every ↙ threat one column left (>> 1). Free columns come from one AND/NOT, and x & -x peels candidates bit by bit. Same asymptotics, but each check is a few word-level ops — the standard trick when n-queens is the inner loop of something bigger.
class Solution:
def solveNQueens(self, n: int) -> list[list[str]]:
full = (1 << n) - 1
res: list[list[str]] = []
placement: list[int] = []
def backtrack(cols: int, diag: int, anti: int) -> None:
if cols == full:
board = [
"." * c + "Q" + "." * (n - c - 1) for c in placement
]
res.append(board)
return
free = full & ~(cols | diag | anti)
while free:
bit = free & -free # lowest free column
free ^= bit
placement.append(bit.bit_length() - 1)
backtrack(
cols | bit,
((diag | bit) << 1) & full,
(anti | bit) >> 1,
)
placement.pop()
backtrack(0, 0, 0)
return res
Walkthrough on n = 4, first solution: row 0 masks all zero → free = 1111. Taking bit 0010 (column 1): next call gets cols=0010, diag=0100 (shifted left: the ↘ threat now covers column 2 of row 1), anti=0001. Row 1 free = 1111 & ~0111 = 1000 → column 3 forced. Row 2 masks: cols 1010, diag ((0100|1000)<<1)&1111 = 1000, anti (0001|1000)>>1 = 0100 → free = 0001 → column 0 forced. Row 3 similarly forces column 2, cols reaches 1111 → emit [1,3,0,2], matching Approach 2.
Complexity: O(n!) time, O(n) space — same tree as Approach 2, cheaper constants.
Common pitfalls
- Only checking columns — diagonal conflicts are the whole difficulty;
abs(r1 - r2) == abs(c1 - c2) is the test people forget.
- Using
r + c for both diagonal directions — one direction needs r - c (or n - 1 + r - c if you index arrays); mixing them accepts illegal boards like queens at (0,0) and (1,1).
- Forgetting to undo all three sets plus the path on backtrack — a single missed
discard silently kills valid solutions further right in the tree.
- Rendering with a shared mutable row — build each row string independently; mutating one list of characters reused across rows aliases every board in the output.
Pattern takeaway
Constraint-satisfaction backtracking lives or dies on how early you can reject. Reformulate the choice so structural constraints are free (one queen per row ⇒ choose only a column), and encode the remaining constraints as O(1)-checkable summaries of the partial solution (c, r-c, r+c sets). The same recipe — pick the decision granularity, then design incremental conflict bookkeeping — powers Sudoku solvers, graph coloring, and exam scheduling.