00 · Problem background
A search problem supplied as a crowded parking puzzle.
This project originated in Unit 4 of Peter Norvig's Udacity CS212 final exam. The supplied exercise described a square parking grid containing two- and three-space vehicles, walls, empty squares, a goal, and a designated car that must reach the exit.
The assignment also supplied important modeling constraints: cars move only along their orientation, one action may move a car several open spaces, a solution is an alternating path of states and actions, and the grid can be represented by indexed locations and tuples of objects with occupied positions.
01 · Problem
Movement rules create a graph.
Each arrangement of vehicles is a state. Moving one vehicle to another legal position creates an edge to a new state. The challenge is to reach an exit state without revisiting positions indefinitely—and preferably with the fewest moves.
02 · Approach
Model first, search second.
Encode the board
Represent vehicle orientation, length, and position in a stable puzzle state.
Generate successors
Produce only positions reachable through legal vehicle movement.
Search by layers
Use breadth-first exploration so the first discovered solution is a shortest path in move count.
03 · Lessons
The state representation controls the search.
- Canonical states prevent wasted work.A consistent representation makes visited-state detection reliable.
- Successor rules carry domain knowledge.The search algorithm is only useful when legal moves are generated accurately.
- Shortest path is a design choice.Breadth-first search fits unweighted moves but can become memory intensive.
04 · Future demonstration
Animate the solution path.
An interactive grid could accept a puzzle, animate the shortest solution, and expose explored-state and frontier-size metrics. That would make both the puzzle and the cost of breadth-first search visible.
Verification boundary: the origin is confirmed as Peter Norvig's Udacity CS212 final exam. The supplied puzzle and representation are distinguished here from the personal implementation. The historical script has not been executed or independently verified during this catalog project.