Twenty-Four puzzle, some observations

Hello all. I am new on this great forum. My first post is about Twenty-Four puzzle, larger version of classic Fifteen. I walked around sliding tile puzzles for quite some time. At some point I decided that what I have is too much for me alone, but enough to write about it here.

Many small puzzles have been solved long ago. There is some information in OEIS: A151944 (about MxN puzzles), A087725 (about NxN puzzle). AFAIK largest solved STP is 4x4 puzzle (classic Fifteen). It was known that 80 single-tile moves required and sufficient, and recently Bruce Norskog wrote on this forum about 43 multi-tile moves.

Next NxN puzzle is 5x5 "Twenty Four". The number of states is 25!/2 = 7,755,605,021,665,492,992,000,000. It is too many to do full analysis in near future. I searched for lower and upper bounds. In 1996, Richard E. Korf and Larry A. Taylor in paper "Finding Optimal Solutions to the Twenty-Four puzzle" showed that 114 single-tile moves are needed. In 2000, Filip Karlemo and Patric Ostergard showed that 210 single-tile moves are sufficient. I was not able to find any better bounds on the web.

Also, it turned out that in most cases single-tile metric (STM) was used by researchers, and probably there is no known upper and lower bounds for 5x5 in multi-tile metric (MTM) yet.

As for lower bound in STM, there is puzzle state with Manhattan distance of 116 moves. Let goal state be the following:

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

Then the following instance has manhattan heuristic of 116 moves:

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

Moreover, it seems like I can show that the following "turned 180-degree" state requires at least 140 STM. So lower bound in STM metric should be 140 moves.

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

To prove this, I used good heuristic developed by Ken'ichiro Takahashi (takaken). Maybe I'll outline idea of this heuristic in separate topic later. However, there is an explanation written by the author (unfortunately, it is in Japanese language) on Takahashi's web site. He developed new Walking Distance (WD) and implemented it in his "15 puzzle Optimal solver". I just used his ideas with 5x5 puzzle. WD heuristic gives for "turned 180-degree" configuration lower bound of 140 moves.

Also the same "turned 180-degree" puzzle configuration requires at most 156 STM. Note that we can turn the whole box with all tiles 180 degrees and get goal state. If we first turn box 90 degrees clockwise and then again 90 degrees clockwise, effect should be the same. But if we turn goal 90 degrees we get much simpler configuration that can be solved optimally in 78 STM. Then we can perform this move sequence twice to turn 180 degrees and so get 78+78=156 moves. So optimal solution for this particular instance is between 140 STM and 156 STM.

4x4 STM God's number is 80, and "turned 180-degree" instance is very close to hardest case (78 STM); so I believe God's number for 5x5 puzzle will be about 160 STM.

I wrote program that searches for suboptimal solutions for sliding tile puzzles. On Jaap's website, he describes multi-phase algorithm to solve large puzzles. My program uses his algorithm with some additional improvements. I cannot write about it in this topic for reasons of brevity. Shortly, this is four-stage suboptimal solver.

About 2,000 random instances have been solved in STM metric with time limit of 10 seconds per instance. Minimal length was 77 moves, maximal length was 152 moves, average length was 118.4 moves.

About 2,000 random instances have been solved in MTM metric with the same time limit of 10 seconds. Minimal length was 47 moves, maximal length was 85 moves, and average length was 69.4 moves.

About 1,000,000 of random 5x5 instances have been solved in 160 STM or less. (Search stops when solution in 160 moves or fewer found). All instances were solved; minimal length was 79 moves, average length was 138.1 moves, and average time per instance was about 5 milliseconds.

Finally, about half million random instances have been solved in 90 or fewer multi-tile moves. Minimal length was 51 moves, average length was 85.4 moves, and average time was about 7 milliseconds.

My solver is four-stage. It is possible to create three-stage solver. For example, first phase solves five tiles in first row, second phase solves first column, and third phase is 4x4 puzzle and can be solved with IDA*.

Many thanks to this forum for its existence.

Many thanks to Jaap for his patience. I received a lot of help from him, as well as on his website.

The Walking Distance heuristic was developed by Ken'ichiro Takahashi.

Thanks to Google Translate service. Neither English nor Japanese is not my native language.

Comment viewing options

Optimal 5x5 solver?

I've taken the ideas you've outlined and used them to implement
the most straightforward 24 optimal solver using IDA* and the
WD metric.

[I make no assertion that it is by any means a *practical* optimal
solver; random positions may well take it quite a long time.]

I've entered the position you give above, and it asserts that there
are no solutions of length 142 or less for the position you list.

This means that the lower bound should actually be *144* at this
point.

I'll let it run for a while and see if it can do any better.

Invert Distance

There is one more special heuristic implemented in Takahashi's solver, Invert Distance heuristic. I did not mention it before because it cannot give better lower bound; its maximal value is 138 with Twenty-Four puzzle. But it probably can be used in optimal solver.

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

We should count all inversions. If i < j and tile i is after tile j, then it is inversion. In given example, InvCount = 105.

Any allowed STM move cannot change InvCount value by more than 3. Any horizontal move never changes InvCount, and vertical move can change InvCount by -3, -1, +1 or +3. So we can divide InvCount by 3 and get minimal number of vertical moves required to go to goal position. 105 / 3 = 35 vertical moves.

In the same way we can count inversions by columns and get minimal number of horizontal moves. In given example, it is 35 also. So lower bound is 35 + 35 = 70 STM.

If InvCount value does not divide by 3 then we can add remainder. If remainder is 1 then we can add 1 because even after InvCount / 3 moves we still cannot reach goal. If remainder is 2 then we can add 2 because it is not possible to make change +-2 in only one move.

So actual formula is InvertDistance = InvCount / 3 + InvCount % 3.

In Twenty-Four case, we can divide by 4 because all possible changes are -4, -2, 0, +2, +4. However, it seems that cannot simply add remainder; if there is remainder then we can only add 1.

Takaken solver also uses the following pattern databases:

```AAAB  BCCC
ABBC  ABBC
ABCC  ABBC
BCC   AAA
```

Each of these databases has size 12,108,096.

Thanks for verification

Thanks for independent verification. BTW, how you implemented your solver? Do you use associative array to store God's database or you was able to calculate indices?

Done through 144; bound now 146

No solution of length 144. So the bound is 146. My program is
working on that; I do not know how long it might take.

I used a sparsely indexed array; I ended up using 711MB for what
should only require 62MB. But since it's not going to fit in
cache anyway, spending more cycles to index it better may not
actually help all that much.

But you are correct; indexing of the WD database is not trivial.

Done through 146; new bound is 148

No solution found at distance 146.

I don't think the program will finish a ply-148 search, but in any case, if my optimal solver is correct, then the new bound should be 148.

Great jump

Did not expect this so soon and with only one WD heuristic. Of course each next ply will be more difficult. Can I ask how quicky grows the number of nodes?

I combined results in MTM metric with those obtained by Bruce Norskog. 9 "fringe" tiles can be solved in at most 38+31=69m, and remaining tiles can be solved as Fifteen puzzle in at most 43m (if all was correct). So upper bound in MTM metric should be 112m.

Keep thinking about lower bound in MTM. Of course one can divide 148 by 4 as one move cannot touch more than 4 tiles. But 37m for 5x5 is not good when we know 43m for 4x4.

After first move, there is 4 choices for each next move. Inequality 8*4^x<25!/2 is true for x<40. It is better that dividing WD by 4 but also not so good.

Slow program

I'm not counting nodes, unfortunately. :-( I can give you some times (I just added time measurement, and restarted, so it has to redo some work):

140-ply 0.22s
142-ply 9.88s
144-ply 268s

It is not impossible that there is a bug in my program, but I've been testing it on some [easier] instances and it seems to be okay.

I think 146-ply will be done (again) in another hour or so. The factor appears to be about 27 or so, so I might be able to finish 148-play in a few days (or find a distance-148 solution).

Korf's "Disjoint Pattern Database Heuristics" [2001] paper seems to report better results with a pretty simple set of pattern databases; he's got what looks like a reasonably practical optimal solver even back then. He solved 50 random instances; my WD-only solver can't even solve one (in the time I've allotted it). It looks like the WD metric is extremely effective *except* it has a blind spot that needs to be covered by an additional metric or three. This is in line with your suggestion to add a few more metrics.

Anyway, I'll be gone for a couple of weeks so my time on this problem will probably come to an end soon.

146 time

146-ply took 8235 seconds.

So, I expect 148-play to finish in *about* three days. I'll have to decide if I want to commit that machine for that length of time.

148 done

148 done. Assuming solver is correct, new bound is 150.

Of course you can stop your s

Of course you can stop your solver any time :) I'll try to write my own solver, I did not yet. Anyway, thanks you.

Very cool

How hard do you think it would be to calculate an optimal
solution to the 180 degree flipped position you show?

This is very interesting; the walking distance metric appears
to be fairly old (the program using it has a date of 2002) yet
this is the first I've heard of it (and I've been very
interested in the 24 puzzle for some time).

Very nice results!

180 degree flipped position

I tried how it is possible to rotate/reflect box with tiles. Unfortunately, in 4x4 case it is impossible to solve turned 90 degree:

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

But I tried to swap tiles 14 and 15 in position above and takaken's solver gave me 39 moves. Flipped 180 position requires 78 moves; that is, twice more. It was strange for me.

```  4  8 12  0
3  7 11 14
2  6 10 15
1  5  9 13
Optimal solution is 39moves.

13  9  5  1
15 10  6  2
14 11  7  3
0 12  8  4
Optimal solution is 39moves.
```

In 3x3 puzzle, flipped-180 position requires 28 moves, and turned-90 position requires 14 moves.

``` 0 8 7     3 6 0
6 5 4     2 5 8
3 2 1     1 4 7
28s*      14s*
```

This strange relationship observed also in 2x2 puzzle. I cannot understand it. Maybe it is simplest way indeed, and this is true for any NxN puzzle?

Square roots of permutations?

I'll call the X-degree flipped NxN goal configuration "NxN_X". For example, 5x5_90 is 90-degree flipped 5x5 goal.

I tried to get solution in 150s, 152s or 154s for 5x5_180 using some intermediate state.

```[1]
4  9 14 19 24
3  8 13 18 23
2  7 12 17 22
1  6 11 16 21
0  5 10 15 20
5x5_90
square root of 5x5_180
78s*
```
```[2]
4  9 14 19 24
3 16 11  6 23
2 17 12  7 22
1 18 13  8 21
0  5 10 15 20
square root of 5x5_180
80s*
```
```[3]
0  1  2  3  4
5 18 17 16  9
10 13 12 11 14
15  8  7  6 19
20 21 22 23 24
"inner3x3-flipped180"
42s*
```
```[4]
24 23 22 21 20
19  6  7  8 15
14 11 12 13 10
9 16 17 18  5
4  3  2  1  0
"outer-flipped180"
120s*
```

Configuration [1] was used to find 156s solution. [2] can be used to find 160s solution. [3] and [4] can be combined to get 162s solution; it is possible to save four moves and still get 158s; that is, [1] and [2] gives better solutions.

Without any proof, it seems like square roots of permutations of tiles can be used to get good solutions. Maybe even there is something like square root of "5x5_180" with solution in 77s*, 76s* or 75s* and corresponding solution in 154s, 152s or 150s for "5x5_180". I guess there is beautiful mathematical explanation of this but I cannot find yet.

By the way, "6x6_180" position requires at most 282s. 16 inner tiles can be "flipped" in 96s, and outer tiles can be cycled in 190s. So there is solution in 286s. However, flipping inner 4x4 maneuver (see below) starts with 2U 2L and ends with 2R 2D; it is possible to include these four moves in 190s cycling maneuver and get 282s solution.

``` 0  1  2  3  4  5
6 28 27 26 25 11
12 22 21 20 19 17
18 16 15 14 13 23
24 10  9  8  7 29
30 31 32 33 34 35
```
```180-Flipping inner 4x4. Before applying maneuver, blank tile should be in square 0.
(96s)
2U 2L 1D 1R  2U 1L 2D 2L  1U 1R 1D 1L
2U 1R 1U 1R  2D 1L 1U 1R  2D 1L 1U 1L
1U 1R 1U 1L  1D 1R 1U 1R  2D 2R 1U 1L
1U 1L 2D 1L  1U 2R 1D 3L  1U 4R 1D 1L
1D 1L 1U 1L  1U 2R 2D 3L  1U 1R 1D 1L
2U 3R 1D 2L  1U 1R 1D 2R  2D
```

Some corrections

In 6x6 sliding tile puzzle, 16 inner tiles can be turned 180 degrees in 92 moves. This transformation is equivalent to the following 5x5 configuration:

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

I've used suboptimal solver to get solution in 96s in my earlier post. Optimal solution to configuration above seems to be 92s*.

```(92s*, 39m) 2L 4U 2L 3D 2RU 1L 2D 1R 2U 1L 2D 1RDLU 2R 3ULDRULDRULDRULDRULD 1RD 3R
```

Outer tiles in 6x6 can be turned 180 degrees in 190s, so solution is 190s+92s=282s; however, six moves can be saved. Solution above begins with 2L and ends with 3R; we can include these moves in 190s maneuver that solves outer tiles and finally get 276s suboptimal solution for 6x6 turned 180.

``` 35 34 33 32 31 30
29 28 27 26 25 24
23 22 21 20 19 18
17 16 15 14 13 12
11 10  9  8  7  6
5  4  3  2  1  0
(276s, 76m)
5RD                                                                   // preparation moves
2L 4U 2L 3D 2RU 1L 2D 1R 2U 1L 2D 1RDLU 2R 3ULDRULDRULDRULDRULD 1RD   // flipping inner tiles
2L 5URDLURDLURDLURDLURDLURDLURDLURDLURD                               // solving outer tiles
```

Turned 90-degree 6x6 configuration requires 141s*. This was found using manhattan solver. I'll give one of 120914 141s* solutions.

```34591 (141s*, 35m) 5LDR 4UL 3DRU 2L 4D 3R 5U 4L 5D 4R 5ULDRUL 4DR 3UL 2DR 3UL 4D 5R 4U 5LDR
```

Repeating 90-degree rotation twice gives obviously 282s which is not optimal as we know 276s. So in arbitrary NxN puzzle, repeating twice 90-degree rotation does not necessarily lead to optimal solution.

The following position also requires 141s*. Outer tiles rotated clockwise, while inner tiles rotated counterclockwise.

``` 30 24 18 12  6  0
31 10 16 22 28  1
32  9 15 21 27  2
33  8 14 20 26  3
34  7 13 19 25  4
35 29 23 17 11  5
210 (141s*, 43m) 5UR 2D 1LU 3LDRULDR 2U 1RDLU 2L 1D 2RU 3LD 2R 1U 2RD 5LURDLURDLURDLURD
```

90-degree rotated positions seems to be very simple for manhattan solver. I've solved 7x7 puzzle 90-degree rotated position in 222s* using only manhattan heuristic. Here is last found solution.

``` 42 35 28 21 14  7  0
43 36 29 22 15  8  1
44 37 30 23 16  9  2
45 38 31 24 17 10  3
46 39 32 25 18 11  4
47 40 33 26 19 12  5
48 41 34 27 20 13  6
47040 (222s*, 49m) 6UR 5D 4LUR 5D 6LURDLU 5R 1DR 5D 6LURDLU 5RD 4LURDL 3UR 2DLUR 3DL 4URDLU 5RD 6LURD
```

The following position requires 226s.

```  6 13 20 27 34 41 48
5 36 29 22 15  8 47
4 37 30 23 16  9 46
3 38 31 24 17 10 45
2 39 32 25 18 11 44
1 40 33 26 19 12 43
0  7 14 21 28 35 42
369798 (226s*, 57m) 6L 1D 5R 3DLUR 4DLU 1LDRU 4RDL 3UR 2DLU 3RD 4L 3U 1LDR 2U 4RDL 2U 1L 3D 6RULDRULDRULDRULDRULDR
```

square roots

I like to think of a transformation (call it h) on a puzzle as the square root of another transformation (call it g) on the puzzle if h2 = g.

With an nxn tile puzzle, we can only compose a transformation with itself if that transformation leaves the empty square in the same place after the transformation as before. If we allow the transformations g & h to include rotating the puzzle (to compensate for certain changes in the location of the empty square), then the transformation that rotates the tile arrangement 90 degrees can be viewed as a square root of the transformation that rotates the arrangement of the tiles 180 degrees using my definition of square root. (The rotation of the puzzle as a whole will not be counted as a move even though we regard it as part of the transformation.)

I note that square roots by my definition are not generally unique. A transformation can have many square roots (or none at all). If h is a square root of g, and g has an optimal maneuver of M moves, then clearly M/2 is a lower bound for the number of moves required to perform the transformation h. But h may require more than M/2 moves. It might even require more than M moves.

Viewing the puzzle as just a permutation of 24 tiles and an empty square, the permutation that moves every pieces 90 degrees around the puzzle fits my definition of a square root. The problem is that moves on the 24 puzzle depend upon where the empty square is. So squaring a permutation is not generally possible simply by repeating the same moves. In fact, squaring a permutation may result in an illegal position. For instance, from the solved state (of the 24-puzzle), move tile #1, then tile #6. This produces the permutation (0,6,1) in cycle notation. As this is a 3-cycle, clearly (0,1,6) is both a square and a square root of (0,6,1), and similarly (0,6,1) is both a square and a square root of (0,1,6). But note that (0,1,6) is an unreachable position.

So while a square root can possibly provide a good solution for a position, one can not always arrive at a good solution this way. A given position does not necessarily have square roots. A square root as a pure permutation may not always be a reachable permutation. If a position does have one or more square roots, there is no guarantee these will be nearly twice as close to solved as the original, and may even be farther from solved.

Thanks for your explanation. Suppose we have transformation X that accepts tile arrangement with blank tile in the upper left corner, performs some number of disjoint 2-cycles of tiles and then rotates resulting tile arrangement 90 degrees clockwise. Let R90 be counterclockwise rotation of the whole puzzle (this is not counted as move). Then transformation X R90 performs only some number of disjoint 2-cycles of tiles. Then Y = X R90 X R903 performs "clean" 180-degree rotation of the whole tile arrangement because all 2-cycles that are performed by transformation X performs twice by transformation Y. That is, by your definition transformation X is square root of transformation that rotates tile arrangement 180 degrees.

I will give example of maneuver X for 4x4 tile puzzle.

```X = 3U 2L 1D 1L 1U 1R 3D 2R 3U 3L 2D 3R 2U 3L 3D 2R 3U 2L 3D

Initial state          After X          After X R90
0  1  2  3       8 12  4  0           0  1  3  2
4  5  6  7      13  9  5  1           4  5  6  7
8  9 10 11      14 10  6  3          12  9 10 15
12 13 14 15      11 15  7  2           8 13 14 11

(0-based goal)                    (0)(2,3)(8,12)(11,15)
```

By your definition, transformation T is square root of transformation that rotates nxn puzzle 180 degrees if it has the following properties:
1. T accepts any tile arrangement with blank tile in square (0;0) (i.e., upper left corner).
2. T leaves blank square in square (n-1;0) (upper right corner).
3. Transformation (T R90)2 does nothing.

If I understand you correctly, it seems like any such square root can be obtained using formula (T R90) = P, where P is product of some number of disjoint 2-cycles (however, 0 should not be in any of these cycles). In the example above, T = X, and (T R90) = (0)(2,3)(8,12)(11,15).

I tried to count all such square roots of transformation that rotates 5x5 puzzle 180 degrees. Let m be the number of disjoint 2-cycles that are performed by transformation T. We should select exactly (2*m) tiles from 24 existing physical tiles; there is 24! / (24 - 2 * m)! ways to do this. However, order of two tiles that are in the same 2-cycle does not matter so we can divide by 2m. Also, order of cycles does not matter so we can divide by (m!).
Finally, there is 24! / (24 - 2 * m)! / 2m / m! transformations that performs exactly m 2-cycles on 5x5 tile puzzle. It is possible to perform from 0 to 12 2-cycles on 5x5 puzzle.

``` m    # of ways to select exactly m disjoint 2-cycles of tiles
0    24!  /  (24 - 0)!   / 1      / 0!            =                  1
1    24!  /  (24 - 2)!   / 2      / 1!            =                276
2    24!  /  (24 - 4)!   / 4      / 2!            =             31,878
3    24!  /  (24 - 6)!   / 8      / 3!            =          2,018,940
4    24!  /  (24 - 8)!   / 16     / 4!            =         77,224,455
5    24!  /  (24 - 10)!  / 32     / 5!            =      1,853,386,920
6    24!  /  (24 - 12)!  / 64     / 6!            =     28,109,701,620
7    24!  /  (24 - 14)!  / 128    / 7!            =    265,034,329,560
8    24!  /  (24 - 16)!  / 256    / 8!            =  1,490,818,103,775
9    24!  /  (24 - 18)!  / 512    / 9!            =  4,638,100,767,300
10   24!  /  (24 - 20)!  / 1024   / 10!           =  6,957,151,150,950
11   24!  /  (24 - 22)!  / 2048   / 11!           =  3,794,809,718,700
12   24!  /  (24 - 24)!  / 4096   / 12!           =    316,234,143,225

total                                             = 17,492,190,577,600
```

So there is 17,492,190,577,600 such transformations T that (T R90) = P, where P is product of disjoint 2-cycles. We can change R90 by reflection through vertical axis (left-right). Let this reflection be S. Then (T S) = P, where P is product of disjoint 2-cycles. Calculations are the same, and we can get another 17,492,190,577,600 "square roots".

Not all these square roots are reachable puzzle arrangements, as you mention. It depends on reachability of tile arrangement that can be obtained by transformation R90 (or S, if we use reflection instead of rotation counterclockwise). In 5x5 puzzle, both R90 and S transformations lead to reachable tile arrangements; so we can perform only any even number of 2-cycles of physical tiles to preserve reachability of resulting square root; that is, 0, 2, 4, 6, 8, 10 or 12 2-cycles. Summing only these rows in table, we can find the number of reachable square roots. This is 8,792,390,355,904.

More square roots

These square roots can be thought of as of the class s f s f', where s is the square root and f is a 90 degree rotation of the whole board.

There's another class of square roots, of the form s t s' t', where t represents a flip of the board across the lower-left to upper-right diagonal.

This latter category numbers about 5! 10! 2^10 / 2 or about 223 billion.

I have checked hundreds of millions of examples from both categories, and none I have tested have a distance of less than 78. Also, I have not found a single instance from either category with a walking distance of less than 70.

clarify my definition of square root

Squaring (s t) does not produce (s t s' t'), so in my view (s t) would not be a square root of (s t s' t'). Of course, one can infer the same kind of distance relationships between (s t) and (s t s' t') as between (s f) and (s f)2. So such a position could be just as useful in determining a bound on the would-be "square" position as a square root (by my definition) would be.

I acknowledge that in the example of (s f), that (s f)2 is not exactly the same as (s f s f'), but both really represent the same intrinsic state of the puzzle (just that one has the puzzle in a non-standard orientation), so I am willing to think of (S f) as a sort of "virtual" square root of (s f s f').

It seems to me Tom's definition of "square root" would imply for a group puzzle, that every legal position of the puzzle would be a square root of the identity. I only would consider order-1 and order-2 positions to be square roots of the identity. I would consider a group puzzle to have an average of exactly 1 square root per position.

I've used the takaken solver

I've used the takaken solver before. I've used it to find out the single-tile metric distances for the multi-tile metric antipodes, for example. So I've been aware of the Walking Distance heuristic, but I didn't really know what it was exactly. So my thanks to stannic for providing additional information about the Walking Distance heuristic. I think I understand how to calculate it now.

multi-tile metric

I looked at your antipodes in MTM. First two of them is very symmetrical. First is reflection of goal about main diagonal, and second is rotation 180 of first. It is also strange for me.

Note that the first antipode

Note that the first antipode is the same as the solved state except rows and columns are transposed.

Now take the 2nd antipode, which is the same position rotated 180 degrees. Make one multitile move sliding the tiles numbered 13, 14, and 15 up. Now rotate the puzzle 90 degrees counterclockwise. The configuration should now look like this.

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

Now apply a 43-move maneuver that would solve the first antipode. This will transpose the rows and columns of the above configuration, giving this:

``` 4  8 12 15
3  7 11 14
2  6 10 13
1  5  9  x
```
Now rotate the puzzle back the normal way. Notice this is one move from solved. So we have solved the position in 1+43+1 = 45 moves. But note that the first antipode has no neighboring position that is also an antipode. So any legal multitile move from that position is a possible start for an optimal solution of that position. So we can choose a solution for which the first move cancels the move that slid the number 13, 14, and 15 tiles up. This gives a 43 move solution for the 2nd antipode.

Walking Distance

This post based on takaken's explanation. He worked with Fifteen puzzle, and his goal state was "null-terminated". So I also used null-terminated goal through this post.

For the following Fifteen instance, Manhattan distance heuristic value is only 3.

```  1  2  3  0
5  6  7  8
9 10 11 12
13 14 15  4
MD = 3, optimal solution 19
```

Note that all tiles are correctly placed in verticals (columns) but one tile moved from row 1 to row 4.

It is possible to create two sub-problems, one including vertical coordinates of tiles, and another including only horizontal coordinates of tiles. First, tiles 1,2,3,4 will be marked with "A", tiles 5-8 with "B", tiles 9-12 with "C", and tiles 13-15 with "D". In other words, tiles that should be in the same row will be marked with the same letter.

``` A A A
B B B B
C C C C
D D D A
"Vertical" subproblem
```

Resulting subproblem involves only vertical coordinates. Horizontal coordinates should not be considered at all. The following configurations should be considered as equivalent to each another because they differs only in horizontal coordinates of tiles:

``` A A A     A   A A     A A A
B B B B   B B B B   B B B B
C C C C   C C C C   C C C C
D D D A   A D D D   D D A D
```

As in subproblem only vertical coordinates involves, we should do only vertical moves because any horizontal move does not change anything. In given example, we have only one unique move:

``` A A A      A A A B
B B B B -> B B B
C C C C    C C C C
D D D A    D D D A
```

After this move, we have three unique moves: move tile A from row 1, move tile B from row 1 or move tile C from row 3.

It is possible to represent any such configurations in table. In the cell in row i and column j is the number of such tiles in row i that should be in row j. For example,

``` A A A         3 0 0 0
B B B B  <->  0 4 0 0
C C C C       0 0 4 0
D D D A       1 0 0 3
Row 1 contains 3 tiles from row 1.
Row 2 contains 4 tiles from row 2.
Row 3 contains 4 tiles from row 3.
Row 4 contains 1 tile from row 1 and 3 tiles from row 4.
```

There are 24,964 correct tables, and each table corresponds to some set of configurations of tiles. God's algorithm for this "sub-puzzle" is 35 moves.

It is possible to do the same things but with subproblem involving only horizontal coordinates. Tiles 1, 5, 9, 13 should be marked with "A", tiles 2, 6, 10, 13 with "B", tiles 3, 7, 11, 15 with "C", and tiles 4, 8, 12 with "D". Only horizontal moves should be used.

Any Fifteen instance can be converted to two "ortogonal" subproblems.

```  1  2  3  0        A A A         A B C
5  6  7  8   ->   B B B B   +   A B C D
9 10 11 12        C C C C       A B C D
13 14 15  4        D D D A       A B C D

Fifteen           horizontal    vertical
instance          subproblem    subproblem

MD = 3            WD1 = 11      WD2 = 0
optimal 19        WD = WD1 + WD2 = 11 + 0 = 11
```

So Walking Distance can give better lower bound than Manhattan Distance. Maximal WD value is 70:

```  0 15 14 13
12 11 10  9
8  7  6  5
4  3  2  1
MD = 58, WD = 70, optimal 78
```

Translator's note. There is also author's picture explanation.

I have calculated God's number for 5x5 puzzle. There are 65,650,495 correct tables, and maximal value in each of two subproblems is 70. There is only one configuration at depth 70:

```  E E E E                           A A A A A
D D D D D                         B B B B B
C C C C C -> 70 vertical moves -> C C C C C
B B B B B                         D D D D D
A A A A A                         E E E E
```

Therefore the following Twenty-Four instance cannot be solved in less than 140 moves:

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

WD 5x5, distribution

``` depth       new      total
1         1          2
2         2          4
3         3          7
4         7         14
5        12         26
6        32         58
7        51        109
8       124        233
9       190        423
10       450        873
11       669       1542
12      1538       3080
13      2170       5250
14      4839      10089
15      6454      16543
16     14039      30582
17     17520      48102
18     37031      85133
19     43146     128279
20     88805     217084
21     96196     313280
22    192532     505812
23    194824     700636
24    379743    1080379
25    359507    1439886
26    680999    2120885
27    607734    2728619
28   1120603    3849222
29    944886    4794108
30   1694006    6488114
31   1360108    7848222
32   2369139   10217361
33   1816212   12033573
34   3067879   15101452
35   2261336   17362788
36   3702816   21065604
37   2623265   23688869
38   4148672   27837541
39   2844873   30682414
40   4350752   35033166
41   2872722   37905888
42   4216272   42122160
43   2699250   44821410
44   3823128   48644538
45   2350552   50995090
46   3171751   54166841
47   1879601   56046442
48   2445261   58491703
49   1383052   59874755
50   1701761   61576516
51    910910   62487426
52   1078879   63566305
53    542962   64109267
54    616621   64725888
55    279543   65005431
56    306588   65312019
57    114860   65426879
58    126372   65553251
59     41125   65594376
60     42833   65637209
61      5053   65642262
62      5528   65647790
63      1316   65649106
64      1236   65650342
65        81   65650423
66        48   65650471
67        13   65650484
68         9   65650493
69         1   65650494
70         1   65650495
```

Verified

These numbers have been verified; congratulations! I think you should post your new lower bound to the OEIS.

Four-stage suboptimal solver

There are several ways to choose subgoals for multi-stage analysis and/or solver. I listed below some subgoals that can be used. I have not listed many small and some large subgoals because I tried to fit in 1 GB of RAM. Also not listed many complex-shaped subgoals because I limited myself to the most promising alternatives.

First, goal state should be defined. I know two possible "standard" goals, and I cannot tell which one is prettier. Both configurations shown below. Blank square denoted by 0.

```   Zero-based      Null-terminated
0  1  2  3  4     1  2  3  4  5
5  6  7  8  9     6  7  8  9 10
10 11 12 13 14    11 12 13 14 15
15 16 17 18 19    16 17 18 19 20
20 21 22 23 24    21 22 23 24 0
```

Through this post, zero-based goal has been used.

In the following table listed possible subgoals. "Possible parent stages" column reflect how stages can be chained together. For example, we can use chain 1b -> 3a -> 6a -> 9a, and so 6a is possible parent for 9a, 3a is possible parent for 6a, and 1b is possible parent for 3a. "Tiles" column reflect which tiles included in subgoal and should be solved during stage. God's number given in two metrics. STM is single-tile moves, and MTM is multi-tile moves.

``` id   Possible        Tiles                        Size             God's number
parent stages                                                 STM     MTM

1a.  -               18 19 23 24                  6,375,600        61      33
1b.  -               20 21 22 23 24               127,512,000      74      38
1c.  -               14 19 22 23 24               127,512,000      71      38

2a.  1a              4 9 14 20 21 22              586,051,200      86      46
2b.  1a              15 16 17 20 21 22            586,051,200      83      43

3a.  1b              15 16 17 18 19               27,907,200       62      32
3b.  1b              4 9 14 19                    1,860,480        58      31
3c.  1b              4 9 14 18 19                 27,907,200       66      34

4a.  1c              4 9 18 20 21                 27,907,200       81      44
4b.  1c              4 9 20 21                    1,860,480        74      41

5a.  2a, 3c, 4a      3 8 13 15 16 17              32,432,400       55      33

6a.  2b, 3a          10 11 12 13 14               3,603,600        49      28
6b.  2b, 3a          3 4 8 9 13 14                32,432,400       61      31
6c.  2b, 3a          4 9 10 11 12 13 14           259,459,200      62      33

7a.  3b, 4b          15 16 17 18                  524,160          46      27
7b.  3b, 4b          3 8 13 15 16 17 18           518,918,400      61      34

8a.  5a, 6b, 7b      1 2 5 6 7 10 11 12           181,440          31      24

9a.  6a              1 2 3 4 5 6 7 8 9            1,814,400        55      36

10a. 6c              1 2 3 5 6 7 8                20,160           36      25

11a. 7a              1 2 3 5 6 7 8 10 11 12 13    239,500,800      53      33
```

It is possible to construct 13 different four-stage "chains" from these subgoals. These chains are listed below.

```    Chain
1.  1a -> 2a -> 5a -> 8a
2.  1a -> 2b -> 6a -> 9a
3.  1a -> 2b -> 6b -> 8a
4.  1a -> 2b -> 6c -> 10a
5.  1b -> 3a -> 6a -> 9a
6.  1b -> 3a -> 6b -> 8a
7.  1b -> 3a -> 6c -> 10a
8.  1b -> 3b -> 7a -> 11a
9.  1b -> 3b -> 7b -> 8a
10. 1b -> 3c -> 5a -> 8a
11. 1c -> 4a -> 5a -> 8a
12. 1c -> 4b -> 7a -> 11a
13. 1c -> 4b -> 7b -> 8a
```

Any of these chains can be used to create four-stage suboptimal solver with or without using "slackness" approach.

It is possible to paint graph (digraph) whose vertices are subgoals (2b, 7a etc.) and edges are "arrows" between subgoals (for example, there is edges from 1b to 3a and from 3a to 6b but there is no edge from 1b to 6b). With subgoals and chains from tables above, graph consists of 20 vertices and 26 edges. Three vertices are sources, and four vertices are sinks. So any chain of nested subgoals that can be used in multi-stage is path between some source and some sink in this graph. There is 13 paths.

Instead of having only one selected chain and searching through this chain, one can have many chains that are paths in graph and explore this graph with effect of running many different four-stage solvers. I have used slackness approach; slackness increased by 1 when all possible paths in graph (i.e., chains of subgoals) explored.

I have not enough RAM to store all 20 lookup databases, so I tried various smaller sets of subgoals. Experimental results from my previous post were obtained using subgoals 1b, 3a, 3b, 6a, 6b, 7b, 8a, 9a. So there were eight lookup databases in RAM with total size of 714,229,920 bytes, and the solver have been explored three chains of 13 (number 5, 6 and 9 from the list above).

Any questions, suggestions and anything else are welcome.