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.

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