Q1 — DFS and BFS on a State Space
MoveGen table search — trace DFS and BFS to find a path from S to G.
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,B] |
| A | [C,D,S] |
| B | [D,G,S] |
| C | [A,B,G,S] |
| D | [A,B] |
| G | [A,B,C,D] |
Official answer (DFS): S,A,C,G
The Topic in 60 Seconds
- DFS uses a stack (LIFO): expand the most recently generated node.
- BFS uses a queue (FIFO): expand the oldest node first.
- "Inspect only new nodes" = a node generated once is never generated again.
Deep-dive: Depth First Search, Breadth First Search, MoveGen.
Step 0 — Read the table as directed moves
The table is asymmetric: C can generate S, but S never generates C — traversal must follow the row you expanded. Alphabetical-first expansion with a stack means pushing each MoveGen list in reverse, so the alphabetically-first child sits on top.
DFS working → S,A,C,G
| Step | STACK (top on the right) | Expand | MoveGen | New (push reversed) | Parents set |
|---|---|---|---|---|---|
| 1 | [S] | S | [A,B] | B, A → [B, A] | A←S, B←S |
| 2 | [B, A] | A (top) | [C,D,S] | D, C → [B, D, C] (S seen) | C←A, D←A |
| 3 | [B, D, C] | C (top) | [A,B,G,S] | G → [B, D, G] (A, B, S seen) | G←C |
| 4 | [B, D, G] | G — goal! | — | — | — |
Path reconstruction via parents: G ← C ← A ← S = S,A,C,G ✓
Bonus — the same table under BFS → S,B,G
The key records the DFS answer; for completeness, a queue sweeps differently:
| Step | QUEUE | Expand | New (append) |
|---|---|---|---|
| 1 | [S] | S | A, B → [A, B] |
| 2 | [A, B] | A | C, D → [B, C, D] |
| 3 | [B, C, D] | B | G (D, S seen) → goal |
G's parent is B, so BFS returns S,B,G — two edges instead of DFS's three. Same data, opposite container, shorter path.
Interactive DFS trace
Tricks & Tips
Answer: S,A,C,G