stannic
Regular
I have solved sub-optimally 1,000,000 random instances of 5x5 sliding tile puzzle in STM metric. The actual running time was about 18,5 hours. The minimum, maximum and average solution length were 73, 171 and 124.48 moves respectively. About 52% of 1,000,000 solutions were in range [118; 132]. There were only 32 instances with (suboptimal) solution length less than 81 (range [73; 80]). Only one instance was solved in 171 moves.
All data from the run are on Domain of the Cube Forum: link to the thread.
What is God's number of the 5x5 sliding tile puzzle?
The 3x3x3 Rubik's Cube has 4.3*10[SUP]19[/SUP] different configurations. The 5x5 Twenty-Four puzzle has 25! / 2 = 7.7*10[SUP]24[/SUP] configurations. This is about 180,000 more than in Rubik's Cube, but much less than 7.4*10[SUP]45[/SUP] configurations of 4x4x4 Rubik's Revenge. Here is the question: is it possible in foreseeable future to find God's number of the Twenty-Four puzzle, as it was done with Rubik's Cube?
Below is provided some history and theory behind the Fifteen and Twenty-Four puzzles.
Anyone interested? Do you know any recent results not listed here? Are there any interesting ideas? What do you think about it?
- stannic
Some links to the (4x4/5x5)-puzzle-related pages (in no particular order):
All data from the run are on Domain of the Cube Forum: link to the thread.
What is God's number of the 5x5 sliding tile puzzle?
The 3x3x3 Rubik's Cube has 4.3*10[SUP]19[/SUP] different configurations. The 5x5 Twenty-Four puzzle has 25! / 2 = 7.7*10[SUP]24[/SUP] configurations. This is about 180,000 more than in Rubik's Cube, but much less than 7.4*10[SUP]45[/SUP] configurations of 4x4x4 Rubik's Revenge. Here is the question: is it possible in foreseeable future to find God's number of the Twenty-Four puzzle, as it was done with Rubik's Cube?
Below is provided some history and theory behind the Fifteen and Twenty-Four puzzles.
In 1996, Richard E. Korf and Larry A. Taylor have solved optimally (STM) 10 random instances of the 5x5 Twenty-Four puzzle. This result was announced in their paper "Finding Optimal Solutions to the Twenty-Four Puzzle". The average solution length in that sample was 102.6 STM; the maximum solution length was 114 moves. 114 STM was lower bound for the puzzle until 2011.
In 1997, Swiss research team (Brüngger, A.; Marzetta, A.; Fukuda, K.; and Nievergelt, J.) in their paper "The Parallel Search Bench ZRAM and Its Applications." announced that every configuration of the 4x4 Fifteen Puzzle can be solved in 80 single tile moves (STM). In 2008, this result was confirmed by Richard Korf.
In 2000, Filip R. W. Karlemo and Patric R. J. Östergård in their article "On Sliding Block Puzzles" announced upper bound of 210 STM for the 5x5 sliding tile puzzle.
In 2010, Bruce Norskog and Morley Davidson announced that 4x4 Fifteen Puzzle can be solved in 43 MTM (multi-tile moves).
The current lower and upper bounds for God's number of the 5x5 Twenty-Four puzzle are 152 STM (Rokicki's result) and 208 STM/109 MTM (my result) respectively.
In 1997, Swiss research team (Brüngger, A.; Marzetta, A.; Fukuda, K.; and Nievergelt, J.) in their paper "The Parallel Search Bench ZRAM and Its Applications." announced that every configuration of the 4x4 Fifteen Puzzle can be solved in 80 single tile moves (STM). In 2008, this result was confirmed by Richard Korf.
In 2000, Filip R. W. Karlemo and Patric R. J. Östergård in their article "On Sliding Block Puzzles" announced upper bound of 210 STM for the 5x5 sliding tile puzzle.
In 2010, Bruce Norskog and Morley Davidson announced that 4x4 Fifteen Puzzle can be solved in 43 MTM (multi-tile moves).
The current lower and upper bounds for God's number of the 5x5 Twenty-Four puzzle are 152 STM (Rokicki's result) and 208 STM/109 MTM (my result) respectively.
Even if finding God's number for the 5x5 sliding tile puzzle is not achievable using current technology, it may be possible to improve upper and lower bounds. Just one fact is that Twenty-Four puzzle can be split to two sub-puzzles with roughly equal state space (the number of configurations):
The goal of first sub-puzzle is to solve tiles in top row and leftmost column of the puzzle. These tiles are called "fringe" tiles. The number of different configurations is 25! / 15! = 1.18*10[SUP]13[/SUP].
Second puzzle is equivalent to the well-known Fifteen Puzzle. This puzzle has state space of 16! / 2 = 1.04*10[SUP]13[/SUP] configurations, and it has been already solved (there is full distance distribution in STM and exact God's number in MTM).
Both sub-puzzles have almost the same state space, so probably the first one can also be solved in reasonable time. This will improve upper bound to (I think) something like 190 STM and/or 100 MTM (see table in the end of the post).
Code:
A A A A A
A B B B B
A B B B B
A B B B B
A B B B xSecond puzzle is equivalent to the well-known Fifteen Puzzle. This puzzle has state space of 16! / 2 = 1.04*10[SUP]13[/SUP] configurations, and it has been already solved (there is full distance distribution in STM and exact God's number in MTM).
Both sub-puzzles have almost the same state space, so probably the first one can also be solved in reasonable time. This will improve upper bound to (I think) something like 190 STM and/or 100 MTM (see table in the end of the post).
Three-color Rubik's Cube is yet another puzzle with almost the same state space as the Fifteen Puzzle (1.08*10[SUP]13[/SUP]), and it also has been solved.
State space of the Rubik's cube can be reduced by a factor of about 48. The number of configurations of the 5x5 "fringe" region can be reduced by symmetry by a factor of about two which is much less significant reduction.
However, it seems from the linked discussion that the 3-color cube was solved without any symmetry reduction.
State space of the Rubik's cube can be reduced by a factor of about 48. The number of configurations of the 5x5 "fringe" region can be reduced by symmetry by a factor of about two which is much less significant reduction.
However, it seems from the linked discussion that the 3-color cube was solved without any symmetry reduction.
According to Rokicki's result, rotated 180 degrees 5x5 configuration (see below) requires at least 152 STM. Therefore lower bound for God's Number of 5x5 puzzle in STM metric is 152 moves.
However, this configuration can be solved in 156 moves. Its exact distance still remains under question (although I believe it is at distance 156 STM actually).
In MTM metric, there are no even good lower bounds for 5x5 sliding tile puzzle yet. Simple counting gives lower bound of 41 multi-tile moves which is lower than God's number for 4x4 puzzle in that metric (43 MTM).
One possibility to obtain a good lower bound is to solve optimally candidate instances. However, optimal solving random instances in MTM metric is harder because there are more possible moves.
Two candidates are shown below. Both configurations can be solved in 73 multitile moves (this is not optimal solution). The reason why these configurations can be "hard" in MTM is that they are reflected, so clockwise loops of tiles turned into counter-clockwise loops, and vise versa. Solving such configurations seems to take many moves.
Note that first two of 16 4x4 antipodes in MTM metric can be obtained by mirroring in the same way as the configurations above.
However, this configuration can be solved in 156 moves. Its exact distance still remains under question (although I believe it is at distance 156 STM actually).
Code:
x 24 23 22 21
20 19 18 17 16
15 14 13 12 11
10 9 8 7 6
5 4 3 2 1One possibility to obtain a good lower bound is to solve optimally candidate instances. However, optimal solving random instances in MTM metric is harder because there are more possible moves.
Two candidates are shown below. Both configurations can be solved in 73 multitile moves (this is not optimal solution). The reason why these configurations can be "hard" in MTM is that they are reflected, so clockwise loops of tiles turned into counter-clockwise loops, and vise versa. Solving such configurations seems to take many moves.
Code:
1 6 11 16 21
2 7 12 17 22
3 8 13 18 23
4 9 14 19 24
5 10 15 20 x
x 20 15 10 5
24 19 14 9 4
23 18 13 8 3
22 17 12 7 2
21 16 11 6 1The table below shows current lower and upper bounds on God's number for the 4x4 Fifteen, 5x5 Twenty-Four and its "fringe" regions in two metrics. Some numbers in the table are hyperlinks.
[table="width: 400, class: grid"][tr]
[td]Puzzle[/td]
[td]4x4 "fringe"[/td]
[td]4x4 full[/td]
[td]5x5 "fringe"[/td]
[td]5x5 full[/td]
[/tr][tr]
[td]STM[/td]
[td]= 61[/td]
[td]= 80[/td]
[td]91...128[/td]
[td]152...208[/td]
[/tr][tr]
[td]MTM[/td]
[td]= 34[/td]
[td]= 43[/td]
[td]41...67[/td]
[td]43...109[/td]
[/tr][/table]
[table="width: 400, class: grid"][tr]
[td]Puzzle[/td]
[td]4x4 "fringe"[/td]
[td]4x4 full[/td]
[td]5x5 "fringe"[/td]
[td]5x5 full[/td]
[/tr][tr]
[td]STM[/td]
[td]= 61[/td]
[td]= 80[/td]
[td]91...128[/td]
[td]152...208[/td]
[/tr][tr]
[td]MTM[/td]
[td]= 34[/td]
[td]= 43[/td]
[td]41...67[/td]
[td]43...109[/td]
[/tr][/table]
- stannic
Some links to the (4x4/5x5)-puzzle-related pages (in no particular order):
1. The Fifteen Puzzle can be solved in 43 "moves". Bruce Norskog, Morley Davidson. (Domain of the Cube Forum)
2. "15puzzle Optimal solver" for windows. Ken'ichiro Takahashi. (His solver implements very powerful heuristic called Walking Distance. This heuristic allowed to find for 5x5 puzzle lower bound of 140 STM, which later was raised to 152 STM).
4. Description of the WD heuristic (Japanese).
5. Description of the Walking Distance heuristic in English and in Russian (Sliding Tile Puzzle Corner).
6. Fifteen Puzzle Optimal Solver. Herbert Kociemba. (The program implements Walking Distance, as well as some other heuristics.)
7. Twenty-Four puzzle, some observations. (Domain of the Cube Forum)
8. 5x5 can be solved in 109 MTM / 208 STM. (Domain of the Cube Forum)
9. Results (Sliding Tile Puzzle Corner). Data on the puzzles. There are, for example, God's numbers of the various sliding-tile puzzles, distance distributions obtained during breadth-first exhaustive search, the number of moves needed to reduce MxN puzzle to smaller one etc.
10. kumi na tano - sliding tile puzzle suboptimal solver.
11. One Million Random Twenty-Four Puzzle Instances in the STM metric (Domain of the Cube Forum).
12. Multi-phase algorithms. Slackness concept. (Jaap's Puzzle Page, Computer Puzzling)
2. "15puzzle Optimal solver" for windows. Ken'ichiro Takahashi. (His solver implements very powerful heuristic called Walking Distance. This heuristic allowed to find for 5x5 puzzle lower bound of 140 STM, which later was raised to 152 STM).
4. Description of the WD heuristic (Japanese).
5. Description of the Walking Distance heuristic in English and in Russian (Sliding Tile Puzzle Corner).
6. Fifteen Puzzle Optimal Solver. Herbert Kociemba. (The program implements Walking Distance, as well as some other heuristics.)
7. Twenty-Four puzzle, some observations. (Domain of the Cube Forum)
8. 5x5 can be solved in 109 MTM / 208 STM. (Domain of the Cube Forum)
9. Results (Sliding Tile Puzzle Corner). Data on the puzzles. There are, for example, God's numbers of the various sliding-tile puzzles, distance distributions obtained during breadth-first exhaustive search, the number of moves needed to reduce MxN puzzle to smaller one etc.
10. kumi na tano - sliding tile puzzle suboptimal solver.
11. One Million Random Twenty-Four Puzzle Instances in the STM metric (Domain of the Cube Forum).
12. Multi-phase algorithms. Slackness concept. (Jaap's Puzzle Page, Computer Puzzling)
Last edited:
