cube files
Indexed Cube Lovers Archive
5x5 can be solved in 109 MTM
Submitted by stannic on Mon, 08/15/2011 - 10:53.
Any instance of the Twenty-Four puzzle (5x5) can be solved in 109m (multi-tile moves) or less. My proof consists of several steps. It is possible that there is logical error in this proof, so please check it thoroughly. However, I cannot find errors.
It is known that 4x4 Fifteen Puzzle can be solved in 43m. Also, there is 16 antipodes that cannot be solved in less than 43m. The table below gives the number of 4x4 antipodes with blank tile in any given square. Note that I used "0-based" goal (that is, in my goal state blank tile is in top left corner); Bruce Norskog used "0-terminated" goal (with blank tile in bottom right corner); so I turned each of 16 antipodes 180 degrees to make this table.
[1] 0 1 2 3 1 0 0 2 4 5 6 7 0 0 1 0 8 9 10 11 0 1 0 0 12 13 14 15 2 0 0 9 0-based goal # of antipodes
I used 4x4 puzzle as last stage of 5x5 solution. Before this stage, we should solve all fringe tiles.
[2] 5x5 goal. Tiles 4,9,14,19,20,21,22,23,24 are fringe tiles. 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
Note that in table [1] above, in any row there is at least one zero. Also, in any column there is at least one zero.
Let M be last move before getting into 4x4 puzzle (that is, all subsequent moves after M wil not touch fringe tiles). Then we always can select such multi-tile move M that resulting tile configuration can be solved in at most 42m.
Next step will be proof that 67m is sufficient to solve all nine fringe tiles. With this proof, the whole 5x5 puzzle can be solved in at most 67m + 42m = 109m.
We can split all configurations to 25 classes. Class i (0 ≤ i < 25) contains all configurations with blank tile in square i. Then we can combine these 25 classes to three groups A,B,C. This splitting is given below in table [3].
[3] A A A A A A C B B A A B B B A A B B B A A A A A A
Assertion 1. Any configuration of fringe tiles from group A can be solved in at most 67m.
Proof. I computed distribution for the following pattern. On the left shown pattern; on the right shown maximal distance in each of 25 classes. We can reflect the pattern through major diagonal; by combining the pattern with its reflection we can get 40m for any configuration from group A.
[4] . . . . 4 40 40 40 40 40 . . . . . 41 41 41 41 41 . . . . . 41 41 41 41 41 . . . . . 41 41 41 41 41 20 21 22 23 24 40 40 40 40 40
To finish solving fringe tiles, during stage 2 we should solve the following pattern. Again, on the left shown pattern, and on the right shown distribution of maximal distances by class. Maximal distance is 28m; however, we always can avoid 28m* configurations in stage 2 by selecting good last move in stage 1. Therefore, any fringe configuration from group A can be solved in at most 40m + 27m = 67m.
[5] . . . . # 27 27 27 27 # . . . . 9 28 28 28 28 28 . . . . 14 28 28 28 28 28 . . . . 19 27 27 27 27 27 # # # # # # # # # #
Assertion 2. Any configuration of fringe tiles from group B can be solved in at most 67m.
Proof. I computed distribution for the following pattern. By combining distributions of this pattern and its reflection through major diagonal, we can get 40m upper bound for any fringe configuration from group B.
[6] . . . . . 40 40 40 40 40 . . . . . 41 41 41 41 40 . . . . . 40 40 40 40 40 . . . . 19 41 40 41 40 41 20 21 22 23 24 41 40 41 40 41
To finish solving fringe tiles, we should solve in stage 2 the following pattern. We can get 27m* for this pattern using pattern on the table [5] by vertical reflection. So, any fringe tile configuration from group B can be solved in at most 40m + 27m = 67m.
[7] . . . . 4 . . . . 9 . . . . 14 . . . . # # # # # #
Assertion 3. Any configuration of fringe tiles from group C can be solved in at most 67m.
Proof. Group C consists of single class 6. We already proven that fringe configuration from any other class can be solved in 67m.
Let's go back to pattern [6]. There is 13 antipodes at depth 41m* for this pattern. However, only one of these configurations has blank square 6.
[8]. Pattern [6], 41m*. 19 . 22 . 20 23 0 . . 24 21 . . . . . . . . . . . . . .
Let's go back to pattern [4]. There is 59 antipodes at depth 41m*. However, only four of these configurations are in class 6.
[9]. Pattern [4], 41m*. 20 23 21 22 24 21 22 23 24 20 24 . . . 20 23 . 21 22 24 . 0 . . . . 0 . . . . 0 . . . 20 0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 . . . . . 4 . . . . 4 . . . . 4 23 . 22 . 4 . . . .
There is no such fringe tile configuration from class 6 that is 41m* both in pattern [4] and pattern [6].
Therefore, any configuration of fringe tiles from group C can be solved in at most 40m + 27m = 67m.
67m is sufficient to solve all nine fringe tiles. So we can solve any 5x5 instance in 67m + 42m = 109m.
