# One Million Random Twenty-Four Puzzle Instances in the STM metric



## stannic (Oct 7, 2012)

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.



Spoiler: History



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.





Spoiler: Fringe region



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):

```
A A A A A
A B B B B
A B B B B
A B B B B
A B B B x
```
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).





Spoiler: 3-color Rubik's Cube



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





Spoiler: Lower bounds for 5x5



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

```
x 24 23 22 21
20 19 18 17 16
15 14 13 12 11
10  9  8  7  6
 5  4  3  2  1
```
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.

```
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  1
```
Note that first two of 16 4x4 antipodes in MTM metric can be obtained by mirroring in the same way as the configurations above.





Spoiler: All known bounds



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


Puzzle4x4 "fringe"4x4 full5x5 "fringe"5x5 fullSTM= 61= 8091...128152...208MTM= 34= 4341...6743...109



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):


Spoiler: Links



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)


----------



## stannic (Oct 11, 2012)

Better lower bounds for 5x5 "fringe" region (old stuff I've forgot at first).

In STM, God's number of 5x5 "fringe" most probably will be somewhere in 110..120 moves (it's just interpolation, however). Solving _n_ tiles of fringe pattern for _n_ = 1..7 requires 29, 42, 52, 63, 74, 85, 91 moves resp. Seems that solving 8 of 9 fringe tiles will most likely require ~105 moves.

- stannic


----------



## ben1996123 (Oct 12, 2012)

Were you using any of the extra options to solve them (start search at, time limit etc.)? 18 hours for 1 million solves seems a bit long :/


----------



## stannic (Oct 12, 2012)

ben1996123 said:


> Were you using any of the extra options to solve them (start search at, time limit etc.)? 18 hours for 1 million solves seems a bit long :/



Yes, I've used option "stop at slackness = 1". So the solver was allowed to search with slackness < 1 (this means, only 0).

Basically, the program was searching only for optimal solutions on each phase. Overall solution is not optimal, just as in Thistlethwaite's algorithm for solving Rubik's Cube in 52 moves; however, there are usually very few alternative optimal solutions on each phase, so the search was rather quick.

Edit: In MTM metric, however, there are very many alternative optimal solutions at each of four stages.

- stannic


----------



## ben1996123 (Oct 13, 2012)

Ok, I've solved over 300 thousand 24 puzzle states for no particular reason, if you want the data.


----------



## stannic (Oct 13, 2012)

ben1996123 said:


> Ok, I've solved over 300 thousand 24 puzzle states for no particular reason, if you want the data.



Nice, and did you save report? Could you send it to me in some way (probably not in the thread itself so as not to clutter it up)?

- Bulat


----------



## ben1996123 (Oct 13, 2012)

stannic said:


> Nice, and did you save report? Could you send it to me in some way (probably not in the thread itself so as not to clutter it up)?
> 
> - Bulat



The batch solver is still running now, on about 320,000 solves, so I can stop it on however many solves you want (up to 500,000).


----------



## stannic (Oct 13, 2012)

Well, the more the better. If you can finish the whole sample then do not stop it manually. When it finishes, just save report with button "Save Report" and send it to me (probably zipped, as it will contain all the instances).
Or you can upload it to some service like mediashare and post link here.

However, I am also not sure what to do right now. This is why I've started this thread. The more random instances, the better results, but I am not sure what type of search to do (options like "start at", "stop at", "time limit"). Maybe someone can share some ideas.

Probably it does not make much sense to just solve millions of random instances with random search options 

I am currently trying to figure out what is the best search chain (partitioning scheme) for solving 5x5 puzzle suboptimally. There are some alternatives. For example, one can reduce 5x5 > 5x4 > 5x3 > 5x2 > I (I = solved puzzle), or 5x5 > 5x4 > 5x3 > 3x3 > I, or 5x5 > 5x4 > 4x4 > 3x3 > I.
It turns out that in STM metric, the best chain is 5x5 > 5x4 > 4x4 > 3x3.

Thanks for running solver for me.

- stannic


----------



## ben1996123 (Oct 13, 2012)

Just stopped at 340,444 states.



Spoiler: Report





```
Puzzle:               5 x 5
Move metric:          STM

Start search at:      off
Stop search at:       off
Start with slackness: off
Stop at slackness:    1
Time limit:           off
Right turns only:     off

Instances Solved:     340444
Total Time:           21282.715 s
Average Time:         62.515 ms
Min. Length:          73
Max. Length:          177
Average Length:       125.6476
Total rNodes:         567251907
Average rNodes:       1666.2121

    length          count
        73              1
        74              1
        75              2
        76              1
        77              1
        78              2
        79              2
        80              2
        81              4
        82              5
        83             14
        84             18
        85             17
        86             25
        87             42
        88             45
        89             68
        90             66
        91            111
        92            135
        93            151
        94            252
        95            302
        96            374
        97            419
        98            554
        99            675
       100            897
       101           1038
       102           1306
       103           1400
       104           1904
       105           2035
       106           2542
       107           2796
       108           3521
       109           3641
       110           4528
       111           4730
       112           5730
       113           5915
       114           6944
       115           7103
       116           8378
       117           8443
       118           9895
       119           9740
       120          11095
       121          10637
       122          12249
       123          11694
       124          12935
       125          11944
       126          12908
       127          11937
       128          12645
       129          11439
       130          12057
       131          11012
       132          11223
       133           9698
       134           9935
       135           8575
       136           8695
       137           7194
       138           7064
       139           5751
       140           5611
       141           4489
       142           4246
       143           3300
       144           3092
       145           2424
       146           2261
       147           1677
       148           1545
       149           1175
       150           1003
       151            701
       152            622
       153            457
       154            371
       155            243
       156            216
       157            158
       158            109
       159             93
       160             64
       161             38
       162             30
       163             21
       164             11
       165             11
       166              4
       167              3
       168              1
       169              3
       170              2
       177              1

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

Regions (8):
 A  fixed tiles: { }, current tiles: { 1 2 3 4 5 }
 B  fixed tiles: { 1 2 3 4 5 }, current tiles: { 6 7 8 9 10 }
 C  fixed tiles: { 1 2 3 4 5 6 7 8 9 10 }, current tiles: { 11 12 16 17 21 22 }
 D  fixed tiles: { 1 2 3 4 5 6 7 8 9 10 11 12 16 17 21 22 }, current tiles: { 13 14 15 18 19 23 }
 E  fixed tiles: { 1 2 3 4 5 6 7 8 9 10 }, current tiles: { 11 12 13 14 15 }
 F  fixed tiles: { 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 }, current tiles: { 16 17 18 19 21 22 23 }
 G  fixed tiles: { 1 2 3 4 5 }, current tiles: { 6 11 16 21 }
 H  fixed tiles: { 1 2 3 4 5 6 11 16 21 }, current tiles: { 7 8 9 10 12 17 22 }

Chains (3):
   [A,G,H,D]   194374
   [A,B,C,D]   118336
   [A,B,E,F]    27734
```

State that took 177 moves: 19 9 14 23 13 21 18 22 11 0 24 5 12 16 7 15 8 17 4 3 10 20 1 6 2
State that took 73 moves: 3 4 11 5 10 6 7 14 2 18 12 1 8 19 15 17 22 16 20 24 21 13 9 0 23


----------



## stannic (Oct 13, 2012)

*Some summary*

The following table shows results with and without using symmetric chains. Chains 1a, 2a and 3a are obtained from 1, 2 and 3 by mirroring through main diagonal.
With mirror chains, the benefit from using chain #1 becomes negligible.

- stannic


Spoiler





```
puzzle = 5x5, move metric = STM, slackness = 0 (stop at 1)
--------------------------------------------------------------------
Chains:
 A A A A A    A A A A A    A A A A A
 B B B B B    B B B B B    B C C C C
 C C C C C    C C D D D    B C D D D
 D D D D D    C C D D D    B C D D D
 D D D D x    C C D D x    B C D D x
     1            2            3
--------------------------------------------------------------------
                                       ben1996123            stannic
used chains                         w/o symmetric     with symmetric
                                          (1+2+3)   (1+1a+2+2a+3+3a)

size of sample                             340444              10000
average length                           125.6476           122.9030
average rNodes                          1666.2121          2590.1651
average time, ms                           62.515            110.230
--------------------------------------------------------------------
1   5x5 > 5x4 > 5x3 > 5x2 > I         27734 ~  8%          954  < 1%
2   5x5 > 5x4 > 5x3 > 3x3 > I        118336 ~ 35%         3783  ~38%
3   5x5 > 5x4 > 4x4 > 3x3 > I        194374 ~ 57%         5263  ~53%
--------------------------------------------------------------------
```


----------



## ben1996123 (Oct 13, 2012)

What does the slackness even do..?


----------



## stannic (Oct 13, 2012)

*"Slackness" concept*



ben1996123 said:


> What does the slackness even do..?



The concept of "slackness" is introduced and explained on Jaap's Puzzle Page, in the section "Multi-Phase algorithms". I've taken his description to include in the manual for _kumi na tano_ (page 7).

Shortly, slackness is the number of allowed non-optimal moves in the solution. Optimal move is a move that brings you closer to the subgoal; non-optimal move is a move that does not bring you closer to the subgoal.

When slackness = 0, only optimal solutions for each phase are allowed.
When slackness = 1, any one of phases is allowed to do one non-optimal move (one more move than minimum length).
When slackness = 2, any one or two phases are allowed to do two suboptimal moves.

If phase 1 optimal solution is 10 moves long, then with slackness = 2 phase 1 is allowed to do 10, 11 or 12 moves. Remaining ("unspent") after phase 1 slackness can be used in phases 2, 3 etc.

For example, with 4-stage algorithm the search goes in the following way:


Spoiler





```
1  2  3  4           // search phase
[slackness = 0]
0  0  0  0           // the number of allowed extra (non-optimal) moves in each phase
[slackness = 1]
0  0  1  0
0  1  0  0
1  0  0  0
[slackness = 2]
0  0  2  0
0  1  1  0
1  0  1  0
0  2  0  0
1  1  0  0
2  0  0  0
[slackness = 3]
0  0  3  0
0  1  2  0
1  0  2  0
0  2  1  0
1  1  1  0
2  0  1  0
0  3  0  0
1  2  0  0
2  1  0  0
3  0  0  0
[slackness = 4]
0  0  4  0
0  1  3  0
[I](12 more possibilities...)[/I]
4  0  0  0
[slackness = 5]
...
```



Note that Kociemba's Two-Phase algorithm does actually just the same thing with two phases (although there is no "slackness" concept in Kociemba's original explanation):


Spoiler





```
1 2 // search phase
[slackness = 0]
0 0    // each phase is solved optimally
[slackness = 1]
1 0    // phase 1 is allowed to do one non-optimal move
[slackness = 2]
2 0
[slackness = 3]
3 0
```



Also note that the last phase is always done optimally. The *penultimate *phase should use ("spend") all non-spent slackness.

Hope this is understandable 
- stannic

*Update:*
I've tried to make the first post more readable using spoilers. Also, some stuff is added in "Lower bounds" section.


----------

