Discussions on the mathematics of the cube

Presentation for Rubik's cube

I just found a recent post by "secondmouse" on sci.math that deserves a wider audience. I'll quote it here in full.
I found the following short presentation for the
miniature 2x2x2 Rubik's cube of order 3674160:

    < a,b,c | a^4 = b^4 = c^4 = 1,
                 ababa = babab,
                 bcbcb = cbcbc,
                 abcba = bcbac,
                 bcacb = cacba,
                 cabac = abacb,
                 (ac)^2 (ab)^3 (cb)^2 = 1 >

See the following link for more info as to why

1,000,000 cubes optimally solved in both QTM and FTM

I have solved all 1,000,000 random cube positions from the earlier article now in both QTM and HTM. Here is the resulting grid:
    12h 13h 14h  15h   16h    17h    18h   19h     sum
15q   1   1   3    2     -      -      -     -       7
16q   -   2  18   48    35      -      -     -     103
17q   -   3  23  143   347    354      -     -     870
18q   -   5  40  305  1713   4520   2034     -    8617
19q   -   1  40  505  5190  29711  33363   474   69284
20q   -   2  39  674  9932 100164 212466  7213  330490
21q   -   -   9  345  7697 104052 301668 16371  430142
22q   -   -   -   41  1533  28173 120449  9720  159916

Largest coset solved yet of actual Rubik's positions

Using Tom Rokicki's coset solver as well as his optimal solver I managed to do a full analysis of the corner and edge permutations of all the 3x3x3 cube positions that have the orientation in the solved state.

Here is the distribution table:
0              1
1              4
2             10
3             36
4            123
5            368
6           1336
7           4928
8          16839
9          63920
10        257888
11       1019992
12       4317941
13      20240924
14     102343680
15     568081384
16    3458261494
17   22676234692
18  153062896516

Positions with the same distance in both QTM and FTM

Does anyone know the number of positions that have the same distance in both QTM and FTM metrics? These are positions similar to:
do nothing                                      (0q* , 0f*)
U                                               (1q* , 1f*) 
U R                                             (2q* , 2f*) 
F B U D R L F B U D R L 	                (12q*, 12f*)
F B U D R L F' B' U' D' R' L' 	                (12q*, 12f*)
F' B' R' L' F B U D R' L' U' D'  	        (12q*, 12f*) 
F B R' L' F B U' D' R L U' D'  	                (12q*, 12f*)
F U F' R B U D' L' D' R U R L' F' D' B L' B'  	(18q*, 18f*)

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