cube files
Indexed Cube Lovers Archive
All 164,604,041,664 Symmetric Positions Solved, QTM
Submitted by rokicki on Sat, 04/12/2014 - 19:54.
Perhaps the most amazing feat of computer cubing was Silviu Radu and
Herbert Kociemba's optimally solving all 164,604,041,664 positions in
the half-turn metric back in 2006. Computers were much slower and had
much less memory back then, and handling so many different subgroups
can be tricky. Radu used GAP to help with the complexity of the group
theory, and Michael Reid's optimal solver to provide the fundamental
solving algorithms, and Kociemba used his Cube Explorer optimal solver
to handle both the smaller subgroups and the positions left over after
Radu's subgroup solver ran.
Finally, some eight years later, the same thing has been accomplished in the quarter-turn metric. The table below gives the overall distance distribution of symmetric positions in the quarter-turn metric:
dist positions mod M mod M+inv mod 48
0 1 1 1 1
1 12 1 1 12
2 18 3 3 18
3 108 5 3 12
4 411 19 14 27
5 1,104 46 25 0
6 3,744 163 102 0
7 11,760 490 258 0
8 36,731 1,582 902 11
9 111,144 4,632 2,370 24
10 358,138 15,054 7,908 10
11 1,028,848 42,895 21,647 16
12 3,266,949 136,691 70,284 21
13 9,443,588 393,602 198,149 20
14 29,201,318 1,218,544 618,945 38
15 83,765,676 3,490,523 1,752,632 12
16 268,136,523 11,177,948 5,644,771 27
17 819,440,112 34,146,994 17,140,681 0
18 3,083,699,868 128,516,587 64,687,074 12
19 11,628,867,276 484,563,973 243,091,188 12
20 41,538,350,563 1,730,948,894 869,224,590 19
21 67,617,360,740 2,817,563,628 1,413,565,363 20
22 37,373,063,137 1,557,455,774 783,700,221 1
23 2,147,815,036 89,510,797 45,330,245 28
24 78,820 3,635 3,324 4
25 36 2 2 36
26 3 1 1 3
--------------- ------------- ------------- --
tot 164,604,041,664 6,859,192,484 3,445,060,704 0
Like Radu and Kociemba's result did for the count of distance-20
positions in the half-turn metric, this exploration did for
the count of distance-24 positions in the quarter-turn metric: it
vastly expanded the set of known positions. Indeed, we believe
that most positions that are distance 24 or greater in the quarter
turn metric are symmetric. We have shown that the number of
asymmetric distance-20 positions in the half-turn metric vastly
outnumber the set of distance-20 symmetric positions.
Further, no position of distance 25 or greater was found, other than those known; this supports our belief that the only positions at distance 25 or greater are those already know. These positions are the single distance-26 position in three distinct orientations, and the two immediate neighbors of this position in 12 and 24 distinct orientations, respectively.
Almost all the symmetric distance-24 positions are also antisymmetric; there are only 311 distinct distance-24 positions that have symmetry but not antisymmetry (modulo symmetry and antisymmetry).
As part of this work, we have duplicated Radu and Kociemba's results, and validated every number in every table on Kociemba's site with respect to symmetric positions in the half-turn metric. We did this in part to validate our programming, since the vast majority of the code is in common between the quarter-turn and half-turn metrics.
We are presently searching for distance-24 positions in the quarter-turn metric using a technique similar to those we have been using for distance-20 positions in the half-turn metric. We will post results on this search soon.
More details are available at http://cube20.org/symmetry/ and there is a short paper at http://tomas.rokicki.com/qtmsymmetry.pdf summarizing these results.
