The 8-puzzle is a classic logical puzzle: a 3×3 grid with eight numbered tiles and one empty space. The objective is to rearrange the scrambled tiles by sliding them into the empty space until you reach an ordered configuration. As part of my Artificial Intelligence coursework at Case Western Reserve University, I implemented two agents to solve it — one using A* search and the other local beam search — and ran experiments to evaluate the heuristics and their performance.
A* Search
I represent the puzzle state as an array of arrays, which makes it easy to visualize the board and to move the blank tile b.
My A* uses two heuristics. The first, h1, counts the tiles that aren't in their expected positions — simple, but it misses much of the puzzle's nuance. The second, h2 (the Manhattan distance), sums the number of moves each tile would need to return to its goal position, fully unobstructed.
Local Beam Search
Unlike A*, beam search is a local search — neither optimal nor complete. It isn't guaranteed to find a solution, and when it does, that solution may not be the best. But when it works, it often finds a path having generated far fewer nodes (usually at the cost of a longer path).
It works by keeping the k best states, expanding each in every legal direction, then iteratively keeping the k best of the newly generated states. If you know hill climbing, it's much the same — pick the best option each time — but with lower odds of getting stuck in a local minimum.
Experiments
After finishing the implementation, I ran a series of experiments to answer a few questions about the performance of the two agents and heuristics.
How does the fraction of solvable puzzles from random initial states vary with the maxNodes limit?
The fraction of solvable puzzles grows with the maxNodes limit — intuitive, since allowing more nodes never makes a previously-solvable puzzle unsolvable. I incremented maxNodes from 150 to 4500 in steps of 150, tested 100 random states, and recorded the percentage solved.
Though the graph suggests beam and h2 generate nodes at a similar level, that's misleading: beam actually generates far fewer nodes in general, but hits more "unsolvable" puzzles, inflating the max-node count.
For A* search, which heuristic generates a lower number of nodes?
H2 is more efficient than H1 by far — it never generates more nodes than H1, as the graph shows. Both H1 and H2 are optimal and complete, so they always find the same solution; they're compared only on efficiency.
How does solution length vary across the three search methods?
H1 and H2 are always optimal, so their move counts never differ. Beam is not optimal, so it's always equal to or worse than A* — usually much worse. Note: wherever beam alone dips below h1/h2, beam failed to complete for that choice of k, so its move total was set to 0.
