An optimal 8-puzzle solver comparing two admissible heuristics: Manhattan distance, and a pair of disjoint additive pattern databases. Pure Python plus NumPy.
git clone https://github.com/<user>/eight-puzzle-astar.git
cd eight-puzzle-astar
pip install numpy
python benchmark.py
A* returns an optimal path whenever the heuristic never overestimates the true remaining cost. Both heuristics here satisfy that, so both find the same optimal cost — the interesting question is how many nodes each one has to generate on the way.
Manhattan distance sums, over the eight tiles, the grid distance from where a tile is to where it belongs. It is admissible because one move shifts one tile by one square, so no move can reduce the sum by more than 1. The blank is excluded: it moves on every step, so counting it would overestimate.
Pattern databases trade memory for a sharper bound. Split the tiles into two groups, {1,2,3,4} and {5,6,7,8}. For each group, enumerate every arrangement of those four tiles over the nine squares and record, by breadth-first search backwards from the goal, the minimum number of moves of those tiles needed to get home. That is 9·8·7·6 = 3,024 entries per group, small enough to hold entirely in a dictionary.
Two properties make the sum of the two tables usable as a heuristic:
Admissibility. In the abstraction, a pattern tile may slide to any adjacent square not held by another pattern tile, and the blank is ignored. Every real move of a pattern tile moves it into the blank square, which is never held by a pattern tile, so every real solution maps onto a legal sequence in the abstraction. The abstract cost is therefore a lower bound.
Additivity. The two groups are disjoint and each table charges only
moves of its own tiles, so no move is counted twice and h₁ + h₂ stays
admissible. This is the part that is easy to get wrong: summing overlapping
databases, or databases that charge blank moves, produces a heuristic that
overestimates and an A* that quietly returns non-optimal paths.
benchmark.py, measured on the three course samples:
| State | Optimal cost | Nodes, Manhattan | Nodes, PDB | Reduction | EBF Manhattan | EBF PDB |
|---|---|---|---|---|---|---|
| Sample 1 | 11 | 49 | 30 | 38.8% | 1.2340 | 1.1555 |
| Sample 2 | 24 | 3,230 | 1,285 | 60.2% | 1.3201 | 1.2623 |
| Sample 3 | 21 | 352 | 239 | 32.1% | 1.2191 | 1.1908 |
Three hand-picked states are a weak sample, so the harness also runs random ones. Over 300 uniformly random solvable states (seed 0, mean optimal cost 21.9):
| Heuristic | Mean nodes generated |
|---|---|
| Manhattan | 2,516 |
| Pattern databases | 1,473 |
41.4% fewer nodes, and the pattern databases were never worse than Manhattan on any of the 300 states. That last point is worth stating carefully: disjoint PDBs are not guaranteed to dominate Manhattan on every state, so "never worse across 300 samples" is an empirical observation about this partition, not a theorem.
Reproduce:
python benchmark.py # the three samples
python benchmark.py --random 300 --seed 0The effective branching factor is the b solving N = 1 + b + b² + … + b^d for N nodes generated at solution depth d — the branching factor a uniform tree would need to hold the same number of nodes. It normalises for depth, which raw node counts do not: a deeper solution generates more nodes even with an identical heuristic, so comparing node counts across states of different depth is misleading and comparing EBF is not.
src/
puzzle.py state, moves, solvability parity, Manhattan distance
pdb.py pattern database construction and the additive heuristic
solver.py A* and the effective branching factor
generate_pdb.py builds patterns.pkl
benchmark.py runs the comparison
tests/ 18 tests
patterns.pkl is not committed. It is a generated artifact, it rebuilds in
about 10 ms, and an unpickle executes whatever the file says — nobody should
download a stranger's pickle. The solver builds the tables in memory if the
file is missing, so nothing breaks on a fresh clone.
python -m unittest discover -s tests -t .The suite checks the properties the correctness argument rests on, not just that the code runs:
- Admissibility — over random states, neither heuristic exceeds the true optimal cost found by A*.
- Agreement — both heuristics return the same optimal cost on the same state. If one were inadmissible, this is where it would show.
- Paths are real — every returned solution is replayed move by move and must land on the goal, with length equal to the reported cost.
- BFS depths are minimal — every arrangement in a table sits one step from an arrangement exactly one level shallower.
- Tables are exhaustive — 3,024 entries each, so a lookup miss means corruption rather than an expected gap.
- Parity is invariant — random walks never leave the solvable half of the state space.
- EBF recovers a known value — a perfect tree of branching factor 3 and depth 4 holds 121 nodes, and the solver returns 3.0.
The closed set stores the best known g per state and stale heap entries
are skipped on pop. Both heuristics are consistent, so g is final the
first time a state is popped and no reopening happens; the check still
matters because one state can sit in the heap several times under different
g values, and expanding the worse copies costs nodes for nothing.
The pattern database heuristic indexes its tables directly rather than
calling .get(key, 0). The tables are exhaustive, so a miss means a corrupt
database — returning 0 there would leave A* running on a silently degraded
heuristic instead of failing where the bug is.
- The frontier stores the full path in every heap entry, which is O(depth) memory per entry. Parent pointers with a reconstruction pass at the end would be cheaper; at 8-puzzle scale it does not matter.
- The 4+4 split is the obvious partition, not a tuned one. Other groupings give different bounds, and a 5+3 split is usually stronger.
- No symmetry reduction. Reflecting the board across the main diagonal maps the puzzle to itself, so a second lookup on the reflected state gives a second admissible value and the max of the two is still admissible.
- 8-puzzle only. The same construction scales to the 15-puzzle, where pattern databases stop being a nicety and become the only practical way to solve hard instances optimally.
MIT