1. One-Liner
N-Queens places queens row by row, backtracking whenever a column or diagonal conflict appears.
2. The Problem It Solves
On an N×N chessboard, place N queens such that no two share a row, column, or diagonal. Naive enumeration tries all N^N placements; you need a systematic search that prunes impossible partial boards early.
3. The Core Idea
Work one row at a time. For each row, try every column; if placing a queen is locally safe (no clash with queens above), commit and recurse to the next row. If no column works, undo the last placement and try the next option—classic depth-first trial with rollback.
4. How It Works (Step-by-Step)
| Step | What Happens |
|---|---|
| 1. State | Track queen column per row, or use sets for occupied cols/diagonals |
| 2. Base | If all N rows filled, record one valid arrangement |
| 3. Try column | For current row, test each column for attacks from above |
| 4. Recurse | If safe, place queen and go to row+1 |
| 5. Backtrack | Remove placement and try next column |
| 6. Pruning | Skip columns that violate row/col/diag constraints immediately |
5. Dry Run Example
N=4. Row 0: try col 0 → row 1: col 2 works → row 2: no safe col → backtrack row 1 to col 3 → eventually find [1,3,0,2] and [2,0,3,1] as solutions.
6. Key Properties
| Property | Value |
|---|---|
| Search type | DFS on implicit tree |
| Constraint check | O(N) per placement (naive) or O(1) with bitsets |
| Solutions | 0 for N=2,3; grows quickly with N |
7. Where It Is Used
| Domain | Use |
|---|---|
| Constraint satisfaction | Prototype for CSP and SAT-style thinking |
| Puzzles / games | Scheduling non-attacking pieces |
| Education | Standard backtracking interview pattern |
8. Interview Tips
Explain why row-by-row reduces symmetry, mention diagonals as r+c and r-c, and discuss count vs list all solutions. Optional: bitmask speedups for small N.
9. Comparison with Other Approaches
| Approach | Idea | Notes |
|---|---|---|
| Backtracking | DFS + prune | Standard, easy to code |
| Bitmask DP | Enumerate with bits | Faster for small N |
| Local search | Random repair | Not typical for interviews |
10. Complexity
| Metric | Value |
|---|---|
| Time | Worst-case roughly O(N!) in naive analysis; heavy pruning in practice |
| Space | O(N) for recursion stack and state |
Implementation Example (PYTHON)
def count_n_queens(n: int) -> int:
def is_safe(cols: list, row: int, col: int) -> bool:
for r in range(row):
if cols[r] == col or abs(cols[r] - col) == abs(r - row):
return False
return True
def dfs(row: int, cols: list) -> int:
if row == n:
return 1
total = 0
for col in range(n):
if is_safe(cols, row, col):
cols[row] = col
total += dfs(row + 1, cols)
return total
return dfs(0, [-1] * n)