Deutsche Version
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.


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. A solvable magic square which can be solved with the blank in the lower right corner cannot have the blank in the lower right corner itself. If you color the 4x4 square like a chessboard all possible blank positions of the solvable magic squares have a different color than the lower right corner position. All possible four positions on the diagonal belong to 416 magic squares each, each of the other four positions to 464 magic squares. In total these are exactly the 3520 solvable magic squares.  
< Home > © 2020 Herbert Kociemba 