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

## Comment viewing options

### Is it possible?

Is it possible to solve the 5x5x5, If I know this Rubik's Cube Solution method? Recently learned..

I have to say that this thread is not about 5x5x5 Rubik's cube, it's about 5x5 sliding-tile puzzle. I do not know any upper bounds for God's Number of the 5x5x5 Rubik's cube (however, there may be).

As for 5x5x5 cube, I think you cannot use just the same solution as for 3x3x3. Jaap's Puzzle Page provides two solutions for the 5x5x5 cube. I have not tried them myself, but this was the first place on the web I thought about.

- Bulat

### 5x5 Fringe puzzle "coset solver" (last edit 08/29/11 GMT 22:07)

I want to sketch here my new attempt to adapt coset solver to fringe subpuzzle of the 5x5 (fringe subpuzzle is to reduce 5x5 puzzle to 4x4 puzzle). Clearly it is not very good description; also, I almost sure it contains many typos, pitfalls and errors. Maybe it even makes no sense at all. Anyway, I'll do this.

First, some agreements.

``` -----------------------------------------------------------------------------------
1. Tiles on diagrams
-----------------------------------------------------------------------------------
Name                                           Tile(s)     Notation
-----------------------------------------------------------------------------------
Slot ("empty square", "blank", "void", "gap")  0           0
Physical tile                                  1...24      1...24
Any physical tile                              1...24      P
Any virtual tile                               0...24      V
Any fringe tile                                16...24     F
Right column tile                              20...24     RC
Locked tile (tile that cannot be moved)        1...24      #
Anything without specification (no matter)     Anything    . - * (different colors)
-----------------------------------------------------------------------------------
```
``` ------------------
2. My solved state
------------------
0  1  2  3 20
4  5  6  7 21
8  9 10 11 22
12 13 14 15 23
16 17 18 19 24
------------------
```

I've renumbered tiles and locations to use continuous ranges. The home location of the slot is in the top left corner. In solved state, tile i occupies location @i for 0≤i<25 (see notation).

I will use notation from table 1 to refer to tile (tiles can be moved). When I want to refer to location (locations cannot be moved) I'll use the same notation but with preceding "at" symbol. For example, 4 is tile but @4 is location. Sentence "4 is in @4", "4 is @4" or even "4@4" means that tile 4 is solved.

Each tile occupies one location; one empty location ("slot location") is occupied by slot tile. Slot tile is virtual tile. All other tiles are physical tiles.

I'll use words where and who to refer to two possible representations of the puzzle state. where[i] = @j means that i@j (tile i is in location @j; location @j is occupied by tile i). Also, who[@j] = i means the same thing. X.where[4] = @4 means that 4@4 in puzzle state denoted by letter X (tile 4 occupies location @4).

Let moves[@i] be set of all moves that can be made when slot is @i (where[0] = @i, or 0@i). Each move represented by the location in which slot stops after move. For example, @6 is in moves[@7] but @10 is not.

If we use STM metric then we have the following:

```  |moves[@i]| = 2 for i in {0, 16, 20, 24},
|moves[@i]| = 4 for i in {5, 6, 7, 9, 10, 11, 13, 14, 15},
|moves[@i]| = 3 for any other i.
```

If we use MTM metric then |moves[@i]| = 8 for any i.

I used combinations "puzzle state" and "fringe state". In puzzle state, we have specified all virtual tiles. In fringe state, we have specified only slot and fringe tiles. Thus 15!/2 distinct puzzle states corresponds to the same fringe state.

Now, problems.

Main problem (MP) is to find the number of moves required to solve any given fringe state.

``` --------------------------------
3. MP
--------------------------------
V  V  V  V  V      .  .  .  . 20
V  V  V  V  V      .  .  .  . 21
V  V  V  V  V  =>  .  .  .  . 22
V  V  V  V  V      .  .  .  . 23
V  V  V  V  V     16 17 18 19 24
--------------------------------
```

Subproblem A[i] is to find the number of moves required to solve any given fringe state with slot @i (0≤i<25).

Then we have MP = max(A[i]; 0≤i<25).

``` --------------------------------
4. A[12]
--------------------------------
P  P  P  P  P      .  .  .  . 20
P  P  P  P  P      .  .  .  . 21
P  P  P  P  P  =>  .  .  .  . 22
0  P  P  P  P      .  .  .  . 23
P  P  P  P  P     16 17 18 19 24
--------------------------------
```

Subproblem B[i, j] is to find the number of moves required to transform any fringe state with slot @i to solved fringe state with slot @j (0≤i<25; 0≤j<16).

Then we have A[i] = min(B[i, j]; 0≤j<16).

``` --------------------------------
5. B[23, 13]
--------------------------------
P  P  P  P  P      .  .  .  . 20
P  P  P  P  P      .  .  .  . 21
P  P  P  P  P  =>  .  .  .  . 22
P  P  P  P  0      .  0  .  . 23
P  P  P  P  P     16 17 18 19 24
--------------------------------
```

Subproblem C[i, j, t] is to find the number of moves required to transform any fringe state from t-set in which slot is @i, to solved fringe state with slot @j (0≤i<25; 0≤j<16). t-set contains all fringe states in which where[k] for k = 20,21,22,23,24 are encoded in t (t is integer number in fact).
In other words, from t we know locations of all right column tiles, and from j we know slot location.

Then we have B[i, j] = max(C[i, j, t]; any t).

For any given t, not all 25 values of i are possible. There are 25!/20!=6,375,600 t-sets; for any given 0≤t<6,375,600 we have only 20 possibilities of i. (For example, if t = (20@2,21@3,22@5,23@8,24@13), then i=2, i=3, i=5, i=8 or i=13 are not compatible with t because we cannot put two tiles in one location.)
We always have 20 possibilities of i and 16 possibilities of j. So we have 20*16*(25!/20!)=2,040,192,000 subproblems C[i, j, t].
Also, t-set contains all fringe states with fixed right column tiles. Four remaining fringe tiles and slot tile can be in 5 of 20 locations, so we have 20*19*18*17*16=1,860,480 fringe states in each t-set.

``` -------------------------------------------
6. C[21, 13, t]
t = (20 @2, 21 @3, 22 @5, 23 @8, 24 @13)
-------------------------------------------
.  . 20 21  .      .  .  .  . 20
. 22  .  .  0      .  .  .  . 21
23  .  .  .  .  =>  .  .  .  . 22
. 24  .  .  .      .  0  .  . 23
.  .  .  .  .     16 17 18 19 24
-------------------------------------------
```

Subproblem D[t] is to find the number of moves required to transform any fringe state from t-set to solved fringe state.
D[t] = max(min(C[i, j, t]; 0≤j<16); 0≤i<25).

Subproblem E[i, t] is to find the number of moves requires to solve any fringe state from t-set in which slot is @i (0≤i<25). For any given t, only 20 values of i are compatible with t (see subproblem C). We have the following:
E[i, t] = min(C[i, j, t]; 0≤j<16);
D[t] = max(E[i, t]; 0≤i<25; i is compatible with t).

``` -------------------------------------------------------------------------------
7. t = (20 @2, 21 @3, 22 @5, 23 @8, 24 @13)
D[t]                                          E[21, t]
-------------------------------------------------------------------------------
.  . 20 21  .      .  .  .  . 20              .  . 20 21  .      .  .  .  . 20
. 22  .  .  .      .  .  .  . 21              . 22  .  .  0      .  .  .  . 21
23  .  .  .  .  =>  .  .  .  . 22             23  .  .  .  .  =>  .  .  .  . 22
. 24  .  .  .      .  .  .  . 23              . 24  .  .  .      .  .  .  . 23
.  .  .  .  .     16 17 18 19 24              .  .  .  .  .     16 17 18 19 24
-------------------------------------------------------------------------------
```

First, I'll try subproblem C[i, j, t]. We have slot @i and where[k] for 20≤k<25. Using this information, we can make representative state R in which all other tiles (1...19) are in arbitrary permutation (however, we need to specify it). Example is given below. I placed tiles 1..19 in natural order; I hope this will be useful. Let call such representative "canonical". We always can make one and only one canonical representative.

``` --------------------------------------------------------------
8.
--------------------------------------------------------------
.  . 20 21  .      1  2 20 21 16                .  .  .  . 20
. 22  .  .  0      3 22  4  5  0                .  .  .  . 21
23  .  .  .  .     23  6  7  8 17                .  .  .  . 22
. 24  .  .  .      9 24 10 11 18                .  0  .  . 23
.  .  .  .  .     12 13 14 15 19                .  .  .  . 24
--------------------------------------------------------------
C[21, 13, t]      Canonical representative (R)     X
t = (20 @2, 21 @3, 22 @5, 23 @8, 24 @13)
--------------------------------------------------------------
```

Now we start IDA* search from R hoping to reach some puzzle state X in which right column tiles are solved, and slot is @j. Looking forward, we do not stop after finding one solution; we continue also with suboptimal solutions.

Each time we found puzzle state X by some maneuver Y, we will look which tiles are in locations @16, @17, @18, @19 in X. If, after finding puzzle state X, we have found that tiles 16, 17, 18, 19 are in these locations, then we would have all fringe tiles solved.

I'll give example.

``` -------------------------------------------------------------------------------------------
9.
-------------------------------------------------------------------------------------------
1  2 20 21 16       .  .  .  . 20     1  .  .  .  .     17  . 20 21  .       .  .  .  . 20
3 22  4  5  0  Y    .  .  .  . 21     .  .  .  5  .      . 22  . 18  0  Y    .  .  .  . 21
23  6  7  8 17  =>   .  .  .  . 22     .  .  7  .  .     23  . 16  .  .  =>   .  .  .  . 22
9 24 10 11 18       .  0  .  . 23     .  .  .  .  .      . 24  .  .  .       .  0  .  . 23
12 13 14 15 19       7  1  5 12 24    12  .  .  .  .     19  .  .  .  .      16 17 18 19 24
-------------------------------------------------------------------------------------------
R                   X               z in R            z' in R'                X'
z = (7,1,5,12)                                       z' = (16,17,18,19)
-------------------------------------------------------------------------------------------
X is found during search from R by maneuver Y:   X = ApplyMoves(R, Y).
R' is obtained by replacing in R tiles 7,1,5,12 with tiles 16,17,18,19 respectively.
X' = ApplyMoves(R', Y).
-------------------------------------------------------------------------------------------
```

Now we have one-to-one correspondence. Each quadruple z=(X.who[@16];X.who[@17];X.who[@18];X.who[@19]) corresponds to some fringe state in which right column tiles and slot are in the same locations as in R. We have 19*18*17*16=93,024 possible quadruples. This is the number of elements of t-set in our subproblem C[i, j, t]. This is the number of elements of t-set with fixed slot location @i. In subproblem C[i, j, t], t-set contains 1,860,480 fringe states. 93,024 is 1/20 of this.

So, if we find all 93,024 quadruples with our IDA* then we would have found all 93,024 fringe states in t-set and therefore find C[i, j, t] for some fixed i, j, t. We can use bitvector of length 93,024 to mark all found X.

Next, we can solve simultaneously all subproblems C[i, j, t] for 0≤i<25 (i is compatible with t) and 0≤j<16. So there are 25*16=400 20*16=320 subproblems C, or 20 subproblems E[i, t].

In main loop of "t-set solver", we can solve subproblems C[i, j, t] one by one, sequentially; however, we can maintain 16 bitvectors at once, each of length 93,024, and start single IDA* from R hoping to reach some puzzle state X in which right column tiles are solved, and slot location is in {@0...@15}. We do not need to have slot in some selected location in X; after solving right column and putting slot in {@0...@15}, we can select one of 16 bitvectors to mark X. So we will solve 16 subproblems C[i, j, t] for 0≤j<16 "in parallel". That is, the whole E[i, t] for some 0≤i<24, 0≤t<6,375,600.

Prepass (before running main loop for depth d) is scanning through each of 16 bitvectors. t is still fixed; for 0≤j<16, 0≤z<93,024, we have incomplete puzzle state with solved tiles 20..24, slot in @j and quadruple of tiles in locations @16...@19 encoded in z.
First, we try to make all moves m in moves[@j], 0≤m<16; z does not change after such moves. Then after such move m we will get from subproblem C[i, j, t] to C[i, m, t].

Then dist(C[i, m, t]; z) ≤ 1 + dist(C[i, j, t]; z).

Second, we try to make all moves m in moves[@j], 16≤m<20; after such moves we do not get to any subproblem C[]. It seems to me that we have to make much more than one move. This is not so nice. I'll show example.

``` -------------------------------------------------------------------------------------
10. Prepass. Subproblems C[i, j, t]; 0≤j<16; i = const; t = const.
-------------------------------------------------------------------------------------
.  .  .  . 20      .  .  .  . 20                       .  .  .  . 20
.  .  .  . 21  1U  .  .  .  . 21  1LD 2R 1U 2L 1DRURD  .  .  .  . 21
.  .  .  . 22  =>  .  .  .  . 22          =>           .  .  .  . 22
.  0  .  . 23      .  1  .  . 23                       0  .  .  . 23
7  1  5 12 24      7  0  5 12 24                       7  5  1 12 24
-------------------------------------------------------------------------------------
X1                X2                                   X3
C[i,13,t]        I cannot use it                       C[i,12,t]
z = (7,1,5,12)                                         z = (7,5,1,12)
-------------------------------------------------------------------------------------
```

I showed maneuver from X1 to X3 in 13 moves. After these 13 moves, we again know what tiles are in @16,@17,@18,@19. So we can use X3. We have the following:

dist(C[i,13,t]; (7,1,5,12)) ≤ 13 + dist(C[i,12,t]; (7,5,1,12)).

In MTM metric, from any X1 we can reach 4! * 16 = 384 X3. One of 384 is X1.
To use this (if it is worth to be used), we need to use arrays instead of bitvectors (that is, 8x more memory). Also, for all possible 0≤i,j<16 and all 24 possible permutations of 4 tiles, we can precompute minimal number of moves in maneuver.

Update: we can do the following. We can go from X1 to X3 in three moves. After this, we reach one of quadruples z=(7,5,p,12); 1≤p<20; p is not in {7,5,1,12}. So we can use in the case on diagram 11:

dist(C[i,13,t]; (7,1,5,12)) ≤ 3 + max(dist(C[i,14,t]; (7,5,p,12)); 1≤p<20; p is not in {7,5,1,12}).

I think this is roughly what Rokicki used in his Fifteen Puzzle "coset" solver.

``` -----------------------------------------------------
11. Prepass. Subproblems C[i, j, t];
0≤j<16; i = const; t = const.
-----------------------------------------------------
.  .  .  . 20      .  .  .  . 20       .  .  .  . 20
.  .  .  . 21  1U  .  .  .  . 21  1LD  .  .  .  . 21
.  .  .  . 22  =>  .  .  .  . 22   =>  .  .  .  . 22
.  0  .  . 23      .  1  .  . 23       .  1  0  . 23
7  1  5 12 24      7  0  5 12 24       7  5  . 12 24
-----------------------------------------------------
X1                X2                   X3
C[i,13,t]        I cannot use it       C[i,14,t]
z = (7,1,5,12)                         z = (7,5,p,12)
-----------------------------------------------------
```

We again can precompute all maneuvers from possible X1 to possible X3. In STM metric, there are 6 three-move maneuvers, 4 four-move nontrivial maneuvers (without three-move maneuver as substring) and two five-move nontrivial maneuvers to precompute. In MTM metric, we have 96 three-move, 64 four-move and 32 five-move maneuvers to precompute.

Adjacency of the subproblems C[i, j, t] in the subproblem graph (this is what I actually used instead of the coset graph in Rubik's cube coset solver) will be simpler.

Let t_moves[@i, t, m] = q iff we can made move m in fringe state from t-set in which slot is in @i, and we will get fringe state from q-set after this:

```  t_moves[@i, t, m] = q
is equivalent to
for any fringe state X in t-set, X.where[0] = @i: ApplyMoves(X, m) in q-set.
```

Let m' be inverse move of m. Then t_moves[moves[@i, m], t_moves[@i, t, m], m'] = t.

Each subproblem C[i, j, t] can be combined with single move m in moves[@i] and lead to another subproblem C[m, j, t_moves[@i, t, m]]. Thus we have:

C[i, j, t] ≤ 1 + C[m in moves[@i], j, t_moves[@i, t, m]].

Added: we can maintain subproblem graph in which each subproblem E[i, t] is single vertex. This graph will be of size 20 * 6,375,600 = 127,512,000. In the inequality for adjacency of the C[] subproblems, j does not change (see previous paragraph); so we can write E[i, t] ≤ 1 + E[m in moves[@i], t_moves[@i, t, m]]. Propagation step of solver will use this inequality.

Note: I'll implement this as I have free time. However, if you see something unclear, strange, wrong or totally impossible in my sketch, I'll highly appreciate any feedback about it, as well as any other feedback.

Bulat
<my nickname> at_ymail_point_com.

### "Coset" solver for 5x5 "fringe region"

Clearly it is not very good description; also, I almost sure it contains many typos, pitfalls and errors. Maybe it even makes no sense at all. Anyway, I'll do this.

I want to say that I totally gave up the case. First time when I tried to implement this, it seemed to me that it is working until I found first errors. Then I attempted to save idea by some minor corrections, but finally decided to put it off for a while. Recently I returned to this; however, now I cannot even understand fully what I described here. It seems that I just made things more complicated than they are. I would like to take back this comment to rethink it, but I cannot once it has replies. So sorry for messing up.

- Bulat

### Distributions

```[4]                        [5]                   [6]                         [7]
depth   count      total   depth count total     depth   count      total    depth count total
------------------------   -----------------     ------------------------    -----------------
0        19         19       0    16    16       0        19         19        0    16    16
1         7         26       1     3    19       1         7         26        1     3    19
2        28         54       2     6    25       2        28         54        2     6    25
3       112        166       3    24    49       3       112        166        3    24    49
4       363        529       4    72   121       4       363        529        4    72   121
5       588       1117       5    64   185       5       486       1015        5    64   185
6      1468       2585       6   102   287       6      1418       2433        6   102   287
7      4180       6765       7   268   555       7      3572       6005        7   268   555
8     10228      16993       8   492  1047       8      9112      15117        8   492  1047
9     19882      36875       9   721  1768       9     16572      31689        9   721  1768
10     46279      83154      10  1215  2983      10     41716      73405       10  1215  2983
11    100183     183337      11  1907  4890      11     84765     158170       11  1907  4890
12    211079     394416      12  2454  7344      12    191020     349190       12  2454  7344
13    408390     802806      13  3707 11051      13    354120     703310       13  3707 11051
14    814120    1616926      14  4296 15347      14    751908    1455218       14  4296 15347
15   1556767    3173693      15  6076 21423      15   1400714    2855932       15  6076 21423
16   2862225    6035918      16  6725 28148      16   2711894    5567826       16  6725 28148
17   5109752   11145670      17  8972 37120      17   4727209   10295035       17  8972 37120
18   8868574   20014244      18  9090 46210      18   8521147   18816182       18  9090 46210
19  15002819   35017063      19 10382 56592      19  14368101   33184283       19 10382 56592
20  24025276   59042339      20  9742 66334      20  23509451   56693734       20  9742 66334
21  38012700   97055039      21  9519 75853      21  37023773   93717507       21  9519 75853
22  56828214  153883253      22  7066 82919      22  55886318  149603825       22  7066 82919
23  82840943  236724196      23  5250 88169      23  82214009  231817834       23  5250 88169
24 113458899  350183095      24  3000 91169      24 112599111  344416945       24  3000 91169
25 151465397  501648492      25  1398 92567      25 151875729  496292674       25  1398 92567
26 189735852  691384344      26   381 92948      26 190893121  687185795       26   381 92948
27 226145476  917529820      27    66 93014      27 229198124  916383919       27    66 93014
28 253527229 1171057049      28    10 93024      28 258819323 1175203242       28    10 93024
29 265281609 1436338658                          29 269347065 1444550307
30 259624015 1695962673                          30 268129472 1712679779
31 230204095 1926166768                          31 230103730 1942783509
32 189615192 2115781960                          32 193742603 2136526112
33 138000172 2253782132                          33 130295381 2266821493
34  89599195 2343381327                          34  87299750 2354121243
35  48932027 2392313354                          35  41839049 2395960292
36  21570608 2413883962                          36  19783979 2415744271
37   7139605 2421023567                          37   5467488 2421211759
38   1515297 2422538864                          38   1380041 2422591800
39    181406 2422720270                          39    128665 2422720465
40      7671 2422727941                          40      7522 2422727987
41        59 2422728000                          41        13 2422728000
```

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

### Results from analysis of subgoals of the 5x5

Below is short results for various subgoals. I've included in this table also known 80s* and 43m* results for 4x4 subpuzzle and 84s* result for 5x3 subpuzzle. Also, subpuzzle "1d" was calculated several months ago using splitting the whole space to classes by position of blank square. Analysis took about four or five days. I've not checked results and did not analysis in MTM metric for this pattern.

``` ------------------------------------------------------------------------------
0-based goal (for reference)
------------------------------------------------------------------------------
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
------------------------------------------------------------------------------
id         Fixed tiles            Pattern tiles            Space  God's number
------------------------------------------------------------------------------
1a                   -           20 21 22 23 24      127,512,000  74s / 38m
1b                   -        19 20 21 22 23 24    2,422,728,000  84s / 41m
1c                   -         4 20 21 22 23 24    2,422,728,000  86s / 41m
1d                   -     14 19 20 21 22 23 24   43,609,104,000  91s
1e                   -        14 18 19 22 23 24    2,422,728,000  81s / 40m
------------------------------------------------------------------------------
2a      20 21 22 23 24               4  9 14 19        1,860,480  58s / 31m
2b   15 20 21 22 23 24      4  9 14 16 17 18 19    3,047,466,240  73s / 39m
2c   19 20 21 22 23 24      4  9 14 15 16 17 18    3,047,466,240  74s / 40m
2d   19 20 21 22 23 24      3  4  8  9 13 14 18    3,047,466,240  74s / 38m
2e    4 20 21 22 23 24      9 14 15 16 17 18 19    3,047,466,240  72s / 39m
2f   14 18 19 22 23 24      4  9 15 16 17 20 21    3,047,466,240  94s / 51m
------------------------------------------------------------------------------
3a        4, 9, 14..24      4x3 subpuzzle            239,500,800  53s / 33m
3b    4, 9, 14, 19..24      4x4 subpuzzle     10,461,394,944,000  80s / 43m
3c              15..24      5x3 subpuzzle        653,837,184,000  84s
------------------------------------------------------------------------------
```

It is possible that there is some sequence that leads to <208s or <109m that I overlooked. Also, there may be some other "better" sub-puzzles. But in any case this technique cannot give much better upper bounds.

### "1d" pattern from the table above

Below is distance distribution from my old analysis for 1d pattern. The location of blank tile in the goal state does not matter, so there are 18 positions at depth 0.

``` "1d" pattern (one of 18 goals)
.  .  .  .  .
.  .  0  .  .
.  .  .  . 14
.  .  .  . 19
20 21 22 23 24
```
```------------------------------------------------------------------------------
depth         count            total     depth         count            total
------------------------------------------------------------------------------
0              18               18      46   1,197,389,792    7,107,927,315
1               7               25      47   1,373,767,749    8,481,695,064
2              13               38      48   1,506,849,719    9,988,544,783
3              24               62      49   1,683,927,226   11,672,472,009
4              51              113      50   1,794,517,697   13,466,989,706
5             113              226      51   1,951,818,062   15,418,807,768
6             214              440      52   2,018,826,180   17,437,633,948
7             396              836      53   2,135,398,217   19,573,032,165
8             699            1,535      54   2,141,529,324   21,714,561,489
9           1,266            2,801      55   2,200,846,865   23,915,408,354
10           2,316            5,117      56   2,137,433,915   26,052,842,269
11           4,220            9,337      57   2,131,967,454   28,184,809,723
12           7,414           16,751      58   2,002,222,834   30,187,032,557
13          13,104           29,855      59   1,935,777,559   32,122,810,116
14          22,737           52,592      60   1,755,128,202   33,877,938,318
15          39,521           92,113      61   1,642,435,755   35,520,374,073
16          67,033          159,146      62   1,435,226,940   36,955,601,013
17         113,492          272,638      63   1,297,918,025   38,253,519,038
18         187,279          459,917      64   1,090,760,458   39,344,279,496
19         309,999          769,916      65     951,351,409   40,295,630,905
20         499,017        1,268,933      66     767,087,235   41,062,718,140
21         804,525        2,073,458      67     643,757,638   41,706,475,778
22       1,259,364        3,332,822      68     496,456,555   42,202,932,333
23       1,976,016        5,308,838      69     399,807,261   42,602,739,594
24       3,008,262        8,317,100      70     293,892,832   42,896,632,426
25       4,596,876       12,913,976      71     226,415,639   43,123,048,065
26       6,803,538       19,717,514      72     157,996,966   43,281,045,031
27      10,108,076       29,825,590      73     116,005,937   43,397,050,968
28      14,533,741       44,359,331      74      76,435,205   43,473,486,173
29      20,996,651       65,355,982      75      53,195,468   43,526,681,641
30      29,336,638       94,692,620      76      32,837,749   43,559,519,390
31      41,229,382      135,922,002      77      21,526,203   43,581,045,593
32      56,000,248      191,922,250      78      12,340,891   43,593,386,484
33      76,608,910      268,531,160      79       7,555,858   43,600,942,342
34     101,229,033      369,760,193      80       3,971,223   43,604,913,565
35     134,915,368      504,675,561      81       2,233,400   43,607,146,965
36     173,567,368      678,242,929      82       1,055,984   43,608,202,949
37     225,554,785      903,797,714      83         535,677   43,608,738,626
38     282,698,235    1,186,495,949      84         221,057   43,608,959,683
39     358,441,239    1,544,937,188      85          96,988   43,609,056,671
40     437,811,873    1,982,749,061      86          32,722   43,609,089,393
41     541,655,685    2,524,404,746      87          11,314   43,609,100,707
42     644,602,478    3,169,007,224      88           2,682   43,609,103,389
43     778,090,116    3,947,097,340      89             556   43,609,103,945
44     901,860,241    4,848,957,581      90              50   43,609,103,995
45   1,061,579,942    5,910,537,523      91               5   43,609,104,000
------------------------------------------------------------------------------
```

Below are all 5 antipodes.

``` 1) 24 22 23 21 20 14  -  -  -  - 19  -  -  -  -  -  -  -  -  -  -  -  -  -  0
2) 24 23 22 21 20 14  -  -  -  - 19  -  -  -  -  -  -  -  -  -  -  -  -  -  0
3) 19 23 21 22 20 24  -  -  -  - 14  -  -  -  -  -  -  -  -  -  -  -  -  -  0
4) 19 22 23 21 20 24  -  -  -  - 14  -  -  -  -  -  -  -  -  -  -  -  -  -  0
5) 19 23 22 21 20 24  -  -  -  - 14  -  -  -  -  -  -  -  -  -  -  -  -  -  0
```

### Fringe pattern of the 5x5 puzzle

One possibility is to do full analysis of the fringe pattern of 5x5 puzzle. Note that state space of the fringe pattern is rough equal to state space of the 4x4 Fifteen Puzzle.

```Fifteen Puzzle        Fringe pattern
0  1  2  3  #          0  .  .  .  4
5  6  7  8  #          .  .  .  .  9
10 11 12 13  #          .  .  .  . 14
15 16 17 18  #          .  .  .  . 19
#  #  #  #  #         20 21 22 23 24

16!/2 ~ 1,046 * 10^13  25!/15! ~ 1,186 * 10^13
```

I tried to write optimal solver for fringe pattern using two 5-tile pattern databases (one for tiles 20, 21, 22, 23, 24, and other for tiles 4, 9, 14, 19, 24). Actually, only one lookup table was used because of symmetry.

I used non-additive PDBs and so was able only to take maximum of two values. I will give outputs of three runs after a few minutes below. Only in small number of random instances, I was able to find optimal solution in less than hour.

It is possible to use additive pattern databases (for example, one for tiles 20, 21, 22, 23, 24, and other for tiles 4, 9, 14, 19). But this heuristic is still poor. Probably it is because it not counted many moves; only 9 out of 24 tiles included in fringe pattern. 4x4 (Fifteen Puzzle) additive PDB solver works much better because all 15 tiles included in PDBs.

```[Fringe optimal solver, attempt 1]
3 23 21 19 13 10 15  1 12 22  8 18  0 24 16 17 20  4  5  9 14 11  2  6  7
depth  48...
nodes = 27
depth  49...
nodes = 62
depth  50...
nodes = 371
depth  51...
nodes = 1319
depth  52...
nodes = 4212
depth  53...
nodes = 14658
depth  54...
nodes = 40534
depth  55...
nodes = 134287
depth  56...
nodes = 347116
depth  57...
nodes = 1157465
depth  58...
nodes = 2880351
depth  59...
nodes = 9536163
depth  60...
nodes = 23164297
depth  61...
nodes = 76358209
depth  62...
nodes = 182914976
depth  63...
nodes = 602371117
depth  64...
```
```[Attempt 2]
13  8 20  7 21  9 10 17  2 16 15 11  1 22  4 24 19 12  6 18 14  5  0  3 23
depth  54...
nodes = 15
depth  55...
nodes = 33
depth  56...
nodes = 177
depth  57...
nodes = 449
depth  58...
nodes = 1949
depth  59...
nodes = 5568
depth  60...
nodes = 19892
depth  61...
nodes = 56305
depth  62...
nodes = 190509
depth  63...
nodes = 536050
depth  64...
nodes = 1718821
depth  65...
nodes = 4821318
depth  66...
nodes = 15051416
depth  67...
nodes = 42344947
depth  68...
nodes = 129777588
depth  69...
nodes = 365426059
depth  70...
```
```[Attempt 3]
18 19 23 22 20 24  8 16 21  4  3 11 17  7  2 13 12 14 15 10  1  5  0  9  6
depth  64...
nodes = 249
depth  65...
nodes = 516
depth  66...
nodes = 5967
depth  67...
nodes = 12612
depth  68...
nodes = 104659
depth  69...
nodes = 242560
depth  70...
nodes = 1648562
depth  71...
nodes = 4348044
depth  72...
nodes = 24424158
depth  73...
nodes = 69478325
depth  74...
nodes = 337937146
depth  75...
```

Currently I am running "coset" solver for fringe pattern. At the time of writing this post, I have 19 128s "cosets" and 11 64m "cosets". So upper bound for fringe tiles in STM is 128s, and in MTM is 64m. Therefore, 5x5 puzzle can be solved in at most (128s + 80s = 208s) single-tile moves or in at most (64m + 42m = 106m) multi-tile moves. I hope to lower these values in worst case to 200s and 100m respectively.

### 104m, 206s

Any 5x5 instance can be solved in 104m/206s. Fringe tiles can be solved in 62m/126s.

### 103m, 204s

Fringe tiles can be solved in 61m/124s. The whole 5x5 can be solved in at most 103m/204s.

### 102m, 202s

If my solver works correctly then fringe pattern can be solved in 122s or 60m. 5x5 puzzle can be solved in 122s+80s=202s or in 60m+42m=102m.

### Quick question

Do you think your software harness will be in a position to derive the actual diameter in the MTM for the 5x5 puzzle (just as we know it is 43m for the 4x4)? Just asking that is all - or can we just expect continued improvements - which is in itself great BTW.

### 44 upper bound for diameter

As Rokicki pointed out, I have not actually proved that the diameter of the MTM 15 puzzle graph is 43. Rather, I proved that no (solvable) position requires more than 43 moves for a goal state where the empty square is in a corner. It easily follows that 45 is an upper bound for the diameter of the graph, and it appears to me it can also be deduced that 44 is an upper bound, using the argument below. (Of course, by 15 puzzle graph, I am here only referring to a connected graph of positions reachable from a given position. The other half of the complete 15 puzzle graph is isomorphic to it.)

From any 15 puzzle position, call this position A, we can get to a position where the empty square is in a corner in at most 2 moves. Call this position B. Since no position requires more than 43 moves to reach position B, any position C can reach B in at most 43 moves. So we can also get from B to C in 43 moves. So to get from A to C, at most 2 + 43 = 45 moves are required.

Note that among the 16 positions that are 43 moves from B, there is at most one of these that is adjacent to any other one. Since there are 3 choices of vertical moves and 3 choices for horizontal moves, there must be at least two vertical moves and at least two horizontal moves that get us to a position 42 moves from B. Since optimal paths in MTM alternate between vertical and horizontal moves, the first move and last move in a 43-move optimal path must be in the same direction (using the term "direction" to mean merely whether the move is horizontal or vertical). Thus, it follows that there are optimal paths to B ending in either horizontal or vertical moves. Thus, we can choose a path that gets us a cancellation with the last move from A to B.

Hence, we can go from A to B in two moves, and then go from B to C in 43 moves starting with a move in the same "direction" as the last move goint from A to B. Since we are guaranteed to cancel at least one move, the total moves required to go from A to C is at most 43 + 2 - 1 = 44 moves. Since A and C were arbitrarily chosen positions, 43 is an upper bound for the diameter of the graph.

Note: I note that I've used the term empty square rather than blank square. In the paper Efficiently Searching the 15-Puzzle, the authors Culberson and Schaeffer use the term empty cell to refer to the position lacking an actual tile, and the term blank tile to refer to a tile we don't care about putting in any particular position. For example, for the fringe pattern database for the 15 puzzle, we can think of the puzzle as having an empty cell, 7 numbered tiles, and 8 blank tiles. To avoid any confusion, I prefer not to use the term blank when referring to the empty square.

### Diameter is actually 43 after all

I am now confident the diameter of the 15 puzzle graph is indeed 43.

First consider a goal state with the blank along an edge (but not in a corner). WLOG we can choose the goal state:

``` 1  2  3  4
5  6  7  8
9 10 11 12
13 14  x 15
```

This is one move away from the standard goal state, so one could solve any given configuration with respect to the standard goal state, and make one additional move to reach this goal state. If it takes less than 43 moves to reach the standard goal state, then adding one more move will still keep the solution at less than or equal to 43 moves. Otherwise, the configuration must be one of the 16 antipodes for the standard goal state. We can choose a solution for any of these that start and end with a horizontal move. This means the we get a cancellation with the move that converts the standard goal state to this goal state. Thus, we still have that 43 moves suffice.

So for any goal state with the empty square in a corner or along an edge, at most 43 moves are needed. Using inverse maneuvers, any initial state with the empty square in a corner or along the edge be manipulated to any legal goal state in at most 43 moves. So the only case left that could require 44 moves is if both the initial state and the goal state have the empty square somewhere among the four center squares.

So now we consider the case with both the initial state and the goal state having the empty square in the center part. WLOG, we choose the goal state to be:

``` 1  2  3  4
5  6  7  8
9 10  x 12
13 14 11 15
```

This goal state is two moves away from the standard goal state. Any configuration that is 41 or less moves from the standard goal state can obviously reach this goal state in at most 43 moves. The remaining configurations where the empty square is also one of the four central squares can be all be checked by running an optimal solver that uses this special goal state. I am confident I have run an optimal solver for all these configurations, and none required more than 43 moves. So no two configurations with the empty square in the center part are more than 43 moves apart.

As we have now covered all possibilities, there are no two legal configurations of the 15 puzzle that are more than 43 moves apart.

### 43m* analysis

I've interested in how you done this analysis. In particular, is there full distance distribution or you proved that there are no tile configurations at distance >43m? If there is distribution, how many configurations there are at distance 42m* from solved?

### We performed a complete bread

We performed a complete breadth-first search of a reduced form of the puzzle space. From this analysis, we could conclude no position of distance 44 or greater in multitile metric could exist. The analysis also provided us with tens of thousands of candidate positions for positions of 42 or more moves (MTM). Our analysis indicated no other positions of 42 or more moves were possible. We solved all candidate positions with an optimal solver, thus identifying all 42m* and 43m* positions. The number of 42m* positions is in the thousands.

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