N-Queens
Place n queens on an n×n board so none attack each other; return all boards.
- 1 <= n <= 9
Intuition
N queens asks you to place n queens on an n×n board so that none attack each other, and to return every valid arrangement. A queen attacks along its row, its column, and both diagonals, so the constraint touches four directions at once.
The first simplification comes from counting. There are n queens and n rows, and two queens in the same row would attack each other — so exactly one queen goes in each row. That is forced, not chosen. Rows stop being a decision, and the only question per row is which column, cutting the search space from an enormous subset problem to n choices per row.
The second simplification is making the attack test cheap. Scanning the board for conflicts is O(n) per placement, but a queen's three threatened lines each have a constant identity:
- Column c; the ↗ diagonal, constant on r + c; and the ↘ diagonal, constant on r − c.
Keep three sets holding the occupied columns and diagonals, and a square is safe exactly when none of its three keys is present — an O(1) test. Add the keys when placing a queen, remove them when backtracking.
From there it is standard backtracking: try each column in the current row, recurse to the next row on success, and undo on the way back. Reaching row n means all n queens are placed safely, and the column choices can be rendered as a board.
Whenever backtracking spends its time asking "does this new piece conflict with anything placed so far?", look for a way to make that check O(1) with sets keyed on an invariant. Cells on the same anti-diagonal share r + c; cells on the same main diagonal share r - c. Encoding a constraint as an arithmetic identity turns a scan over the board into a hash lookup — the same idea makes sudoku solvers fast.
Approach
Before reading on: price up what the direct approach costs here, then ask what has to be undone after each choice so the next branch starts clean. Aim for O(n!) time and O(n) space.
Place exactly one queen per row
Since two queens cannot share a row, the assignment is one queen per row. This is forced by the problem, not a heuristic — it removes row conflicts entirely and reduces the branching factor to the n column choices.
Encode the three attack lines as keys
A square (r, c) is attacked if its column c, its ↗ diagonal r + c, or its ↘ diagonal r − c is already occupied. Both diagonal values are constant along their line, which is what turns the safety check into three set lookups instead of a board scan.
Test safety in O(1) with three sets
Maintain sets of used columns, used r + c values, and used r − c values. A square is safe when none of its three keys is in its set. This is what makes the solution fast enough for n = 12 or more, where a per-placement board scan would not be.
Place, recurse, then undo
Add all three keys and record the column, recurse into the next row, then remove the keys and the record. The removal is what lets the next column in this row be tried from a clean state — omitting it silently loses solutions rather than crashing.
Emit a board at row n
Reaching row n means every row holds a safely placed queen. Convert the list of column choices into the required board strings — row r gets a queen at its recorded column and dots elsewhere — and append it to the results.
Cost of the search
The upper bound is O(n!) since each row has at most n choices and constraints shrink the options for later rows, but pruning cuts the real search tree far below that. Space is O(n) for the recursion and the three sets, plus the output, which grows quickly — n = 8 has 92 solutions.
Solution & live demo
Common pitfalls
Scanning the board to test each placement
def safe(r, c):
for pr, pc in enumerate(place):
if pc == c or abs(pr - r) == abs(pc - c):
return False
return Trueif c in cols or r + c in diag1 or r - c in diag2:
continueCorrect, but it re-derives from scratch what could be remembered, making every placement O(n) instead of O(1). The set version encodes the same geometry as three constant-time membership tests.
Removing from only some sets when backtracking
backtrack(r + 1) cols.remove(c) place.pop()
backtrack(r + 1) cols.remove(c); diag1.remove(r + c); diag2.remove(r - c); place.pop()
Stale diagonal entries make later branches think squares are attacked when they aren't, so valid solutions get silently pruned and the count comes back short. Every set added to before the recursive call must be removed from after it.
Tracking both diagonals with the same key
if c in cols or r + c in diag1 or r + c in diag2:
if c in cols or r + c in diag1 or r - c in diag2:
r + c is constant along anti-diagonals and r - c along main diagonals — two different families. Using one key for both leaves an entire diagonal direction unguarded, and queens end up attacking each other along it.
Edge cases
Search exhausts with no output — correctly returns [].
Single queen on the single square: [["Q"]].