Lower bounds for the 3x3x3 Super Group

For quite a while I was looking for an optimal solution for the 'Pure Superflip' (a Superflip pattern were all centers remain untouched). Such an algorithm would also allow to define the lower bound for the 3x3x3 Super Group. I don't know if there already exist lower and upper bounds for this cube group.

Years ago I computed all optimal solutions of the 'Superflip' pattern in ftm (face turn metric) to see if any of the 4416 algorithms may leave the centers unchanged. Unfortunately all these algorithms twist either 4 or 5 of the centers.

I figured out that such an algorithm must be within the range of 23 and 24 moves, but I never was able to prove it. It took just too long for solvers these days to compute a solution.

Nevertheless, in May 23, 2009, I found two short algorithms that seemed to be optimal:
B2 L2 B2 L' D2 F2 R' D B U L2 F2 R2 L' D' L F D' L D' R' B' U' F' (24 ftm, 32 qtm)
L2 D2 L2 D' B2 R2 U' B L F D2 R2 U2 D' B' D R B' D B' U' L' F' R' (24 ftm, 32 qtm)


I recently gave it another try and was finally lucky to prove that the 'Pure Superflip' can be solved optimally in 24 ftm. The algorithm I found was also more efficient in terms of quarter turn moves. The solver required 6 weeks, 6 days, 22 hours, 58 minutes and 34.1 seconds to find it:

New solution found in July 19, 2014:
B' L2 R U' B' D B2 R' L F2 D' F U R2 L' F (U L)2 (R' U')2 (24 ftm, 28 qtm)


There might a high chance that this algorithm is optimal in qtm (quarter turn metric) too. Maybe someone can be confirmed that.


I also discovered an optimal solution in ltm (layer turn metric):
CR2 MF' MR2 MD MF' R U B L U MR F' MR B MR F' L' U' R' U' (19 ltm, 26 ftm, 28 qtm)

Note, that in SSE notation a prepending C describes a 'Cube rotation'. CR means to rotate the whole cube in clockwise direction as seen form the right face.
And a prepending M describes a 'Mid-layer twist'. MR means to twist the middle layer in clockwise direction as seen from the right face.
See also this description to learn more about the SSE notation.


Cheers,
Walter Randelshofer

Comment viewing options

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

New 28q* positions for the supergroup

As Bruce mentions in an earlier comment, superflip+fourspot has essentially one unique 28q* position (the one where the U center is untwisted but the other five centers are twisted 180 degrees). All other center orientations of superflip+fourspot can be solved in 26q or less.

For superflip, of 2048 unique center orientations (without reducing by symmetry), 456 (or more than 20%) are at distance 28q*, so this provides a lot more distance-28 positions. This is too many to list here, but I'm happy to provide my data on request.

As for the half-turn metric, I've solved many size-2048 cosets (1270) of the deepest and most symmetric positions, and these positions plus the one listed above are the only ones that required 28 quarter turns. Thus, it is extremely likely that the diameter of the supergroup in the quarter-turn metric is 28.

New distance-24 solutions in HTM

The main posting here has shown that pure superflip is at distance 24 in the half-turn metric. I've found three additional patterns that are at distance 24 in the half-turn metric; these are: Superflip with all centers turned 180 degrees:
   U F U L D B2 R2 D2 L D2 L D2 B2 F U2 R' B U' R2 B L' D' U' R' (24h*)
Superflip with one center untwisted, and other centers turned 180 degrees:
   U F U D R2 B F U' R2 D' B2 L' R D2 B L2 D U L U2 R2 B2 R' D' (24h*)
Superflip/supertwist with all centers solved:
   U R U D L F' R D2 B' D B2 D' B2 L' U' F' B L' D R2 F U' L F (24h*)
In addition, I've solved 31 cosets of size 2048 for the supercube, and I see this distribution of solution lengths:
     17 17
    183 18
   2433 19
  20810 20
  39341 21
    704 22
which indicates the mode is almost certainly 21, and the average is about 20.6. I've also solved the size-2048 cosets of the 289 most symmetric distance-20 positions, and gotten this distribution:
  73095 20
 412050 21
 106157 22
    561 23
      9 24
where those 9 positions at distance-24 come from the sequences listed above. From this, I strongly believe that the diameter of the supergroup is 24. Proving this will likely require much more CPU time than there is interest to justify, unless someone comes up with a nice shortcut.

<R,F> subgroup

Since the depths of the <R,F> subgroup for QTM and FTM are quite similar to those of the whole cube, the depths with center orientation of <R,F> might be good indications for those of the whole cube.
<R,F> group table for QTM:
Level     |          | SO       | GO       | Inv      | SO + Inv | GO + Inv |
----------+----------+----------+----------+----------+----------+----------+
    0     |        1 |        1 |        1 |        1 |        1 |        1 |
    1     |        4 |        2 |        1 |        2 |        1 |        1 |
    2     |       10 |        5 |        3 |        6 |        4 |        3 |
    3     |       24 |       12 |        6 |       12 |        6 |        4 |
    4     |       58 |       29 |       15 |       31 |       18 |       11 |
    5     |      140 |       70 |       35 |       70 |       35 |       20 |
    6     |      338 |      169 |       85 |      174 |       93 |       51 |
    7     |      816 |      408 |      204 |      408 |      204 |      108 |
    8     |     1970 |      985 |      493 |      997 |      513 |      267 |
    9     |     4756 |     2378 |     1189 |     2378 |     1189 |      609 |
   10     |    11448 |     5725 |     2863 |     5752 |     2916 |     1483 |
   11     |    27448 |    13724 |     6862 |    13752 |     6876 |     3472 |
   12     |    65260 |    32632 |    16324 |    32727 |    16461 |     8308 |
   13     |   154192 |    77098 |    38550 |    77168 |    38585 |    19388 |
   14     |   360692 |   180350 |    90192 |   180582 |    90522 |    45501 |
   15     |   827540 |   413780 |   206898 |   413979 |   207074 |   103923 |
   16     |  1851345 |   925690 |   462893 |   926328 |   463786 |   232692 |
   17     |  3968840 |  1984439 |   992268 |  1985625 |   993015 |   497698 |
   18     |  7891990 |  3946095 |  1973209 |  3947610 |  1975398 |   989918 |
   19     | 13659821 |  6830037 |  3415314 |  6834924 |  3418469 |  1712711 |
   20     | 18471682 |  9236067 |  4618491 |  9238500 |  4622960 |  2316366 |
   21     | 16586822 |  8293763 |  4147448 |  8301511 |  4152530 |  2081704 |
   22     |  8039455 |  4019999 |  2010449 |  4021563 |  2013156 |  1010156 |
   23     |  1511110 |   755693 |   378110 |   757928 |   379817 |   191250 |
   24     |    47351 |    23701 |    11894 |    23737 |    12005 |     6152 |
   25     |       87 |       44 |       27 |       53 |       32 |       21 |

<R,F> group table for FTM:
Level     |          | SO       | GO       | Inv      | SO + Inv | GO + Inv |
----------+----------+----------+----------+----------+----------+----------+
    0     |        1 |        1 |        1 |        1 |        1 |        1 |
    1     |        6 |        3 |        2 |        4 |        2 |        2 |
    2     |       18 |        9 |        5 |        9 |        6 |        4 |
    3     |       54 |       27 |       14 |       30 |       15 |       10 |
    4     |      162 |       81 |       41 |       81 |       45 |       25 |
    5     |      486 |      243 |      122 |      252 |      126 |       70 |
    6     |     1457 |      729 |      365 |      729 |      378 |      196 |
    7     |     4360 |     2180 |     1091 |     2206 |     1103 |      572 |
    8     |    13016 |     6508 |     3256 |     6528 |     3303 |     1672 |
    9     |    38482 |    19243 |     9627 |    19345 |     9692 |     4911 |
   10     |   113094 |    56548 |    28282 |    56605 |    28441 |    14301 |
   11     |   328920 |   164462 |    82243 |   164864 |    82440 |    41454 |
   12     |   942351 |   471183 |   235611 |   471307 |   236060 |   118393 |
   13     |  2616973 |  1308507 |   654297 |  1309754 |   655082 |   328547 |
   14     |  6774848 |  3387472 |  1693858 |  3388767 |  1695717 |   849714 |
   15     | 15105592 |  7552965 |  3776718 |  7557196 |  3780187 |  1894131 |
   16     | 24231019 | 12115830 |  6058483 | 12121324 |  6064602 |  3038464 |
   17     | 19421274 |  9711098 |  4856334 |  9718187 |  4862261 |  2437950 |
   18     |  3843568 |  1922014 |   961504 |  1924617 |   964036 |   485064 |
   19     |    47465 |    23763 |    11954 |    23984 |    12152 |     6325 |
   20     |       54 |       30 |       16 |       28 |       17 |       12 |

<R,F> group table with center orientation for QTM:
Level     |          | SO       | GO       | Inv      | SO + Inv | GO + Inv |
----------+----------+----------+----------+----------+----------+----------+
    0     |        1 |        1 |        1 |        1 |        1 |        1 |
    1     |        4 |        2 |        1 |        2 |        1 |        1 |
    2     |       10 |        5 |        3 |        6 |        4 |        3 |
    3     |       24 |       12 |        6 |       12 |        6 |        4 |
    4     |       58 |       29 |       15 |       31 |       18 |       11 |
    5     |      140 |       70 |       35 |       70 |       35 |       20 |
    6     |      338 |      169 |       85 |      174 |       93 |       51 |
    7     |      816 |      408 |      204 |      408 |      204 |      108 |
    8     |     1970 |      985 |      493 |      997 |      513 |      267 |
    9     |     4756 |     2378 |     1189 |     2378 |     1189 |      609 |
   10     |    11482 |     5741 |     2871 |     5770 |     2920 |     1485 |
   11     |    27720 |    13860 |     6930 |    13860 |     6930 |     3500 |
   12     |    66554 |    33279 |    16647 |    33382 |    16782 |     8463 |
   13     |   159508 |    79754 |    39877 |    79754 |    39877 |    20038 |
   14     |   381906 |   190954 |    95487 |   191171 |    95816 |    48114 |
   15     |   909128 |   454564 |   227282 |   454564 |   227282 |   114035 |
   16     |  2148570 |  1074294 |   537174 |  1074919 |   538091 |   269723 |
   17     |  5021152 |  2510576 |  1255288 |  2510576 |  1255288 |   629091 |
   18     | 11519183 |  5759657 |  2879919 |  5761075 |  2882462 |  1443450 |
   19     | 25564140 | 12782070 |  6391035 | 12782070 |  6391035 |  3201141 |
   20     | 53165460 | 26582972 | 13291964 | 26587116 | 13299938 |  6658066 |
   21     | 98093052 | 49046526 | 24523263 | 49046526 | 24523263 | 12282132 |
   22     |144569655 | 72285713 | 36144428 | 72295139 | 36161903 | 18101620 |
   23     |145058552 | 72529276 | 36264638 | 72529276 | 36264638 | 18171981 |
   24     | 81149863 | 40576208 | 20290372 | 40585835 | 20304096 | 10171369 |
   25     | 19091708 |  9545854 |  4772927 |  9545854 |  4772927 |  2400251 |
   26     |   917746 |   458981 |   229787 |   459614 |   230293 |   116581 |
   27     |     2100 |     1050 |      525 |     1050 |      525 |      337 |
   28     |        4 |        4 |        2 |        2 |        2 |        2 |

<R,F> group table with center orientation for FTM:
Level     |          | SO       | GO       | Inv      | SO + Inv | GO + Inv |
----------+----------+----------+----------+----------+----------+----------+
    0     |        1 |        1 |        1 |        1 |        1 |        1 |
    1     |        6 |        3 |        2 |        4 |        2 |        2 |
    2     |       18 |        9 |        5 |        9 |        6 |        4 |
    3     |       54 |       27 |       14 |       30 |       15 |       10 |
    4     |      162 |       81 |       41 |       81 |       45 |       25 |
    5     |      486 |      243 |      122 |      252 |      126 |       70 |
    6     |     1457 |      729 |      365 |      729 |      378 |      196 |
    7     |     4360 |     2180 |     1091 |     2206 |     1103 |      572 |
    8     |    13048 |     6524 |     3264 |     6528 |     3303 |     1672 |
    9     |    38951 |    19476 |     9743 |    19557 |     9783 |     4955 |
   10     |   115976 |    57988 |    29004 |    58007 |    29126 |    14644 |
   11     |   343978 |   171989 |    86009 |   172266 |    86140 |    43297 |
   12     |  1015774 |   507890 |   253961 |   507949 |   254347 |   127545 |
   13     |  2976658 |  1488336 |   744190 |  1489185 |   744702 |   373353 |
   14     |  8604330 |  4302183 |  2151138 |  4302491 |  2152494 |  1078096 |
   15     | 24101505 | 12050818 |  6025502 | 12053216 |  6027477 |  3018874 |
   16     | 62871619 | 31435981 | 15718303 | 31437602 | 15723377 |  7871909 |
   17     |138338799 | 69169739 | 34585522 | 69175826 | 34593097 | 17320643 |
   18     |205367581 |102684511 | 51343575 |102690863 | 51357489 | 25716912 |
   19     |129314254 | 64657973 | 32330465 | 64664914 | 32340382 | 16210032 |
   20     | 14708735 |  7354767 |  3678095 |  7355953 |  3680693 |  1853098 |
   21     |    47724 |    23879 |    12003 |    23901 |    12013 |     6521 |
   22     |      110 |       57 |       29 |       55 |       29 |       19 |
   23     |       12 |        6 |        3 |        6 |        3 |        3 |
   24     |        2 |        2 |        1 |        1 |        1 |        1 |
As you can see, the tables with center orientation reach exactly as far as the lower bound 24 and 28 for the whole cube. But the average distances of <R,F> are less than those of the whole cube.

Super Group is at least 28 moves in QTM

I now got my 9 GB solver running. It is written in pure C and can run several threads at the same time, I used 6 threads in parallel.
I applied it to 'pure superflip' * X, where X is from {UUD,UUR,UDR,UDR',UD'R,URU,URU',URR,URF,URF',URD,URD'URL,URL',URB,URB',UR'U,UR'U',UR'F,UR'F',UR'D,UR'D',UR'L',UR'B,UR'B'} (25 cases) and in no case a 23 move solution was found.

The solver is not so fast as I hoped. It took about 36 h to handle all cases.

When I have done some cleanup I will make it public.

I also am running the superflip-4spot position with the orientations as Bruce described and it took a bit less than an hour to complete depth 24. So it will take several days to complete depth 26.

A coset solver surely would be the best choice to find more 28q* or even 30q* positions. But a coset for the target group I described has 8!*8!*4!/2*4^2/2 elements, which needs at least 19 GB additional space using 1 bit per coset position. So on a 32 GB machine it should be doable.

Congrats & thanks

Congratulations on proving 28 as a lower bound.

I thank you for you taking the time and effort to create this solver. I also hope you are able to complete the search you are doing on that superflip-4spot position through depth 26.

Thanks. With X=superflip-4spo

Thanks. With X=superflip-4spot position I checked XUU, XUR, XUR', XUD, XUD' up to now and the first solution which appeared was for XUR giving U2 F2 U D' F' R' L U' R2 D' F B' U2 B2 D2 L U' D' B D' (26q*), so this is exactly the (28q*) solution for X you already got. So we already know that there is no (26q*) solution starting with U or U'.
I now run the remaining cases XRU, XRU', XRR, XRD, XRD', XDR, XDR', XDD, which will take another 3.5 days.

It would seem to me you also

It would seem to me you also need to do XRL, XRL', XRF, and XRF'. I also believe XDDR could suffice for XDD.

EDIT: I believe XRB and XRB' are also needed.

You are absolutely right. The

You are absolutely right. These 6 cases are all needed. I am glad you detected my negligence. So there are 19 different cases. Currently I run 4 cases in parallel which takes 50% of the resources of my machine. Each run will be about 3 days. It will take more than a week until all cases are finished.

And with XDDR you are right too. XDD has rotational symmetry about the UD-axis and has mirror symmetry. And XDDU is included in XUD.

XRL, XRL' and XRR have some symmetry too which also can be exploited.

The computation of the 19 cas

The computation of the 19 cases is now finished. No 26* were found. In two cases a 28* solution was given before I stopped the computation:
R B' U U R B D L B' R D' L F R R D' F U R' B' U R' U D' R' F' U' F  (28q*)
D D R U R R F' D B' U R F U' L U L F F R U' D' L' D L U' R D' B' (28q*)
Still did not work on the program to get it into a shape such that it is useful for others.

Great results

Hmm, I may need to get a supergroup solver going!

It's a much bigger problem space but very doable.

And maybe a coset solver.

Anyway, great work.

Welcome to this forum, Walter

Welcome to this forum, Walter!

There was another thread on the supercube group on this forum awhile ago. There was a claim that the average distance in that group was virtually certain to be less than 22 face turns, but only a poor upper bound for God's number of 43 face turns. (This was before God's number for the standard cube group was proven, which would have reduced it to 41.)

I note that it's long been known that there are essentially only two 20f* superflip maneuvers (mod symmetries, inverses, and cyclic shifts) in the standard cube group. So that's why all the 20f* maneuvers you checked were split into only two sets based upon the number of twisted centers.

Similarly there are essentially only four 24q* maneuvers for superflip in the standard cube group. All four twist at least two centers, so the minimal "pure superflip" for the supercube must be at least 26 quarter turns. Of course, superflip composed with 4 spot gives a lower bound of 26q already for the supercube group.

Belief that a 28q* must exist

I have analyzed my database of 26q* maneuvers for the standard Rubik's cube. My analysis indicates there exists supercube positions for 4 spot composed with superflip that can not be solved in 26q. This would imply 28q* positions must exist for the supercube.

A position that my analysis indicates must be at least 28q* is the following:
4 spot, with the "spots" in the E layer, composed with superflip and all centers rotated 180 degrees except the U center, which is not rotated

(The E layer is the layer between the U and D layers. By symmetry, you can choose either the U center or the D center (but not both) to be the center that is not rotated.)

An optimal supercube solver should be used to verify that the distance of this position is indeed at least 28q*.

New lower bound for ltm

@ Bruce Norskog
In the standard Cube Group the 'Superflip with 4 Spots' requires indeed 26 moves in qtm compared to 24 moves for the Superflip, when solved optimally in this metric. So this is a very interestic position too. Nice finding, Bruce!


While checking similar positions, I discovered that a Superflip with all centers rotated around 180°, requires slightly more moves in ltm then a Pure Superflip. This means, that we do have a new lower bound of 20 moves for this metric: :-)

Optimal solution found in July 22, 2014:
CF' CR' R' MD' MF D2 L2 MD2 MR U MF' MR' D F B R' MF2 D2 MF' U2 R' U' (20* ltm, 28 ftm, 36 qtm)

As far as I know, this pattern can be solved in 24 moves ftm:
U F D R D B' U' D' F' L B2 D' L B' D2 R L2 (U2 F)2 U2 B2 L2 (24 ltm, 24 ftm, 32)

I am currently running this position through the solver to see if 24 moves is, as expected, optimal in face turn metric. However, the result will have no effect on the current lower bound for the face turn metric, but this Superflip variation might be of interest when looking for a lower bound in qtm too.

I've been checking my positio

I've been checking my position using Cube Explorer 5.01s in both face turn metric and slice turn metric, to see what it comes up with.

So far, the following optimal slice turn metric maneuvers have been found:

R U2 F2 E R' S' L' B2 R' E F2 D2 B2 R F' B' D S' x y'  (18s*)
R U' D' F D2 R2 U2 M' F' D2 B' E F' M' U2 L2 F M' x z  (18s*)

These are both 28 face quarter turns in length, thus establishing an upper bound in QTM of 28 for this specific position. So I'm pretty confident there is no supercube position corresponding to the four spot composed with superflip that requires more than 28q to solve.

In face turn metric, it's at least 21f*, but it hasn't found an optimal solution yet.

Walter, do you have your own custom solver that you are using? Also, as Cube Explorer 5 only supports FTM and STM, I'm not aware of an existing supercube optimal solver for QTM. I would like to be able to verify the above position is indeed 28q* with a QTM optimal solver.

And congratulations on finding a 20s* position. It looks like you use "ltm" to refer to what seems to be more commonly referred to (on the 3x3x3 at least) as slice turn metric.

EDIT: The position I've claimed to require 28 face quarter turns has the following optimal solution in face turn metric:

U R U2 F2 U D' F' R' L U' R2 D' F B' U2 B2 D2 L U' D' B D'  (22f*)

This maneuver is also 28q, so there is still no counterexample to my claim that this position requires 28 face quarter turns. Since 22 is optimal, the two optimal slice turn metric solutions above are also optimal in face turn metric.

I now made a QTM version of C

I now made a QTM version of Cube Explorer which you find in the download section of my homepage.
For supercubes the performance is not as good as it should be to show that for example the "pure superflip" is 28q*. If we call pure superflip X, we can solve XUUD, XUUR, XUDR... (if I count right 25 cases) and show that there is no solution in 23 moves. With 8 cores this will take about 1-2 weeks.

Since Cube Explores is 32-bit, the pruning table for supercubes cannot be made in the way which would be much more effective in my opinion:

Use the standard phase 1 coordinates edge flip (2^11), corner flip (3^7) and UD-slice (495) together with the twists of the R, F, L and B centers (4^4). Symmetry reduced by 16 symmetries you get an index from 0..64430*3^7*4^4. With compression this table should fit into about 7.5 GB of memory.
If you prune in UD- FB- and RL- direction in parallel this should give a good perfomance.

Thank you for this. I'm not a

Thank you for this. I'm not aware of any other program that optimally solves supercube positions in QTM.

I've looked at trying to solve my position that I believe to be 28q*. Unfortunately, it looks like it would take too long on my computer for me to commit to doing this right now. Thus, I wonder if there might be any chance of a 64-bit version like you described being produced, even if a GUI isn't included.

I already have written an opt

I already have written an optimal QTM solver in C a couple of years ago - I almost forgot this. So it really should not be difficult, the indexing function for the center twists is trivial. But since the QTM version of Cube Explorer was quite time consuming I will not do it in the moment.

I put an update for the QTM version online since solutions for the two-phase algorithm were only displayed for less than 30 moves. For pure superflip the two phase alg seems not to find a solution<30 moves within a reasonable time, so the old version showed no solution at all.

Edit: Meanwhile I computed the depth for the 64430*3^7*4^4 different values of the supercube QTM solver pruning table and got the following result:

 0             1
 1             2
 2            12
 3            62
 4           443
 5          3874
 6         34891
 7        316778
 8       2869226
 9      25784433
10     225890872
11    1817722226
12   10609437022
13   20490699918
14    2899361515
15        431685