5x5 can be solved in 109 MTM

Any instance of the Twenty-Four puzzle (5x5) can be solved in 109m (multi-tile moves) or less. My proof consists of several steps. It is possible that there is logical error in this proof, so please check it thoroughly. However, I cannot find errors.

It is known that 4x4 Fifteen Puzzle can be solved in 43m. Also, there is 16 antipodes that cannot be solved in less than 43m. The table below gives the number of 4x4 antipodes with blank tile in any given square. Note that I used "0-based" goal (that is, in my goal state blank tile is in top left corner); Bruce Norskog used "0-terminated" goal (with blank tile in bottom right corner); so I turned each of 16 antipodes 180 degrees to make this table.

[1]
  0  1  2  3     1 0 0 2
  4  5  6  7     0 0 1 0
  8  9 10 11     0 1 0 0
 12 13 14 15     2 0 0 9
 0-based goal   # of antipodes

I used 4x4 puzzle as last stage of 5x5 solution. Before this stage, we should solve all fringe tiles.

[2] 5x5 goal. Tiles 4,9,14,19,20,21,22,23,24 are fringe tiles.
  0  1  2  3  4
  5  6  7  8  9
 10 11 12 13 14
 15 16 17 18 19
 20 21 22 23 24

Note that in table [1] above, in any row there is at least one zero. Also, in any column there is at least one zero.

Let M be last move before getting into 4x4 puzzle (that is, all subsequent moves after M wil not touch fringe tiles). Then we always can select such multi-tile move M that resulting tile configuration can be solved in at most 42m.

Next step will be proof that 67m is sufficient to solve all nine fringe tiles. With this proof, the whole 5x5 puzzle can be solved in at most 67m + 42m = 109m.

We can split all configurations to 25 classes. Class i (0 ≤ i < 25) contains all configurations with blank tile in square i. Then we can combine these 25 classes to three groups A,B,C. This splitting is given below in table [3].

[3]
  A A A A A
  A C B B A
  A B B B A
  A B B B A
  A A A A A

Assertion 1. Any configuration of fringe tiles from group A can be solved in at most 67m.

Proof. I computed distribution for the following pattern. On the left shown pattern; on the right shown maximal distance in each of 25 classes. We can reflect the pattern through major diagonal; by combining the pattern with its reflection we can get 40m for any configuration from group A.

[4]
  .  .  .  .  4   40 40 40 40 40
  .  .  .  .  .   41 41 41 41 41
  .  .  .  .  .   41 41 41 41 41
  .  .  .  .  .   41 41 41 41 41
 20 21 22 23 24   40 40 40 40 40

To finish solving fringe tiles, during stage 2 we should solve the following pattern. Again, on the left shown pattern, and on the right shown distribution of maximal distances by class. Maximal distance is 28m; however, we always can avoid 28m* configurations in stage 2 by selecting good last move in stage 1. Therefore, any fringe configuration from group A can be solved in at most 40m + 27m = 67m.

[5]
  .  .  .  .  #   27 27 27 27  #
  .  .  .  .  9   28 28 28 28 28
  .  .  .  . 14   28 28 28 28 28
  .  .  .  . 19   27 27 27 27 27
  #  #  #  #  #    #  #  #  #  #

Assertion 2. Any configuration of fringe tiles from group B can be solved in at most 67m.

Proof. I computed distribution for the following pattern. By combining distributions of this pattern and its reflection through major diagonal, we can get 40m upper bound for any fringe configuration from group B.

[6]
  .  .  .  .  .   40 40 40 40 40
  .  .  .  .  .   41 41 41 41 40
  .  .  .  .  .   40 40 40 40 40
  .  .  .  . 19   41 40 41 40 41
 20 21 22 23 24   41 40 41 40 41

To finish solving fringe tiles, we should solve in stage 2 the following pattern. We can get 27m* for this pattern using pattern on the table [5] by vertical reflection. So, any fringe tile configuration from group B can be solved in at most 40m + 27m = 67m.

[7]
  .  .  .  .  4
  .  .  .  .  9
  .  .  .  . 14
  .  .  .  .  #
  #  #  #  #  #

Assertion 3. Any configuration of fringe tiles from group C can be solved in at most 67m.

Proof. Group C consists of single class 6. We already proven that fringe configuration from any other class can be solved in 67m.

Let's go back to pattern [6]. There is 13 antipodes at depth 41m* for this pattern. However, only one of these configurations has blank square 6.

[8]. Pattern [6], 41m*.

 19  . 22  . 20
 23  0  .  . 24
 21  .  .  .  .
  .  .  .  .  .
  .  .  .  .  .

Let's go back to pattern [4]. There is 59 antipodes at depth 41m*. However, only four of these configurations are in class 6.

[9]. Pattern [4], 41m*.

 20 23 21 22 24     21 22 23 24 20     24  .  .  . 20     23  . 21 22 24
  .  0  .  .  .      .  0  .  .  .      .  0  .  .  .     20  0  .  .  .
  .  .  .  .  .      .  .  .  .  .      .  .  .  .  .      .  .  .  .  .
  .  .  .  .  .      .  .  .  .  .      .  .  .  . 21      .  .  .  .  .
  4  .  .  .  .      4  .  .  .  .      4 23  . 22  .      4  .  .  .  .

There is no such fringe tile configuration from class 6 that is 41m* both in pattern [4] and pattern [6].

Therefore, any configuration of fringe tiles from group C can be solved in at most 40m + 27m = 67m.

67m is sufficient to solve all nine fringe tiles. So we can solve any 5x5 instance in 67m + 42m = 109m.

208s for 5x5

I was unable to further reduce 109m upper bound using the same technique as in my post above. However, I was able to get 208s upper bound for 5x5 puzzle. I tried various combinations of first two stages that should solve 9 "fringe" tiles and alternatives for stage 3 (not necessarily a 4x4 sub-puzzle).

Below is sequence of substages that solves 5x5 in at most 208=85+72+51 single tile moves.

 -----------------------------------------------------------------------------
 Stage 1                        Stage 2                    Stage 3
 (85s)                          (72s after stage 1)        (51s after stage 2)
 -----------------------------------------------------------------------------
 Goal state
  .  .  .  .  .                 .  .  .  3  4               0  1  2  #  #
  .  .  .  .  .                 .  .  0  8  9               5  6  7  #  #
  .  .  .  .  .                 .  .  . 13 14              10 11 12  #  #
  .  .  0  . 19                 .  .  . 18  #              15 16 17  #  #
 20 21 22 23 24                 #  #  #  #  #               #  #  #  #  #
 -----------------------------------------------------------------------------
 Distance by location of the blank tile (slot)    
 81 82 83 82 83                73 72 73 74 75              52 51 52  #  #
 82 81 82 81 82                72 73 72 73 74              51 52 51  #  #
 83 82 83 82 83                73 72 73 74 75              52 51 52  #  #
 84 83 84 83 84                72 73 72 73  #              53 52 53  #  #
 85 84 85 84 85                 #  #  #  #  #               #  #  #  #  #
 -----------------------------------------------------------------------------
 Distance distribution
 depth    new      total      depth     new      total
  0         1          1        0         1          1
  1         4          5        1         4          5
  2         9         14        2         9         14
  3        16         30        3        16         30
  4        23         53        4        21         51
  5        45         98        5        47         98
  6        90        188        6        91        189
  7       177        365        7       189        378
  8       300        665        8       321        699
  9       544       1209        9       629       1328
 10       921       2130       10      1046       2374
 11      1738       3868       11      2061       4435
 12      2939       6807       12      3348       7783
 13      5239      12046       13      6471      14254
 14      8496      20542       14     10520      24774
 15     14828      35370       15     19880      44654
 16     23261      58631       16     31091      75745
 17     39311      97942       17     57293     133038
 18     60197     158139       18     87760     220798
 19     99322     257461       19    158370     379168
 20    147377     404838       20    235725     614893
 21    236137     640975       21    412464    1027357
 22    339096     980071       22    595474    1622831
 23    527814    1507885       23   1009974    2632805
 24    735547    2243432       24   1409581    4042386
 25   1113970    3357402       25   2312393    6354779
 26   1504206    4861608       26   3121326    9476105
 27   2211526    7073134       27   4945452   14421557
 28   2893432    9966566       28   6441325   20862882
 29   4134561   14101127       29   9842724   30705606
 30   5244021   19345148       30  12358092   43063698
 31   7291144   26636292       31  18206389   61270087
 32   8975149   35611441       32  22038462   83308549
 33  12161404   47772845       33  31337265  114645814
 34  14546233   62319078       34  36573742  151219556
 35  19258468   81577546       35  50219630  201439186
 36  22430670  104008216       36  56487772  257926958
 37  29041445  133049661       37  74916624  332843582
 38  32934739  165984400       38  81163463  414007045
 39  41736768  207721168       39 103924737  517931782
 40  46100246  253821414       40 108336991  626268773
 41  57174756  310996170       41 133879264  760148037
 42  61460632  372456802       42 134167626  894315663
 43  74515296  446972098       43 159999863 1054315526
 44  77808480  524780578       44 154016675 1208332201
 45  92115552  616896130       45 177239627 1385571828
 46  93344039  710240169       46 163742701 1549314529
 47 107814181  818054350       47 181761910 1731076439
 48 105920451  923974801       48 160906433 1891982872
 49 119269494 1043244295       49 172188539 2064171411
 50 113511284 1156755579       50 145808500 2209979911
 51 124480410 1281235989       51 150299336 2360279247
 52 114644678 1395880667       52 121453625 2481732872
 53 122312105 1518192772       53 120439405 2602172277
 54 108886659 1627079431       54  92544352 2694716629
 55 112895774 1739975205       55  88105478 2782822107
 56  96993533 1836968738       56  64062581 2846884688
 57  97551735 1934520473       57  58336641 2905221329
 58  80721088 2015241561       58  39839095 2945060424
 59  78635509 2093877070       59  34515153 2979575577
 60  62551622 2156428692       60  21912639 3001488216
 61  58926236 2215354928       61  17928169 3019416385
 62  44943111 2260298039       62  10415481 3029831866
 63  40848516 2301146555       63   7958953 3037790819
 64  29775251 2330921806       64   4128018 3041918837
 65  26049211 2356971017       65   2897039 3044815876
 66  18078197 2375049214       66   1295515 3046111391
 67  15181336 2390230550       67    819256 3046930647
 68   9979043 2400209593       68    298432 3047229079
 69   8010568 2408220161       69    165974 3047395053
 70   4951933 2413172094       70     45111 3047440164
 71   3787231 2416959325       71     21152 3047461316
 72   2187917 2419147242       72      3622 3047464938
 73   1584772 2420732014       73      1215 3047466153
 74    843808 2421575822       74        73 3047466226
 75    572444 2422148266       75        14 3047466240
 76    273810 2422422076
 77    171403 2422593479
 78     71276 2422664755
 79     40090 2422704845
 80     13875 2422718720
 81      6752 2422725472
 82      1692 2422727164
 83       690 2422727854
 84       108 2422727962
 85        38 2422728000
 -----------------------------------------------------------------------------