Discussions on the mathematics of the cube

Rubik Xcode Project

I have put together some source code demonstrating my approach to modeling the Rubik's cube puzzle. I have made an attempt to make the code clear, understandable and well commented. The language is Objective C and makes much use of the Mac OS Foundation and Application kit class libraries. So it is pretty Mac specific although C++ programmers may wish to browse the source files for ideas. Although the syntax is different, as object oriented languages C++ and Objective C bear many similarities.

Those interested may download the Rubik Xcode Project from my web site.

1,000,000 cubes optimally solved

Using my relatively new Core i7 920 CPU machine (Linux 64-bit with 12GB of RAM) I solved 1,000,000 random cubes optimally at a rate of about 20 cubes per minute. The computation took about four weeks (I also used a few other slower boxes to do some of them). I got the following results:
12f*: 1
13f*: 14
14f*: 172
15f*: 2063
16f*: 26448
17f*: 267027
18f*: 670407
19f*: 33868
No 20f* cube was encountered, which is as expected. No symmetrical or anti-symmetrical positions were encountered.

These results are very close to Kociemba's results for 100,000 cubes; much closer to his overall predictions than those extrapolated from the 250 cosets I ran completely. This seems to indicate that running random cubes may be a more effective way to get a distribution estimate than by running many fewer random cosets (but which contain collectively many more individual positions).

Void cube diameter at least 20 (face turn metric)

The void cube is the 3x3 without centers. For every legal 3x3 void position, there are 12 possible ways the centers can be inserted to yield a legal 3x3 cube position. (Pick any of the six colors for the top, then pick one of the adjacent four colors for the front; half of the time the result will have the wrong axis parity).

The "superflip" void position has a distance of 20. This can be shown by computing the optimal solution for all 12 axis insertions in the 3x3 cube; this yields only three unique positions (mod M), and all three have a distance of 20.

U1F1U2F1L2B1U2F1L3R3F2D1R2U2L2B1F3L1F2D1 (20f*) //superflip

An analysis of the corner and edge orientations of the 3x3x3 cube

An analysis of the corner and edge permutations of the 3x3x3 cube has already been done by Bruce Norskog. His results for the quarter-turn metric are:
Distance       Positions    
--------       ---------    
 0q                    1    
 1q                   12    
 2q                  114    
 3q                1,068    
 4q               10,011    
 5q               93,840   
 6q              877,956   
 7q            8,197,896   
 8q           76,405,543   
 9q          710,142,108   
10q        6,565,779,580   
11q       59,762,006,092   
12q      506,821,901,799

An interesting conjugate class

As you know the number of conjugate classes of the cube is 81120.

Unfortunately as far as I know there is no fast way to calculate the optimal distances distribution for a chosen conjugacy class. The only way is to search for the optimal distance of each position one by one. That is what I did for the following conjugacy class:

CE x CC : 1_1_1_1_1_1_1_1_4 x 1_1_1_1_4

which has 495*6*2^3*70*6*3^3 = 269438400 positions and which include the 12 cube generators.

I did this search however only for one orientation which reduced the number to 495*6*70*6 = 1247400 positions. Here is the optimal distribution:

New estimate for 20f*: 300,000,000

Over the past few weeks I've run 250 random cosets of the Kociemba group, each with 19,508,428,800 positions, out to completion, calculating an optimal solution to all. This is a total of 4,877,107,200,000 positions, almost all unique modulo M+inv. I ran these to try to get a better estimate of the total count of 20f* positions and also to compare the overall histogram of position depths against my previous work to calculate the exact count of 13f* positions, and Kociemba's recent experiment to optimally solve a one hundred thousand random cube positions.

Of these 250 random cosets, 232 had absolutely no distance-20

Syllables and Graphs

I've been reading a little bit about graph theory, and I wish I knew more about it.  So pardon what may perhaps be a bit of naiveté about graphs on my part.

I suspect that everyone who reads this forum is familiar with Cayley graphs and how they relate to Rubik's cube space.  One of the best references in this regard may be found at http://www.jaapsch.net/puzzles/cayley.htm  I also suspect who everyone reads this forum is familiar with the concept of doing a breadth first search while storing all the results as a way of investigating a space such as the Cayley graph for Rubik's cube.

Fast solver for arbitrary target groups

As you know one of the breakthrough of cube computing is Silviu's successful depth calculation of all symmetrical positions. This breakthrough used a two phase algorithm that has the symmetrical positions as its target group. Regular solvers will simply stop once they hit the position they want to solve but Silviu's idea is to never stop until all positions in the target group are hit... This way of solving is very fast and it is what Rokiki has used to calculate the "group that fixes the edges".

My question is can this be applied to arbitrary target groups whose elements share something in common? for example let's say my target group is some conjugacy class of the cube.


I modified kociemba's optimal solver so that it calculates the depth of sequences in a Depth-first search manner.

The moves order I used is URFDLBU'R'F'D'L'B'.

Here are the initial results after an hour or so of running :
initializing memory.
initializing tables.........................................................
loading pruning table (538 MB) from disk................
-1                               UU
--2                              UUR
---3                             UURU
----4                            UURUU
-----5                           UURUUR
------6                          UURUURU
-------7                         UURUURUU
--------8                        UURUURUUR
---------9                       UURUURUURU
----------10                     UURUURUURUU
-----------11                    UURUURUURUUR
------------12                   UURUURUURUURU
-------------13                  UURUURUURUURUU
-------------14                  UURUURUURUURUUR
---------------15                UURUURUURUURUURU
----------------16               UURUURUURUURUURUU
---------------15                UURUURUURUURUURUR
---------------15                UURUURUURUURUURUF
---------------15                UURUURUURUURUURUD
---------------15                UURUURUURUURUURUL
-----------------17              UURUURUURUURUURULU
----------------16               UURUURUURUURUURULR
----------------16               UURUURUURUURUURULF
------------------18             UURUURUURUURUURULFU
-----------------17              UURUURUURUURUURULFR
-----------------17              UURUURUURUURUURULFF
-----------------17              UURUURUURUURUURULFD
-----------------17              UURUURUURUURUURULFL
-----------------17              UURUURUURUURUURULFB
-------------------19            UURUURUURUURUURULFBU
------------------18             UURUURUURUURUURULFBR
------------------18             UURUURUURUURUURULFBF
------------------18             UURUURUURUURUURULFBD
--------------------20           UURUURUURUURUURULFBDU
-------------------19            UURUURUURUURUURULFBDR
-------------------19            UURUURUURUURUURULFBDF
-------------------19            UURUURUURUURUURULFBDD
-------------------19            UURUURUURUURUURULFBDL
-------------------19            UURUURUURUURUURULFBDB
-------------------19            UURUURUURUURUURULFBDU'
-------------------19            UURUURUURUURUURULFBDR'
-------------------19            UURUURUURUURUURULFBDF'
-------------------19            UURUURUURUURUURULFBDL'
-------------------19            UURUURUURUURUURULFBDB'
-------------------19            UURUURUURUURUURULFBL
------------------18             UURUURUURUURUURULFBB
------------------18             UURUURUURUURUURULFBU'
------------------18             UURUURUURUURUURULFBR'
--------------------20           UURUURUURUURUURULFBR'U
-------------------19            UURUURUURUURUURULFBR'F
-------------------19            UURUURUURUURUURULFBR'D
-------------------19            UURUURUURUURUURULFBR'L
-------------------19            UURUURUURUURUURULFBR'B
---------------------21          UURUURUURUURUURULFBR'BU
--------------------20           UURUURUURUURUURULFBR'BR
--------------------20           UURUURUURUURUURULFBR'BF
--------------------20           UURUURUURUURUURULFBR'BD
--------------------20           UURUURUURUURUURULFBR'BL
--------------------20           UURUURUURUURUURULFBR'BB
--------------------20           UURUURUURUURUURULFBR'BU'
--------------------20           UURUURUURUURUURULFBR'BR'
--------------------20           UURUURUURUURUURULFBR'BF'
--------------------20           UURUURUURUURUURULFBR'BD'
--------------------20           UURUURUURUURUURULFBR'BL'
--------------------20           UURUURUURUURUURULFBR'U'
-------------------19            UURUURUURUURUURULFBR'R'
-------------------19            UURUURUURUURUURULFBR'F'
-------------------19            UURUURUURUURUURULFBR'D'
-------------------19            UURUURUURUURUURULFBR'L'
-------------------19            UURUURUURUURUURULFBR'B'
-------------------19            UURUURUURUURUURULFBF'
------------------18             UURUURUURUURUURULFBD'
------------------18             UURUURUURUURUURULFBL'
--------------------20           UURUURUURUURUURULFBL'U
-------------------19            UURUURUURUURUURULFBL'R
-------------------19            UURUURUURUURUURULFBL'F
---------------------21          UURUURUURUURUURULFBL'FU
--------------------20           UURUURUURUURUURULFBL'FR
--------------------20           UURUURUURUURUURULFBL'FF
--------------------20           UURUURUURUURUURULFBL'FD
--------------------20           UURUURUURUURUURULFBL'FL
--------------------20           UURUURUURUURUURULFBL'FB
--------------------20           UURUURUURUURUURULFBL'FU'
----------------------22         UURUURUURUURUURULFBL'FU'U
---------------------21          UURUURUURUURUURULFBL'FU'R
---------------------21          UURUURUURUURUURULFBL'FU'F
---------------------21          UURUURUURUURUURULFBL'FU'D
---------------------21          UURUURUURUURUURULFBL'FU'L
---------------------21          UURUURUURUURUURULFBL'FU'B
---------------------21          UURUURUURUURUURULFBL'FU'U'
---------------------21          UURUURUURUURUURULFBL'FU'R'
---------------------21          UURUURUURUURUURULFBL'FU'F'
---------------------21          UURUURUURUURUURULFBL'FU'D'
---------------------21          UURUURUURUURUURULFBL'FU'L'
---------------------21          UURUURUURUURUURULFBL'FU'B'
---------------------21          UURUURUURUURUURULFBL'FR'
--------------------20           UURUURUURUURUURULFBL'FD'
--------------------20           UURUURUURUURUURULFBL'FL'
--------------------20           UURUURUURUURUURULFBL'FB'
--------------------20           UURUURUURUURUURULFBL'D
---------------------21          UURUURUURUURUURULFBL'DU
--------------------20           UURUURUURUURUURULFBL'DR
--------------------20           UURUURUURUURUURULFBL'DF
--------------------20           UURUURUURUURUURULFBL'DD
--------------------20           UURUURUURUURUURULFBL'DL
--------------------20           UURUURUURUURUURULFBL'DB
--------------------20           UURUURUURUURUURULFBL'DU'
--------------------20           UURUURUURUURUURULFBL'DR'
--------------------20           UURUURUURUURUURULFBL'DF'
--------------------20           UURUURUURUURUURULFBL'DL'
--------------------20           UURUURUURUURUURULFBL'DB'
--------------------20           UURUURUURUURUURULFBL'B
-------------------19            UURUURUURUURUURULFBL'U'
-------------------19            UURUURUURUURUURULFBL'R'
-------------------19            UURUURUURUURUURULFBL'F'
-------------------19            UURUURUURUURUURULFBL'D'
-------------------19            UURUURUURUURUURULFBL'L'
-------------------19            UURUURUURUURUURULFBL'B'
-------------------19            UURUURUURUURUURULFU'
-----------------17              UURUURUURUURUURULFR'
-----------------17              UURUURUURUURUURULFD'
-----------------17              UURUURUURUURUURULFL'
-------------------19            UURUURUURUURUURULFL'U
------------------18             UURUURUURUURUURULFL'R
------------------18             UURUURUURUURUURULFL'F
--------------------20           UURUURUURUURUURULFL'FU
-------------------19            UURUURUURUURUURULFL'FR
-------------------19            UURUURUURUURUURULFL'FF
-------------------19            UURUURUURUURUURULFL'FD
-------------------19            UURUURUURUURUURULFL'FL
---------------------21          UURUURUURUURUURULFL'FLU
--------------------20           UURUURUURUURUURULFL'FLR
--------------------20           UURUURUURUURUURULFL'FLF
--------------------20           UURUURUURUURUURULFL'FLD
--------------------20           UURUURUURUURUURULFL'FLL
--------------------20           UURUURUURUURUURULFL'FLB
--------------------20           UURUURUURUURUURULFL'FLU'
--------------------20           UURUURUURUURUURULFL'FLR'
--------------------20           UURUURUURUURUURULFL'FLF'
--------------------20           UURUURUURUURUURULFL'FLD'
--------------------20           UURUURUURUURUURULFL'FLB'
--------------------20           UURUURUURUURUURULFL'FB
-------------------19            UURUURUURUURUURULFL'FU'
-------------------19            UURUURUURUURUURULFL'FR'
-------------------19            UURUURUURUURUURULFL'FD'
-------------------19            UURUURUURUURUURULFL'FL'
-------------------19            UURUURUURUURUURULFL'FB'
-------------------19            UURUURUURUURUURULFL'D
------------------18             UURUURUURUURUURULFL'B
------------------18             UURUURUURUURUURULFL'U'
------------------18             UURUURUURUURUURULFL'R'
------------------18             UURUURUURUURUURULFL'F'
------------------18             UURUURUURUURUURULFL'D'
------------------18             UURUURUURUURUURULFL'L'
------------------18             UURUURUURUURUURULFL'B'
------------------18             UURUURUURUURUURULFB'
-----------------17              UURUURUURUURUURULD
------------------18             UURUURUURUURUURULDU
-----------------17              UURUURUURUURUURULDR
-------------------19            UURUURUURUURUURULDRU
--------------------20           UURUURUURUURUURULDRUU
-------------------19            UURUURUURUURUURULDRUR
-------------------19            UURUURUURUURUURULDRUF
-------------------19            UURUURUURUURUURULDRUD
-------------------19            UURUURUURUURUURULDRUL
-------------------19            UURUURUURUURUURULDRUB
-------------------19            UURUURUURUURUURULDRUR'
-------------------19            UURUURUURUURUURULDRUF'
-------------------19            UURUURUURUURUURULDRUD'
-------------------19            UURUURUURUURUURULDRUL'
-------------------19            UURUURUURUURUURULDRUB'
-------------------19            UURUURUURUURUURULDRR
------------------18             UURUURUURUURUURULDRF
------------------18             UURUURUURUURUURULDRD
------------------18             UURUURUURUURUURULDRL
------------------18             UURUURUURUURUURULDRB
------------------18             UURUURUURUURUURULDRU'
------------------18             UURUURUURUURUURULDRF'
------------------18             UURUURUURUURUURULDRD'
------------------18             UURUURUURUURUURULDRL'
------------------18             UURUURUURUURUURULDRB'
------------------18             UURUURUURUURUURULDF
-----------------17              UURUURUURUURUURULDD
-----------------17              UURUURUURUURUURULDL
-----------------17              UURUURUURUURUURULDB
-----------------17              UURUURUURUURUURULDU'
-----------------17              UURUURUURUURUURULDR'
-----------------17              UURUURUURUURUURULDF'
-------------------19            UURUURUURUURUURULDF'U
------------------18             UURUURUURUURUURULDF'R

Commutator elements of the cube

I was wondering if the number of commutator elements of the cube is known?

Commutator elements are of the form ABA'B' where A and B are some sequences.

It seems that the subgroup generated by the commutator elements is half the size of the cube, but is it the case that every element of the commutator subgroup is a commutator element? if not how many are they and how far they are from solved?