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.

Download Program

Did you notice that the arrangement of numbers in the 15-puzzle shown above has an interesting property?

The numbers in the rows, columns and both main diagonals all add up to 30.
Such an arrangement is called a Magic Square. There are 7040 different Magic Squares, but only 3520 of them can be solved with the blank in the lower right corner - as shown at the top of the page. The one shown above is the only one which is solvable within 35 moves and there are no Magic Squares which are solvable with fewer moves.

© 2013  Herbert Kociemba