5x5 sliding puzzle can be solved in 205 moves

Consider a 5x5 sliding puzzle with the solved state
 1  2  3  4  5
 6  7  8  9 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24   
We can solve the puzzle in three steps. First solve 1,2,3,4,5,6,7, then solve 8,9,10,11,12,16,17,21,22, and finally solve the 8 puzzle in the bottom right corner. Step 1 requires 91 moves:
depth   new             total
0       18              18
1       6               24
2       13              37
3       27              64
4       54              118
5       117             235
6       231             466
7       443             909
8       786             1695
9       1448            3143
10      2597            5740
11      4816            10556
12      8532            19088
13      15472           34560
14      26748           61308
15      47183           108491
16      79496           187987
17      136672          324659
18      224636          549295
19      376088          925383
20      600761          1526144
21      977539          2503683
22      1515075         4018758
23      2393571         6412329
24      3601325         10013654
25      5527589         15541243
26      8069297         23610540
27      12022277        35632817
28      17021031        52653848
29      24627525        77281373
30      33844614        111125987
31      47586505        158712492
32      63514288        222226780
33      86887502        309114282
34      112774814       421889096
35      150314361       572203457
36      189957201       762160658
37      246973888       1009134546
38      304170270       1313304816
39      386085891       1699390707
40      463529743       2162920450
41      574570371       2737490821
42      672500485       3409991306
43      813816527       4223807833
44      928097024       5151904857
45      1095799490      6247704347
46      1216751429      7464455776
47      1400776123      8865231899
48      1513349352      10378581251
49      1697763464      12076344715
50      1783569892      13859914607
51      1948622983      15808537590
52      1989357113      17797894703
53      2115033986      19912928689
54      2096685318      22009614007
55      2167372761      24176986768
56      2084209967      26261196735
57      2092375966      28353572701
58      1949444991      30303017692
59      1898272010      32201289702
60      1711178109      33912467811
61      1613791967      35526259778
62      1405324573      36931584351
63      1281373441      38212957792
64      1075889326      39288847118
65      946422379       40235269497
66      764388688       40999658185
67      647094763       41646752948
68      501331438       42148084386
69      407273182       42555357568
70      301651766       42857009334
71      234365835       43091375169
72      165264320       43256639489
73      122305698       43378945187
74      81667733        43460612920
75      57231802        43517844722
76      35912967        43553757689
77      23653330        43577411019
78      13820185        43591231204
79      8478741         43599709945
80      4550561         43604260506
81      2555472         43606815978
82      1235541         43608051519
83      621129          43608672648
84      262060          43608934708
85      112429          43609047137
86      39245           43609086382
87      13409           43609099791
88      3407            43609103198
89      706             43609103904
90      87              43609103991
91      9               43609104000
92      0               43609104000
Step 2 requires 84 moves:
depth   new             total
0       9               9
1       6               15
2       11              26
3       20              46
4       40              86
5       85              171
6       159             330
7       299             629
8       545             1174
9       1001            2175
10      1830            4005
11      3324            7329
12      5953            13282
13      10669           23951
14      18987           42938
15      33495           76433
16      58330           134763
17      101083          235846
18      173039          408885
19      294498          703383
20      494067          1197450
21      823164          2020614
22      1353950         3374564
23      2214163         5588727
24      3573928         9162655
25      5733208         14895863
26      9069793         23965656
27      14247674        38213330
28      22071656        60284986
29      33889391        94174377
30      51266714        145441091
31      76735420        222176511
32      113083778       335260289
33      164597031       499857320
34      235684483       735541803
35      332870380       1068412183
36      462213490       1530625673
37      632425747       2163051420
38      850238821       3013290241
39      1125671656      4138961897
40      1463511574      5602473471
41      1873186675      7475660146
42      2353402676      9829062822
43      2909790637      12738853459
44      3530532007      16269385466
45      4213385459      20482770925
46      4933988628      25416759553
47      5678800914      31095560467
48      6413837131      37509397598
49      7113857320      44623254918
50      7743843883      52367098801
51      8270017065      60637115866
52      8670245074      69307360940
53      8907608786      78214969726
54      8986369519      87201339245
55      8872198502      96073537747
56      8603675858      104677213605
57      8153719906      112830933511
58      7590423939      120421357450
59      6895662414      127317019864
60      6151170762      133468190626
61      5346220516      138814411142
62      4557885007      143372296149
63      3779181153      147151477302
64      3067889459      150219366761
65      2417318650      152636685411
66      1858658948      154495344359
67      1384259292      155879603651
68      1000825045      156880428696
69      699567548       157579996244
70      471239409       158051235653
71      306330726       158357566379
72      190084789       158547651168
73      113468754       158661119922
74      63857593        158724977515
75      34265655        158759243170
76      17003083        158776246253
77      7866868         158784113121
78      3246307         158787359428
79      1194858         158788554286
80      363662          158788917948
81      93145           158789011093
82      16830           158789027923
83      2380            158789030303
84      97              158789030400
85      0               158789030400
Step 3 requires 30 moves. The distribution of 8 puzzle is well known and it shows that the puzzle can be solved in 31 moves. However, after we finish step 2, the empty space will be in either position 13, 14, 15, 18, or 23. There are only 2 positions on 8 puzzle that require 31 moves and neither of them have the empty space in any of these positions, so stage 3 can be solved in 30 moves for a total of 91+84+30=205 moves.

Comment viewing options

Select your preferred way to display the comments and click 'Save settings' to activate your changes.

Down to 204

I have verified the correctness of these computations and I noticed that all 9 configurations at depth 91 in Step 1 have to be solved in an even number of moves (considering the parity of the empty cell), which I believe implies there are actually no configurations that require the full 205 moves and that we can lower the upper bound to 204.

Down to 200 moves

I believe I have now reduced the upper bound for the 5x5 sliding puzzle to 200 moves.

I find it conceptually convenient to think of starting with the solved state and to then reach each state from there in the minimum number of moves, so while my dissection into phases is very similar to Ben Whitmore's, I have numbered the solving phases in the opposite order. Here is a side by side comparison in some phase dissection notation:

Ben Whitmore  |  Johan de Ruiter
              |
   3 3 3 3 3  |  3 3 3 3 3
   3 3 2 2 2  |  3 2 2 2 3
   2 2 1 1 1  |  2 2 1 1 1
   2 2 1 1 1  |  2 2 1 1 1
   2 2 1 1 0  |  2 2 1 1 0
Where Ben found 31 + 84 + 91 = 206 as phase depths, I find 31 + 78 + 94 = 203.

Ben observed that in phase 1 (in my numbering), although the maximum number of moves is 31, the states at this depth do not contribute to longer sequences because "after we finish step 2, the empty space will be in either position 13, 14, 15, 18, or 23. There are only 2 positions on 8 puzzle that require 31 moves and neither of them have the empty space in any of these positions". The same argument holds for my configuration, so that gives us 205 and 202 moves respectively.

Inspired by this argument, but thinking in the other direction (branching out from the solution), I figured the states at a lower depth could potentially get a head start in the next phase, if only there was a way to transfer this information from one phase to the next. The location of the empty cell seemed to be an excellent candidate: As soon as all states with the empty cell in a specific position have been reached during phase N, phase N+1 could get started with the empty cell in that position. We basically shift the phases into each other as much as possible. I noticed that stannic used diagrams for empty locations that are very similar to mine in this older thread, but it wasn't clear to me yet how he used them exactly. In any event, I don't think these diagrams, depicting the depth at which each position is last encountered as the empty cell within a phase, in and of themselves contain sufficient information to draw optimal conclusions, but they can be used as offsets in the computation of the next phase.

Applying phase shifting to our respective phase dissections, Ben Whitmore's is reduced to 204 moves (matching the bound I previously obtained with a parity argument), while mine is reduced to 200 moves.

Down to 198 moves

When looking at the table that indicates the depth of the deepest occurrence of the empty location for the phase dissection above that led to 200 when using phase shifting, I realized that depending on the location of the empty cell in the scrambled puzzle, we could choose to either use this phase dissection or the one obtained by reflecting it along the main diagonal.
198 199 200 199 198
197 198 199 198 197
196 197 198 197 196
197 196 197 196 197
196 197 196 197 196
Since all the 199 and 200 values in this table are located above the main diagonal, I think we can say that the new upper bound is now 198 moves.

Down to 196 moves

Using the dissection below, in combination with its reflection in the main diagonal, I believe I got the upper bound down to 196 moves.
2 2 2 2 2
2 1 1 1 1
2 1 1 1 1
2 1 1 1 1
3 1 1 1 0
It is known that all 4x4 puzzles can be solved within 80 moves and when I looked at the 17 antipodes, I noticed all of them have their blank in the upper left, so for the phase shifting I used these offsets:
-- -- -- -- --
-- 80 79 78 79
-- 79 78 79 78
-- 78 79 78 79
-- 79 78 79 78
Because I didn't work through the 4x4 myself yet, I wasn't sure if these offsets were chosen too pessimistically, but even with the most optimistically chosen offsets the upper bound remains 196.

Down to 184 moves

This is a result from February 26th that I didn't report here yet:

By combining phase 2 and phase 3 from the previous result, using the same pessimistic phase offsets, I believe I have reduced the upper bound to 184 moves.

Down to 182 moves

I believe I have managed to further reduce the upper bound to 182 moves by combining results for rotations of the phase dissection I used for the 184 moves. The intuition behind this is that worst cases for one dissection, might not be worst cases for another.

When the 4x4 is in the top left, two extra moves are necessary to move the blank back to the lower right corner (for which there are two choices) and when it is in the lower left or in the top right, one extra move is necessary.

I was still constrained by not having computed the real phase offsets for the 4x4 yet and by the fact that my program currently relies on symmetry in the main diagonal, so I had to apply some rotations and I had to artifically increase some of the phase offsets because of this too.

Extra info and more bounds

Also it's probably worth pointing out that I did this computation over a year ago (oct/nov 2016) but never published it anywhere. I also have bounds for the 6x6 through 10x10 puzzles:
puzzle    upper bound    solution steps (moves required)
6x6       405            top row (111), left column (89), 5x5 (205)
7x7       716            1,2,3 (84), 4,5,6,7 (101), left column (126), 6x6 (405)
8x8       1164           1,2,3,4 (121), 5,6,7,8 (121), 9,17,25 (112), 33,41,49,57 (94), 7x7 (716)
9x9       1780           1,2,3 (119), 4,5,6 (109), 7,8,9 (122), 10,19,28,37 (133), 46,55,64,73 (133), 8x8 (1164)
10x10     2587           1,2,3,4 (162), 5,6,7 (125), 8,9,10 (141), 11,21,31 (129), 41,51,61 (119), 71,81,91 (131), 9x9 (2587)
I've added all of these bounds to OEIS A087725.