# 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.

### The lame software harness

First of all, thanks you for your question.

Second, I am sorry but I should disappoint you; my software harness contains error. This is not a bug in the program code but very stupid bug in my logic, so I need to rewrite most of sources. So current proved upper bounds for 5x5 puzzle are 109m and 208s; I found these bounds earlier without using "coset" solver using different technique. However, I want to continue work with "coset" solver, and I still think about proving upper bounds of 200s and 100m. Once again, sorry for disinformation.

Third, I do not think I can derive God's number for 5x5 puzzle in MTM (at least, with my current soft- and hardware harness). I do not think even about God's number in STM. Maybe I will be able to find God's number for fringe pattern of 5x5.

As far as I know, simplest way to derive God's number is to find at least one position that is at distance X and prove that all puzzle positions can be solved in ≤X. In STM metric, there is a way to obtain hard puzzle state (and therefore good lower bound); you can turn solved puzzle 180 degrees. With 4x4 puzzle, this lead to a position at distance 78s*, and you know God's number for 4x4 in STM is 80s. For 5x5 puzzle, this lead to a position that cannot be solved in <152s (according to Rokicki's optimal solver) but can be solved in 156s (you can rotate 90 degrees in 78s). By the way, I believe this "turned-180" position to be at distance 156s*, and I do not think God's number in STM will be >170s or so.

In MTM metric, I even do not know good lower bounds for 5x5. 180-degree positions are not so hard in MTM; for example, 4x4 turned 180 position can be solved in 30m while you know God's number for 4x4 is 43m. With 5x5 puzzle, turned 180-degrees can be solved in only 46m. If anyone knows harder positions in MTM or can give better theoretical lower bound please let me know.