# Supergroup knowledge

center facelets.) Have any computer explorations been performed? Any "hard"

positions known? Any coset explorations?

I know Jaap has a supergroup solver embedded in a Java applet. Does anyone else have

any programs?

A start might be an optimal solution length distribution that take a solved cube to a

solved cube, but just change the center facelet twists. But maybe an optimal solver

for the supergroup would just be too slow.

## Comment viewing options

### Domino (3x3x2) super-group

### I now added support for the s

The optimal solver for random supercubes is not too usefull in Cube Explorer because most situation need more than 20 moves and this would take too much time to solve.

The two-phase-algorithm however runs very well and gives solutions with an average length of less than 23 moves within seconds.

U R L U2 R' L' U R L U2 R' L' (12f*) //u++ U2 L' R B2 D2 F2 L R' D2 B2 (10f*) //u++ f++ U2 R2 F2 B2 L2 D2 R2 F2 B2 L2 (10f*) //u++ d++ U R L F2 B2 R' L' D' R L F2 B2 R' L' (14f*) //u+ d- U F B L R' U' D' F' U D L' R F' B' (14f*) //u+ f- U R U R2 U' R' B2 L2 F2 D R2 F2 L B2 L (15f*) //u+ d+ U F U' D' F2 L' R F B U F' B' L R' F2 D (16f*) //u+ f+ R L D2 R' L' D F2 R2 D2 L2 B2 R2 U2 B2 L2 D (16f*) //u++ d++ f++ U R U D F' B R' L U' D F2 D' R L' F B' D' (17f*) //u+ f++ r+ U D F2 U D' F R2 U2 D2 L2 B' U2 B2 R2 D2 L2 F2 (17f*) //u++ f+ b+ U R U R2 U' D' L' F2 D2 B2 R' D L U D' B2 D' (17f*) //u++ f++ r++ F U R L' U' D R' L F B' R' L F' U D' R L' B' (18f*) //u+ f+ b++ U F B' R2 F B L2 B2 D' F2 R2 D2 R2 F2 R2 D2 B2 L2 (18f*) //u+ d- f++ L' D2 B2 R' U2 B2 D2 L' F2 L2 U L U' L' U' L' U' L U (19f*) //u+ f++ r- U B U' B' U' B' U' B U F2 R2 U2 L2 F B2 R2 D2 L2 B2 (19f*) //u+ d++ f- U2 F2 L R' U2 F2 B2 U2 L' R F2 D2 (12f*) //u++ d++ f++ b++ U F2 L2 U F2 R2 B2 D F2 L2 D R2 B2 L2 (14f*) //u++ d++ f++ l++ U F L' R U' D F B' L' U D' L R' F' B D' (16f*) //u+ d- f+ l- U F' B L' R U R' F B' U' D L R' F L' D' (16f*) //u+ f+ r- l- U F2 U2 F2 U2 L2 R2 B2 D' F2 U2 B2 U2 L2 R2 B2 (16f*) //u+ d- f++ b++ U B F R' L U' D' B F' U D R L' B' F' D' (16f*) //u+ d- f- b+ U L2 F2 B2 R2 D' F B R2 U2 F B L2 U2 F2 L2 (16f*) //u+ d- f++ l++ U F B L' R U' D' F2 B' U D L R' F' B' D2 (16f*) //u+ d++ f++ b- U B F R L' U' D' B' F' U D R' L B' F' D (16f*) //u+ d+ f- b- U F2 R2 L2 B2 D F2 U2 B U2 R2 L2 D2 F D2 B2 (16f*) //u+ d+ f+ b+ U R' F2 R L' U' D F B' R' L' U R' L F' B D' (17f*) //u+ f++ r++ l- U F U B L2 B R2 F2 U F2 R2 B2 U' D F' U' F2 (17f*) //u+ d+ f++ l++ U D' F' B' L2 B2 U F B' U' D' B' L2 R2 F L2 D2 B (18f*) //u+ f+ r++ l++ U L U D L2 D2 B' F L R' U L R U2 R2 B F' D' (18f*) //u+ d++ r++ l+ U L R F2 B2 U2 L' R' D' F B' L2 F B U2 D2 L2 F2 (18f*) //u+ d+ f++ b++ U' L' U L U L U L' U' R' L' U2 B2 D2 L B2 U2 F2 R2 (19f*) //u+ d++ f++ r+ U2 B2 L B2 D' U R L' B F D U F' R' L D U B' F' (19f*) //u+ d+ f- l+ U F B L2 U D' F' B' U' D L2 F' L R F2 L' R' B' D (19f*) //u+ d+ f+ b- U F B' L' R' U F2 U2 D2 B2 L' R' F' B U D L R2 D (19f*) //u+ f++ b++ l- U R' L' F' B U D R D' F B' R L U' D' R2 U2 F U2 R2 (20f*) //u+ d- f+ r+ U L R B' L2 D2 R2 F2 U D' L U D F' U2 R2 D2 B2 L R' (20f*) //u+ f+ b+ l+ U R L U2 L2 U' D R' L D2 F2 U' D' R L' D' (16f*) //u+ d+ f++ r+ l- U F U2 D2 F B' R L F2 R L B U' D' F2 D (16f*) //u++ d++ f++ r++ l++ U R U D' F' B R L' D' F B2 U' D R' L F B' (17f*) //u+ d- f+ b++ r+ U R L' B' U D F' B R' L U' D F2 R F B' D' (17f*) //u+ d+ f++ b- r+ U D R2 U D' L2 U2 F2 L F2 U2 D2 B2 R' D2 L2 F2 (17f*) //u++ f++ b++ r+ l+ U R U D' F' B R L' D' F2 B2 U' D R' L F B' D' (18f*) //u+ d++ f++ b++ r+ U R L2 U D F' B R' L U' D F2 D R L' F B' D' (18f*) //u+ d++ f++ r+ l++ F B U2 R2 L2 F' B' U R2 F2 U2 R2 F2 R2 D2 R2 F2 D (18f*) //u+ d- f++ r++ l++ U R L U2 L2 F U D F' B' R L' U D' F2 R' F' B D (19f*) //u+ d+ f+ r+ l++ U F2 R L' U' D F B R' L' F' U D' R L F B R2 F2 (19f*) //u+ f+ b++ r- l- U2 F' B' R2 U D B L' R' U' D F B R U' D' F2 L R (19f*) //u+ d+ f++ b+ r- U R2 F R2 B R2 U D R2 L F' B' U' R2 D' F' B' L' D (19f*) //u+ d+ f- b- r++ U R2 F2 B U2 L F2 U2 D2 B2 R D2 B' L2 D F2 R2 L2 B2 (19f*) //u+ d+ f++ r+ l+ U R F2 R' L B2 U D F B R' L U' R' L' F' B L2 D (19f*) //u+ d++ f++ r++ l- U R U D R2 U' D' L U D' R L F2 L2 U' D R L' D' (19f*) //u+ d- f++ r+ l- U R U' D' F' B R L D R2 U2 B U' D R L' B2 D2 F' B' (20f*) //u+ d- f++ b- r+ U D' F B U F' B' U' D' B' U2 F2 B L2 D2 B U2 B R2 B (20f*) //u+ f++ b- r++ l++ U L R' U D' L R' U' D B2 F2 L' R D' (14f*) //u+ d- f++ b++ r- l+ U R L U' D F2 R L' U D R' L B2 D' (14f*) //u+ d+ f++ b++ r+ l+ U R L U2 D2 R' L' F2 B2 U' D' R2 L2 D (14f*) //u++ d++ f++ b++ r++ l++ U R L F2 B2 R' L' D F B R2 L2 F' B' D2 (15f*) //u+ d- f++ b++ r++ l++ U2 R L D' F' B' R2 L2 D2 F B U' R' L' F2 B2 (16f*) //u+ d+ f++ b++ r++ l++ R L' U D' L F B' U D' R L' F' U D' F B' U2 D2 (18f*) //u+ d- f+ b++ r++ l- U F L R' U' D F' B L R2 B2 U D' L' R F B' D (18f*) //u+ d+ f+ b++ r++ l+ R2 U2 L' F2 D2 U2 L2 R2 F2 R' U2 R2 D' L2 B2 F2 R2 U' (18f*) //u+ d+ f++ b++ r- l- F U' D' B R L F' U' D' B R L F U' D' B' R L (18f*) //u+ d+ f+ b+ r- l- U R' F B' D R L' F' U D' L F B' U' R L' B D' (18f*) //u+ d- f+ b- r+ l- U R F' B' L2 B2 U D' R' L B R2 U' D F' B R' L' D (19f*) //u+ d+ f++ b- r+ l++ F U R2 F B' U D F' B L2 U' D' F B D F' B' D2 B (19f*) //u+ d- f+ b+ r++ l++ U R2 U2 D2 L2 F B R L' U' D' B U' D' R' L F B D2 (19f*) //u+ d++ f++ b- r++ l++ F' U D B2 D2 F B' R' L U D' R' F B' U' D L2 B2 R' L' (20f*) //u+ d- f+ b++ r+ l++ U L R U2 D' B2 U R2 D L R' U D L2 R' F2 L D2 R D' (20f*) //u+ d++ f++ b++ r++ l+ U F L2 F R2 F U D' R' D2 R2 F B' U' F B' L2 D2 L' D' (20f*) //u+ d++ f+ b++ r- l- L R D' F' B' L2 R B2 L' F' B' U' L R D2 F L2 F2 B' U2 (20f*) //u+ d+ f+ b- r- l+ U F2 R2 B2 L F2 U2 D2 B2 R' D R2 F2 L2 B R2 U2 D2 L2 F' (20f*) //u+ d+ f+ b+ r+ l+ F U F B' R2 L U' D F' B2 R L' D' R L' B U D' R' B' (20f*) //u+ d- f+ b+ r- l- U D R' L U D' B R L' U D R' L B D2 L2 B' U2 D2 F R2 (21f*) //u+ d+ f+ b+ r+ l-

### Wow

I think it would be *fairly* straightforward to do a subgroup chain with a single middle group, and exhaustively explore each, to get a *much* better estimate (same technique as Reid used so long ago).

Most of the code exists. It's just a question of putting the pieces together, running it, and checking it extensively.

I'd give it a go but I've got too many irons in the fire as it is.

### Middle group

But with some disk-swapping technique on a 8 GB machine a computation should be possible within a reasonable time.

I now ran the two-phase-algorithm on 1000 supercubes for about 20 hours and got the following distribution

18f: 1 19f: 2 20f: 18 21f: 137 22f: 842So I think it is save to say that the average number of moves to solve a supercube optimally is less than 22 moves.

### Disk swapping

As long as you do your breadth-first search as a scan and not

with some sort of random explicit queue, just reading

and writing chunks as needed into and out of memory (or even

using mmap) should work just fine.

It would be a fairly large amount of I/O, but disks are pretty

fast these days, and programmer time is more costly than runtime.

I also suspect just the computation would be greater than the

I/O. I'm not sure on this, though; a little bit of bit twiddling

can go a long way.

We are talking about 1.25T states by 10 moves means 12.5T

transitions; if we can do 1M per second that's 145 days. Oops.

Using symmetry, assuming you can do 1M symmetry-reduced

transitions per second (shouldn't be hard; symmetry is mostly

handled at the outer layer anyway) that's about 9 days. And

you might be able to get a *lot* more than 1M transitions per

second; just put the cheapest transitions in the inner loop.

I think this is very doable. I do not at the moment have a

machine with 40GB of disk space free.

### Very doable

This problem is more than 2.5 times smaller in symmetry-reduced terms than the permutations of the cubies analysis I've done with only 1GB of RAM. In fact you don't even need anywhere near that amount of RAM storage.

You could divide the 1248539443200 positions into smaller sets, and calculate the new positions for the next depth for one of these sets at a time (or a few sets at a time, if memory permits). Choose the sets so that given any element of a known set and one of the ten moves, the resulting position will be from some specific set.

For example, divide into sets according to corner permutation. This will make 40320 sets of 30965760 elements. Symmetry will reduce this to somewhat more than 2520 sets of 30965760 elements. Two bits of RAM per element is sufficient, so the "main array" could be less than 8MB! These sets are small enough you could probably calculate several sets at a time.

To calculate the next depth for a set, you need to read the data for at most ten other sets. Each of the ten moves gives you a different corner permutation, and that corner permutation corresponds to one other set. (You only need to know whether each position in those ten sets were elements of the previous depth. These bits can be checked linearly, so you don't need to consume much memory for that data.) When you're done calculating the new positions for the current set and for the current depth, save the results to a file.

In the permutations of the cubies analysis, I used two sets of files. One set had 4 bits per position, so that the files could contain the exact depth of each position. (For QTM, floor(depth/2) was stored since the LSB of the depth was a fixed value for each set.) The other set had one bit per position, and contained a 1 for each position with exactly a given depth. When processing the next depth, two new sets of files were created, so I would have a total of four sets on disk temporarily.

You might want to choose a larger set so that you have fewer total sets. For example, you could use 256 center configurations of 4877107200 elements each if you have enough memory. Symmetry reduction should reduce this to somewhere around 20 to 25 sets.

In summary, this technique allows the calculation to be done with a rather limited amount of RAM, and a fixed amount of file I/O for each depth calculated. The initial depths will be completely dominated by the file I/O, while the peak depths will be dominated by CPU processing.

### Using GAP, I get 124853944320

Using GAP, I get 1248539443200 for the size of <U,D,L2,R2,F2,B2>. Herbert, are you sure you're not counting unreachable positions?

For the Thistlethwaite phases, I get the following sizes for the supercube.

1: 8192 2: 8660520 3: 235200 4: 5308416

The simplest way to reduce this to three stages would be to combine the first two stages. That is almost 71 billion positions (assuming my figures are correct). I note that I have already done the analysis for the last phase (using only half-turns, not the optimal analysis using all turns). That phase can be solved using no more than 16 half-turns. See: Supercube Squares Group.

A better 3-phase breakdown would be using <U,F,R> and <U,R>. For this I get the following sizes for the phases.

1: 16220160 2: 9289728 3: 587865600

This could be done without resorting to symmetry reduction.

EDIT: Well, this latter 3-phase solution would be rather easy to do a calculation for, but the upper bound will be rather poor. Solving the __ subgroup with only U and R layer turns alone would be at least 20 moves, based upon the normal Rubik's cube.__

### Unreachable positions

If the parity of the middle slice edges is even, the sum of the center twists of the R, F, L and B center facelets is 0 mod 4 (and 2 mod 4 if the parity is odd). So it is impossible to twist for example only the R-center facelet by 180 degrees (r++) in H.

This reduces the number of elements by another factor 2, and we get indeed your number.

## There was a competition in th

There was a competition in the German science magazine Bild der Wissenschaft in 1981 which addressed the supergroup problem. I won the first price by providing a formula for a maneuver which takes as parameters the possible misorientations ou, or, od, ol and ob of the U, R, D, L and B center facelets with the possible values 0, 1, 2 and 3.

If the U center facelet is misoriented for example by 90 degrees clockwise, we have ou=1.

D

_{s}which is equivalent to U'_{s}for example means a slice-turn and is the same as U D' followed by a rotation of the whole cube. In some notations this move is called E.The maneuver-formula is

F

^{ or - 1}L^{ od - 1}U^{- (ou + 1)}B^{- (ob + 2) }F_{s}^{ }D_{s}^{ }F'_{s}^{ }D'_{s}B

^{ ob + 2 }U^{ ou + 1}L^{- (od - 1)}F^{- (or - 1) }D'_{s}^{ }R_{s}^{ }D_{s}L^{od + ob+ ol + 2}^{ }F_{s}^{ }R'_{s}^{ }F'_{s}L^{- (od + ob+ ol + 2)}Applying this maneuver, five of the six center facelets will have the correct orientation. As you might notice, the misorientation of the F center facelet does not appear in the formula. If the sum of all six misorientations is 0 mod 4, then the F center facelet orientation is fixed too, else it will be misoriented by 180 degrees after applying the maneuver and you will have to apply e.g. (F R L F2 R' L')

^{2}to fix it.I must admit, that I rarely used this method to fix the center-orientations, but nevertheless I think it is a quite interesting result which is worth to share.