
Ian Parberry, "A Memory-Efficient Method for Fast Computation of Short 15-Puzzle Solutions", IEEE Transactions on Computational Intelligence and AI in Games, Vol. 7, No. 2, pp. 200-203, 2015. [pdf from IEEEXplore]
Abstract
While the 15-puzzle has a long and interesting history dating back to the 1870s, it still continues to appear as apps on mobile devices and as minigames inside larger video games. We demonstrate a method for solving the 15-puzzle using only 4.7MB of tables that on a million random instances was able to find solutions of 65 moves on average and 95 moves in the worst case in under a tenth of a millisecond per solution on current desktop computing hardware. These numbers compare favorably to the worst-case upper bound of 80 moves and to the greedy algorithm published in 1995, which required 118 moves on average and 195 moves in the worst case.