The original goal:
Solving the 15 puzzle optimally in Ruby
The current status:
I have an implementation of A* that uses Manhattan distance as the heuristic. It solves any 8 puzzle, including the worst case scenario (31 moves to reach the goal state), in a few seconds, or if no solution exists, immediately says so.
Tests with randomly generated 4 x 4 grids suggest that A* is insufficient for solving the 15 puzzle in a reasonable amount of time. Further research has confirmed that A* is ill-suited for solving random 15 puzzles.
In light of this, I implemented two further optimizations:
- I used a more accurate heuristic: Manhattan Pair Distance
- I switched to iterative deepening A* to keep a manageable memory profile
This has made solving random 15 puzzles more tractable at the expense of increasing the time to solve random 8 puzzles from a few seconds to a few minutes. The added calculation for linear conflict and the fact that IDA* does not remember prior work is detrimental for the small search space of a 3 x 3 grid, but practically essential for 4 x 4 grids and beyond.
Unfortunately, even after all this, solving random 15 puzzles optimally in a reasonable amount of time in Ruby still proves elusive. The next thing I'll try is to generate a disjoint pattern database for the 15 puzzle and use that as an even more accurate heuristic for IDA*.
(still in progress...)