Fifteen Puzzle Optimal Solver

The solved state of the Fifteen 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,46,139,4944,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.

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