15Puzzle Optimal Solver  


Korf, R., and Schultze, P. 2005. Largescale parallel breadthfirst search. In Proceedings of the 20th National Conference on Artificial Intelligence (AAAI05), 1380–1385.
The expected value for the solving length is 52.59. 

The 17 positions which need 80 moves are 

To find one or all optimal solutions, we do an iterative deepening depthfirst search. Using a heuristic which gives a lower estimate of the number of moves to solve the puzzle allows tree pruning (IDA*) You can choose between several different heuristics:
Generating 1000 random positions led to the following average performance (Intel(R) Core(TM)i7 CPU 920@2.67 GHz, 1 core), in ms/position: Manhattan Distance: 25600, Walking Distance(WD): 1890, 555Pattern Database(PDB): 370 I hope the features of the program are almost selfexplanatory. You can use drag and drop with the left or right mouse button to swap tiles. Download Program 

Did you notice that the arrangement of numbers in the 15puzzle shown above has an interesting property? The numbers in the rows, columns and both main diagonals all add up to 30. © 2013 Herbert Kociemba 