LeetCode #51 Hard

N-Queens

Place n queens on an n×n board so none attack each other; return all boards.

backtracking

02

Intuition

One queen per row is forced, so search row by row: the only question per row is which column. Three sets — columns, ↗ diagonals (r+c), ↘ diagonals (r−c) — make the attack check O(1). Dead rows trigger backtracking.

How to spot this pattern

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.

03

Approach

1

Row-by-row placement

Placing per row eliminates row conflicts by construction; the branching factor is columns only.

2

O(1) safety via three sets

A square (r,c) is attacked iff c, r+c, or r−c is occupied. Add on place, remove on backtrack.

3

Emit at row n

Reaching row n means n non-attacking queens — render the board from the column choices.

04

Solution & live demo

▶1class Solution:
▶2    def solveNQueens(self, n):
▶3        res, cols, diag1, diag2, place = [], set(), set(), set(), []
▶4        def backtrack(r):
▶5            if r == n:
▶6                res.append(["." * c + "Q" + "." * (n - c - 1) for c in place])
▶7                return
▶8            for c in range(n):
▶9                if c in cols or r + c in diag1 or r - c in diag2:
▶10                    continue
▶11                cols.add(c); diag1.add(r + c); diag2.add(r - c); place.append(c)
▶12                backtrack(r + 1)
▶13                cols.remove(c); diag1.remove(r + c); diag2.remove(r - c); place.pop()
▶14        backtrack(0)
▶15        return res

05

Common pitfalls

Scanning the board to test each placement

✗ Wrong

def safe(r, c):
    for pr, pc in enumerate(place):
        if pc == c or abs(pr - r) == abs(pc - c):
            return False
    return True

✓ Right

if c in cols or r + c in diag1 or r - c in diag2:
    continue

Correct, 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

✗ Wrong

backtrack(r + 1)
cols.remove(c)
place.pop()

✓ Right

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

✗ Wrong

if c in cols or r + c in diag1 or r + c in diag2:

✓ Right

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.

06

Edge cases

n = 2 or 3

Search exhausts with no output — correctly returns [].

n = 1

Single queen on the single square: [["Q"]].

07

Complexity

Time

O(n!)

Space

O(n)

Branching shrinks each row; sets give O(1) checks.