All 164,604,041,664 Symmetric Positions Solved, QTM

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.

Comment viewing options

Select your preferred way to display the comments and click 'Save settings' to activate your changes.

All positions Vs Symmetric ones

Very cool. So this is what we know so far regarding QTM:
 d         All positions                         Symmetric positions
--       ---------------                        --------------------
 0                     1                                           1
 1                    12                                          12
 2                   114                                          18
 3                 1,068                                         108
 4                10,011                                         411
 5                93,840                                       1,104
 6               878,880                                       3,744
 7             8,221,632                                      11,760
 8            76,843,595                                      36,731
 9           717,789,576                                     111,144
10         6,701,836,858                                     358,138
11        62,549,615,248                                   1,028,848
12       583,570,100,997                                   3,266,949
13     5,442,351,625,028                                   9,443,588
14    50,729,620,202,582                                  29,201,318
15   472,495,678,811,004                                  83,765,676
16                                                       268,136,523    
17                                                       819,440,112  
18                                                     3,083,699,868 
19                                                    11,628,867,276 
20                                                    41,538,350,563
21                                                    67,617,360,740
22                                                    37,373,063,137 
23                                                     2,147,815,036   
24                                                            78,820 
25                                                                36   
26                                                                 3
--------------------------------------------------------------------
tot  43,252,003,274,489,856,000                      164,604,041,664

Two more levels

We actually know two more levels for All Positions, thanks
to Thomas Scheunemann and his results of July 2010. See nodes
194 and 195 on this forum.

Wow! "only" 9 levels left:)

 d         All positions                         Symmetric positions
--       ------------------------               --------------------
 0                            1                                    1
 1                           12                                   12
 2                          114                                   18
 3                        1,068                                  108
 4                       10,011                                  411
 5                       93,840                                1,104
 6                      878,880                                3,744
 7                    8,221,632                               11,760
 8                   76,843,595                               36,731
 9                  717,789,576                              111,144
10                6,701,836,858                              358,138
11               62,549,615,248                            1,028,848
12              583,570,100,997                            3,266,949
13            5,442,351,625,028                            9,443,588
14           50,729,620,202,582                           29,201,318
15          472,495,678,811,004                           83,765,676
16        4,393,570,406,220,123                          268,136,523    
17       40,648,181,519,827,392                          819,440,112  
18                                                     3,083,699,868 
19                                                    11,628,867,276 
20                                                    41,538,350,563
21                                                    67,617,360,740
22                                                    37,373,063,137 
23                                                     2,147,815,036   
24                                                            78,820 
25                                                                36   
26                                                                 3
--------------------------------------------------------------------
tot  43,252,003,274,489,856,000                      164,604,041,664

STM -- ideas for improvement

I did not know it was so hard to compute. I just thought it was quite doable because you have perfect pruning.

Here are some ideas. Maybe you already apply them, maybe not. Maybe they are good, maybe not.

(1) Perhaps STM is a bad metric in the sense that the turn tree grows much harder than the level's number of positions. You can generated all positions up to the level at which pruning gets effective. Next you reduce symmetry on these positions.

(2) Search for symmetries of the void cube with mirror equivalence and check afterwards if they are symmetries. With the void cube, you can add a factor of 24 symmetries, namely SO3 moves. With the void cube with mirror equivalence, you can add another factor of 48 symmetries. To do that, your algorithm must already use all 48 symmetries for reduction, which can be accomplished as follows.

(3) Modify your algorithm such that it uses 48 symmetries. The symmetry subgroups of size 2 are the hardest, I guess. For the UD symmetry, you can use 16 symmetries for reduction. This can be blown up to 48 by adding RL symmetry and FB symmetry to your prune table as well. For the UR symmetry, you can use 8 symmetries for reduction. Adding another 5 symmetries to your prune table gives all 48 symmetries again.

My guess is that (3) is more or less neutral with respect to speed: the number of symmetries increases but the pruning gets worse. But you may need (3) for (2).

STM

Thanks for the comments! I'm actually probably going to spend some
time on the 4x4x4 right now. I'm not sure exactly what went wrong
with the STM; I suspect as you say the tree is just different
somehow and that changes the efficacy of the approach.

I do have a blindingly fast STM optimal solver so it would be easy
for me to do the smaller subgroups (all but the subgroups of size
2). But I'd hate to spend the resources on that if I can't finish
them all.

New STM ideas

In STM, the turn tree branching factor is about 19, I guess, while the corner cube branching factor is based on the branching factor of the 2x2x2 (or void corner 3x3x3), which is 6. That is a large discrepancy.

For that reason, it might be a good idea to move the corner cube to the prune side. So you fix a specific symmetric corner cube and searches for edges cubes with corresponding symmetries. (This way, the search process moves somewhat to general optimal solving.)

For symmetries of order 3 and up, fixing the corner cube will result in prune tables which are too large. So I would suggest to overcome your resistance, and try the original concept or run the optimal general solver. A third idea is to apply the below with a non-perfect solver.

So there are five symmetries left, which are called c_2(a), c_2(b), c_s(a), c_s(b), and c_i on Herbert's Cube Explorer webside. Now I think the easiest to start with is also the largest, which is c_i.

c_i: If I am not mistaken, there are 332640 cosets of symmetric edge cubes. There are also 1837080 void corner cubes with mirror image reduction. Now make a prune table for solving void cubes with mirror image reduction to such cubes for which the corners are solved and the edges satisfy c_i. Assuming a factor 48 of symmetry reduction and four entries per byte, the prune table will become 3.2GB. Solve each symmetry-reduced symmetric void corner cube with solved edges (in an arbitrary manner, it does not matter for the symmetry c_i) with mirror image reduction, using the above prune table. Any solution you get this way will satisfy c_i.

The next symmetry is c_2(a). If I am not mistaken, there are again 332640 cosets of symmetric edge cubes. The same idea as above can be applied, but the conjugacy class of c_2(a) has size 3 instead of 1. This makes that both the symmetry reduction and the voiding is a factor 3 less, resulting in a prune table which is 9 times as large. Do you have 32 GB?

For the other three symmetries, there are too many cosets of symmetric edge cubes. So we must take small cosets for the corners. For c_s(a), we can solve the corners to <F2,R2>, which provides us a factor 6, if I am not mistaken. The other two symmetries have an additional problem that their conjugacy classes have size 6. But there are less of them, so there must be small coset for the corners that work.

Not really improvements

After some thought, I think that (2) does not really improve things, because there are more solutions to find. But you can of course use the ideas to do the symmetric positions of the void cube.

Congratulations!

There have been no comments in this thread so far, so I would like to congratulate Tom on yet another amazing feat of computer cubing. These results are quite wonderful!

Jerry