qq280833822
Member
In the past week, I have calculated the god's algorithm for square one in face turn metric (ftm). According to the calculation, any twistable square-one states can be solved no more than 31 moves, where (x, 0), (0, y), / are counted as one move, (x, y) are counted as two moves.
In previous works, Mr. masonjones calculated the god's algorithm for sq1 in twist turn metric[1]. And Mike Godfrey solved all odd-permutation cube-shape positions and found that there're at least 12 positions cannot be solved in 30 moves in face turn metric[2].
Recently, I calculated the god's algorithm for sq1 in ftm. The number of different positions is 3,678 * 40,320 * 40,320 * 2 = 11,958,666,854,400, which is 3678 different shapes without considering middle layer and for each shape there are 40,320 * 40,320 combinations of permutations.
The number of positions is too large to handle, so I use symmetric reduction to reduce the search space. Firstly, all positions are split into 3678 * 2 * 2 sets according to shape, middle layer and parity, with 40320*20160 different positions per set. Then, I use symmetric to reduce the number of sets to 3816. Therefore the search space is reduced to 3816*40320*20160 = 3,101,840,179,200.
Finally, I use disk-based BFS search to calculate the god's algorithm. It spends 2 bits on each position. If the position have been visited, it stores the depth of the position modulo 3, otherwise it stores '3' to indicate the position has not been visited. So the total disk space required is 775,460,044,800 Bytes or 722.2GBytes.
After searching up to 31 moves, all positions have been accessed and therefore the god number of SQ1 is exactly 31.
Here's the depth distribution of all positions.
I also count the depth distribution of all 3816 unique sets. The value of cube-shaped odd-permutation sets matches the calculation of Mike Godfrey.
[1] Square One God's Algorithm Computed, http://cubezzz.dyndns.org/drupal/?q=node/view/35
[2] Odd Permutations of the Cube Shape of Square-1, http://cubezzz.dyndns.org/drupal/?q=node/view/77
In previous works, Mr. masonjones calculated the god's algorithm for sq1 in twist turn metric[1]. And Mike Godfrey solved all odd-permutation cube-shape positions and found that there're at least 12 positions cannot be solved in 30 moves in face turn metric[2].
Recently, I calculated the god's algorithm for sq1 in ftm. The number of different positions is 3,678 * 40,320 * 40,320 * 2 = 11,958,666,854,400, which is 3678 different shapes without considering middle layer and for each shape there are 40,320 * 40,320 combinations of permutations.
The number of positions is too large to handle, so I use symmetric reduction to reduce the search space. Firstly, all positions are split into 3678 * 2 * 2 sets according to shape, middle layer and parity, with 40320*20160 different positions per set. Then, I use symmetric to reduce the number of sets to 3816. Therefore the search space is reduced to 3816*40320*20160 = 3,101,840,179,200.
Finally, I use disk-based BFS search to calculate the god's algorithm. It spends 2 bits on each position. If the position have been visited, it stores the depth of the position modulo 3, otherwise it stores '3' to indicate the position has not been visited. So the total disk space required is 775,460,044,800 Bytes or 722.2GBytes.
After searching up to 31 moves, all positions have been accessed and therefore the god number of SQ1 is exactly 31.
Here's the depth distribution of all positions.
Code:
Depth Total #New
0 1 1
1 16 15
2 85 69
3 297 212
4 1,438 1,141
5 5,371 3,933
6 19,400 14,029
7 63,588 44,188
8 202,540 138,952
9 649,260 446,720
10 1,965,432 1,316,172
11 6,140,878 4,175,446
12 18,288,350 12,147,472
13 56,172,978 37,884,628
14 165,639,212 109,466,234
15 498,518,504 332,879,292
16 1,454,898,116 956,379,612
17 4,285,819,784 2,830,921,668
18 12,288,746,014 8,002,926,230
19 34,951,544,310 22,662,798,296
20 96,075,902,092 61,124,357,782
21 257,070,679,994 160,994,777,902
22 653,697,566,102 396,626,886,108
23 1,581,344,013,920 927,646,447,818
24 3,471,138,980,310 1,889,794,966,390
25 6,600,087,749,620 3,128,948,769,310
26 9,902,019,903,186 3,301,932,153,566
27 11,668,654,358,130 1,766,634,454,944
28 11,950,188,612,006 281,534,253,876
29 11,958,657,866,914 8,469,254,908
30 11,958,666,854,024 8,987,110
31 11,958,666,854,400 376
I also count the depth distribution of all 3816 unique sets. The value of cube-shaped odd-permutation sets matches the calculation of Mike Godfrey.
[1] Square One God's Algorithm Computed, http://cubezzz.dyndns.org/drupal/?q=node/view/35
[2] Odd Permutations of the Cube Shape of Square-1, http://cubezzz.dyndns.org/drupal/?q=node/view/77