Deutsche Version

# 15-Puzzle Optimal Solver

 The solved state of the 15-puzzle can be reached from any solvable position within 80 moves or less. Exchanging two arbitrary tiles of a solvable position leads to an unsolvable position. There are 16!/2 = 10,461,394,944,000 different solvable positions. Korf was able to compute the number of states as a function of the depth in 2005.
 depth states depth states 0 1 41 83,099,401,368 1 2 42 115,516,106,664 2 4 43 156,935,291,234 3 10 44 208,207,973,510 4 24 45 269,527,755,972 5 54 46 340,163,141,928 6 107 47 418,170,132,006 7 212 48 500,252,508,256 8 446 49 581,813,416,256 9 946 50 657,076,739,307 10 1,948 51 719,872,287,190 11 3,938 52 763,865,196,269 12 7,808 53 784,195,801,886 13 15,544 54 777,302,007,562 14 30,821 55 742,946,121,222 15 60,842 56 683,025,093,505 16 119,000 57 603,043,436,904 17 231,844 58 509,897,148,964 18 447,342 59 412,039,723,036 19 859,744 60 317,373,604,363 20 1,637,383 61 232,306,415,924 21 3,098,270 62 161,303,043,901 22 5,802,411 63 105,730,020,222 23 10,783,780 64 65,450,375,310 24 19,826,318 65 37,942,606,582 25 36,142,146 66 20,696,691,144 26 65,135,623 67 10,460,286,822 27 116,238,056 68 4,961,671,731 28 204,900,019 69 2,144,789,574 29 357,071,928 70 868,923,831 30 613,926,161 71 311,901,840 31 1,042,022,040 72 104,859,366 32 1,742,855,397 73 29,592,634 33 2,873,077,198 74 7,766,947 34 4,660,800,459 75 1,508,596 35 7,439,530,828 76 272,198 36 11,668,443,776 77 26,638 37 17,976,412,262 78 3,406 38 27,171,347,953 79 70 39 40,271,406,380 80 17 40 58,469,060,820

Korf, R., and Schultze, P. 2005. Large-scale parallel breadth-first search. In Proceedings of the 20th National Conference on Artificial Intelligence (AAAI-05), 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 depth-first 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:

• Manhattan Distance: For each tile the number of grid units between its current location and its goal location are counted and the values for all tiles are summed up. This heuristic is easy to compute but it is not very powerful.
• Walking Distance: Considerably more powerful than the Manhattan Distance while not using much memory. Developed by Ken'ichiro Takahashi, see his website for details.
• Felner, Ariel, Korf, Richard E., Hanan, Sarit, Additive Pattern Database Heuristics, Journal of Artificial Intelligence Research 22 (2004) 279-318
Pattern Databases: The heuristics introduced in this paper are implemented in my program. The 78 Pattern Database heuristic takes a lot of memory but solves a random instance of the puzzle within a few milliseconds on average. An optimal solution to the 80 moves antipodes takes a few seconds each.

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, 555-Pattern Database(PDB): 370
555-PDB + WD: 200, 663-PDB: 160, 663-PDB+WD: 120, 78-PDB: 5

I hope the features of the program are almost self-explanatory. You can use drag and drop with the left or right mouse button to swap tiles.