Supergroup knowledge

I'm going to have to play with this sequence; this looks very neat.
(And very useful, as the most concise "solution" to fixing the center
orientations I have ever seen).

I now added support for the supergroup to Cube Explorer and was able to compute optimal maneuvers for all 73 nontrivial cases (up to symmetry and inversion) which just change the center facelet twists. There is one single situation which needs 21 moves (Symmetry type C4). Together with Tom Rokickis result this shows, that the supergroup needs at most 43 moves - which is of course quite a bad estimation. The comments behind the maneuver I added manually, I hope there are not too many typos there.

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-

Gotta download that new version; congratulations!

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.

Yes, this is absolutely correct. The two-phase-algorithm implementation target group for phase 1 I use is the same as for the standard cube: H=<U,D,R2,F2,L2,B2> . But here it has 40320*40320*12*128=2,497,078,886,400 elements, because there are 128 possible centertwist within this subgroup. It needs 13 moves max to go to this subgroup from an arbitrary cube but the size of H is too big for me to to determine the diameter. With symmetry reduction and using two bits/element we still need about 39 GB RAM.

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:    842

So I think it is save to say that the average number of moves to solve a supercube optimally is less than 22 moves.

I think the "disk swapping" required here is pretty minimal.
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.

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 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.

I think you are right. I overlooked the dependence between the parity of the four middle slice edges and the twist of the R,F,L and B center facelets in H=<U,D,L2,R2,F2,B2>.
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.