From-scratch build · single-agent reasoning
Strip a puzzle down to its essence — a set of states, the moves between them, and a goal — and "solving it" becomes "searching cleverly." This project models that in plain Python: a clean problem interface, two concrete puzzles, and four search algorithms (BFS, uniform-cost, A*, IDA*) that all find the optimal answer but differ wildly in how much work they do. The headline is the efficiency gap a good heuristic buys you.
What it is
A problem is four things: an initial state, a goal test, a successor function (the legal moves), and a step cost. Any domain that implements that interface can be handed to any search algorithm. Solving the puzzle is finding a least-cost path to a goal state — the same act whether you're planning a route or sliding tiles.
Doing it from scratch makes the trade-offs concrete. Breadth-first guarantees the shortest path but explores almost everything. A* uses a heuristic to head toward the goal — and if the heuristic never overestimates (it's admissible), the path it returns is still optimal, but it expands a tiny fraction of the nodes.
The build
3×3 sliding-tile puzzle (any N×N). Inversion-parity solvability test and a k-move scrambler with a known optimal-length bound.
River-crossing constraint puzzle; the classic 3M/3C/boat-2 instance has a known optimum of 11 crossings.
Breadth-first (shortest path on equal costs) and uniform-cost / Dijkstra (optimal for any non-negative cost).
Best-first on f = g + h, and iterative-deepening A* with memory linear in depth. Same optimal cost, far fewer nodes.
Both admissible; Manhattan dominates misplaced-tiles, so A* with it expands no more nodes — usually many fewer.
The suite computes the true optimal cost-to-go and asserts the heuristic never exceeds it on sampled states.
The point
Output from demo.py. All four algorithms return the same optimal cost; only the nodes expanded differ.
| algorithm | cost | nodes expanded |
|---|---|---|
| BFS | 23 | 80,439 |
| UCS | 23 | 119,498 |
| A* | 23 | 1,193 |
| IDA* | 23 | 784 |
A* with the Manhattan heuristic expands 67× fewer nodes than BFS for the identical optimal solution; IDA* fewer still. On a lighter 18-move scramble (optimal 12) the gap is 821 → 33, about 25×. Missionaries & cannibals is tiny — all four agree on the 11-crossing plan, BFS expanding 13 nodes.
Try it
The real solver is the Python package in this repo. This is a faithful JavaScript re-implementation of the same algorithms on the same puzzle, so you can watch the node counts diverge live. Scramble the board, pick an algorithm, and solve.
Reflection