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.

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.