Q1 — DFS and BFS on a State Space
MoveGen table search — trace DFS and BFS to find a path from S to G, inspecting only new nodes.
The Question
A MoveGen table defines the state space. S is the start, G is the goal. MoveGen returns nodes in table order. DFS and BFS inspect only new nodes.
| X | MoveGen(X) |
|---|---|
| S | [A, C] |
| A | [B, C, D, S] |
| B | [A, D, E] |
| C | [A, D, S] |
| D | [A, B, C, E, G] |
| E | [B, D, G] |
| G | [D, E] |
Official answer: S,A,B,E,G
The Topic in 60 Seconds
- DFS uses a stack (LIFO): dive deep, backtrack when stuck.
- BFS uses a queue (FIFO): explore level by level.
- "Inspect only new nodes" = don't re-expand already-visited nodes.
Deep-dive: Depth First Search, Breadth First Search, MoveGen.
DFS trace → S,A,B,E,G
DFS uses a stack (LIFO). Expand the most recently added node first.
| Step | Stack | Expand | MoveGen | Push (new only) | Parent |
|---|---|---|---|---|---|
| 1 | [S] | S | [A, C] | push C, A | A←S, C←S |
| 2 | [C, A] | A (top) | [B, C, D, S] | push D, B (C, S seen) | B←A, D←A |
| 3 | [C, D, B] | B (top) | [A, D, E] | push E (A, D seen) | E←B |
| 4 | [C, D, E] | E (top) | [B, D, G] | push G (B, D seen) | G←E |
| 5 | [C, D, G] | G — goal! |
Path (follow parents): G ← E ← B ← A ← S = S, A, B, E, G ✓
Bonus — the same table under BFS → S,A,D,G
The official key records the DFS answer above. If you re-run the table as a queue (FIFO), the frontier sweeps level by level:
| Step | QUEUE | Expand | New (append) |
|---|---|---|---|
| 1 | [S] | S | A, C → [A, C] |
| 2 | [A, C] | A | B, D → [C, B, D] |
| 3 | [C, B, D] | C | none (A, D, S seen) → [B, D] |
| 4 | [B, D] | B | E → [D, E] |
| 5 | [D, E] | D | G → goal |
Parents give G ← D ← A ← S = S,A,D,G — BFS finds the 3-edge route while DFS dives to the 4-edge one. Same MoveGen table, opposite data structure, different path.
Tricks & Tips
Answer: S,A,B,E,G