Building an 8-puzzle is easy. Finding its solution is tougher. An 8 puzzle is a sliding puzzle on a 3 x 3 grid of tiles with one missing. The others are scrambled by sliding tiles into the blank space.
I decided that in order to find a solution, I had to try a breadth-first search.
- look at next possible moves
- check for a solution
- no solution?
- look through possible moves for solutions, starting with the move closest to the first move
Empirically I proved that finding solutions took longer than my capacity to tolerate delay before I lost my cool. To improve the search I added a heuristic, or a smarter method of choosing which move was best.
To do this we sum all the steps away each tile is from where it belongs. In taxicab geometry (I swear that is a real branch of mathematics), there is a concept of a manhattan distance or the distance between two points on a grid. We can use this to underestimate how many moves we are from a whole solution.
We add our heuristic to our search and we’ve got ourselves an A* search algorithm:
- check to see if your leaf is the solution (I know, right?)
- if it’s not the solution, collect all the connected leaves
- put the leaves in a basket
- pick the best leaf from the basket using our heuristic
- then return our last leaf to the tree and don’t pick it again
And with that change, my solutions survived my patience. Check the code below if you’re interested in the details.
