N-Queens
Why it exists
Problem: Placing N non-attacking queens on an NxN chessboard. A naive generate-and-filter approach on an 8x8 board would evaluate '64 choose 8' (over 4.4 billion) combinations, which is computationally intractable.
Better idea: Enforce constraints intrinsically. Place queens row by row (since exactly one queen must occupy each row). Use O(1) set lookups to track attacked columns and diagonals, abandoning any invalid subtree the moment a threat is detected.
Mental model
Like filling out a Sudoku row by row, crossing out entire sections of possibilities as soon as a number is placed.
We process the board row by row. At each row, we try placing a queen in each column. If the cell isn't attacked, we place it, mark its column and both its diagonals as 'under attack', and recurse to the next row.
Repeated decision: In the current row, which column is safe to place a queen based on the three attack sets?
Explanation
N-Queens is the flagship backtracking problem because it demonstrates how profoundly pruning reduces a search space.
**1. Why row-by-row?**
Since queens attack horizontally, two queens can never share a row. Therefore, we MUST place exactly one queen per row. By making the recursion depth equal to the row index, we get the row constraint for free and shrink the search from 'combinations of 64 squares' to 'N branches per row, depth N'.
**2. The O(1) Attack Sets**
To place a queen at `(row, col)`, we must check if that cell is safe. Scanning the board takes O(N). Instead, we track three sets:
- `cols`: columns currently occupied.
- `diag1`: the primary diagonal. Notice that for any cell, `row - col` is constant along its top-left to bottom-right diagonal.
- `diag2`: the anti-diagonal. For any cell, `row + col` is constant along its top-right to bottom-left diagonal.
Checking safety becomes three O(1) set lookups.
**3. The Loop**
```python
for col in range(N):
if col in cols or (row - col) in diag1 or (row + col) in diag2:
continue
# Choose
cols.add(col); diag1.add(row-col); diag2.add(row+col)
board[row][col] = 'Q'
# Recurse
backtrack(row + 1)
# Un-choose
cols.remove(col); diag1.remove(row-col); diag2.remove(row+col)
board[row][col] = '.'
```
**4. Hand-Trace (4x4 Board)**
N=4 is the smallest solvable board (N=2 and N=3 have no solutions!).
- Row 0: Place Q at (0, 0).
- Row 1: Columns 0 and 1 are attacked. Place Q at (1, 2).
- Row 2: All columns 0, 1, 2, 3 are attacked! Dead end.
- Backtrack to Row 1, move Q to (1, 3).
- Row 2: Place Q at (2, 1).
- Row 3: All columns attacked. Dead end.
- Backtrack all the way to Row 0, move Q to (0, 1). This eventually finds a solution.
Key points
- Mathematical Coordinate Invariants: Any top-left to bottom-right diagonal shares a constant `row - col`. Any top-right to bottom-left diagonal shares a constant `row + col`.
Pattern: Constraint Satisfaction Backtracking
Recognition cues:
- Place N items on a grid
- Complex non-overlapping constraints
Failure signals
- Checking safety by rescanning the whole board.
- Recursion that never un-marks the attack sets.
Engineering examples
Constraint Satisfaction Solvers
Exam timetabling, register allocation in compilers, and Sudoku solvers.
N-Queens is the canonical constraint-satisfaction template, assigning values to variables subject to hard constraints via backtracking.
Common mistakes
- Scanning the board to check safety: Iterating through the board grid to check if a queen is threatened takes O(N) per cell. Using mathematical invariants (`row - col` and `row + col`) with hash sets brings this down to O(1).
- Confusing the two diagonal families: It's easy to mix up the math. Remember: `row - col` tracks the \ diagonal, and `row + col` tracks the / diagonal.
Recall questions
- Why does the N-Queens algorithm process the board row by row?
- How does the algorithm verify diagonal safety in O(1) time?
- What is the smallest N for which the N-Queens problem has a valid solution?
Questions & answers
Solve the N-Queens puzzle and return all distinct solutions.
Backtrack row by row. Use three sets: `cols`, `posDiag (r+c)`, `negDiag (r-c)`. For each col in row, if not in sets, add to sets, update board, backtrack to `row+1`, then remove from sets.
Approach: Row-by-row traversal with O(1) coordinate invariant tracking.
Is it possible to optimize the space complexity of the attack trackers?
Yes, by replacing the hash sets or boolean arrays with integer bitmasks. Using bitwise operations allows tracking column and diagonal availability with virtually zero allocation overhead.
Approach: Bitmasking for extreme constraint-satisfaction performance.
Continue learning
Previous: Backtracking template