N-Queens
Place n queens on an n×n board so none attack each other; return all boards.
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.
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
python
▶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
Edge cases
n = 2 or 3
Search exhausts with no output — correctly returns [].
n = 1
Single queen on the single square: [["Q"]].
06
Complexity
Time
O(n!)
Space
O(n)
Branching shrinks each row; sets give O(1) checks.