🧩
1. The Problem
Goal
Place 4 Queens on a \(4 \times 4\) chessboard such that no queen attacks another.
No two queens can share the same:
- Row
- Column
- Diagonal
Symmetry Insight: We only need to consider placing the first queen in the first two squares of the top row. The other two are symmetric reflections.
🌳
2. DP Formulation
We can formulate this as finding a path in a graph.
- • Root Node (s): Empty board.
- • Transitions: Placing a queen in the next row in a safe square.
- • Terminal Nodes: Either a full solution (4 queens) or a dead-end (cannot place next queen).
- • Cost: 0 for valid moves. 1 for arcs to artificial terminal node from dead-ends.
graph TD
S((Start)) --> Q1_1["Q at (1,1)"]
S --> Q1_2["Q at (1,2)"]
Q1_1 --> Q2_3["Q at (2,3)"]
Q1_1 --> Q2_4["Q at (2,4)"]
Q1_2 --> Q2_4_2["Q at (2,4)"]
Q2_4 --> Q3_2["Q at (3,2)"]
Q3_2 --> DeadEnd(("X"))
style DeadEnd fill:#fee2e2,stroke:#ef4444
style S fill:#dcfce7,stroke:#22c55e
📈
3. Complexity
The N-Queens Explosion
For \(N=4\), it's easy. But as \(N\) grows, the state space explodes.
N = 8
~16 Million
placements
N = 4
Small
manageable
For large \(N\), exact DP is impossible. We need Rollout or other search methods.
📝