cube files
Indexed Cube Lovers Archive
Twenty-Four puzzle, some observations
Submitted by stannic on Sun, 07/24/2011 - 01:39.
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.
