Discussions on the mathematics of the cube

God's Algorithm out to 15f*

Yeah, I know this is kind of late, but as promised (or threatened) I have finished my 15f* calculation and here are the results, first positions at exactly that distance (adding a few minor numbers):
 d  (mod M + inv)*     mod M + inv       mod M             positions
--- --------------- ---------------- ---------------- -----------------
 0                1                1                1                 1
 1                2                2                2                18
 2                8                8                9               243
 3               48               48               75              3240
 4              517              509              934             43239
 5             6359             6198            12077            574908
 6            81541            80178           159131           7618438
 7          1067047          1053077          2101575         100803036
 8         14034826         13890036         27762103        1332343288
 9        184907170        183339529        366611212       17596479795
10       2437753739       2419418798       4838564147      232248063316
11      32135500721      31909900767      63818720716     3063288809012
12     423434369503     420569653153     841134600018    40374425656248
13    5575030719304    5538068321152   11076115427897   531653418284628
14   73286135656774   72805484795034  145610854487909  6989320578825358
15  957963000510751  951720657137855 1903440582318440 91365146187124313

Slice turn metric, anyone?

Anyone got a reasonable upper or lower bound for slice turn metric? (Clearly, the 20 result gives us a trivial upper bound of 20.) Lower bounds? Here are position count results; these are the easy ones. I'm hoping this table will magically extend itself. First table is exact count at that level:
dist mod M+inv       mod M     positions
 0           1           1             1
 1           4           4            27
 2          13          19           501
 3         150         236          9175
 4        1920        3642        164900
 5       31341       61457       2912447

God's Number is 20

Every position of Rubik's Cube™ can be solved in twenty moves or less.

With about 35 CPU-years of idle computer time donated by Google, a team of researchers has essentially solved every position of the Rubik's Cube™, and shown that no position requires more than twenty moves.

This was a joint effort between Morley Davidson, John Dethridge,
Herbert Kociemba, and Tomas Rokicki.

More details are posted at http://cube20.org/.

C3v Three Face Group

In a previous thread the C3v Three Face Group (RUF group, etc.) was discussed. I have since been fooling around with the group and tried my hand at writing a coset solver for it. I thought I might report some results from this.

Here are the states at depth enumerations for the three face edges only group and the three face corners only group:

C3v Three Face Edges Group: States at Depth

15f* = 91365146187124313

The number of positions at distance 15 in the face turn metric is 91,365,146,187,124,313.

This result is from a collaboration between Morley Davidson, John Dethridge, Herbert Kociemba, and Tomas Rokicki.

More details will be forthcoming in a future announcement.

Relation between positions and positions mod M in FTM

Tom proposed that I give the relation between the number Nm of positions mod M and the number of positions N in the way N = 48*Nm - constant C. This is indeed possible, because the symmetric positions of the cube are completely analyzed.

God's Algorithm out to 17q*

Well it's done. Here are the results in the Quarter Turn Metric for positions at exactly that distance:
 d  (mod M + inv)*   mod M + inv       mod M             positions
-- --------------- --------------- --------------- -----------------
 0               1               1               1                 1
 1               1               1               1                12
 2               5               5               5               114
 3              17              17              25              1068
 4             135             130             219             10011
 5            1065            1031            1978             93840
 6            9650            9393           18395            878880
 7           88036           86183          171529           8221632
 8          817224          802788         1601725          76843595
 9         7576845         7482382        14956266         717789576
10        70551288        69833772       139629194        6701836858
11       657234617       651613601      1303138445       62549615248
12      6127729821      6079089087     12157779067      583570100997
13     57102780138     56691773613    113382522382     5442351625028
14    532228377080    528436196526   1056867697737    50729620202582
15   4955060840390   4921838392506   9843661720634   472495678811004
16  46080486036498  45766398977082  91532722388023  4393570406220123
17 426192982714390 423418744794278 846837132071729 40648181519827392

God's Algorithm out to 16q*

So switching to edge cube positions as cosets (instead of corner cube positions and twist) made a huge impact on the calculation, but more on that later. So my results for up to 16q* for positions at exactly that distance are:
 d (mod M + inv)*     positions
-- -------------- ----------------
 0              1                1
 1              1               12
 2              5              114
 3             17             1068
 4            135            10011
 5           1065            93840
 6           9650           878880
 7          88036          8221632
 8         817224         76843595
 9        7576845        717789576
10       70551288       6701836858
11      657234617      62549615248
12     6127729821     583570100997
13    57102780138    5442351625028
14   532228377080   50729620202582
15  4955060840390  472495678811004
16 46080486036498 4393570406220123
* The (mod M + inv) column means symmetry reduced postions but only considering the edge cube positions. I just included it because I had those numbers. It is not comparable to earlier calculations because it may include duplicate positions of the full cube and is dependent on what cosets are used in the calculation.

even and odd cube positions

After calculating 14f* and 15f* being at bit out of range, I started calculations in the quarter turn metric and just for the heck of it I switched to edge cube positions as cosets. I am in the process of verifying 15q*, which will take about 24 hours on a total of 120 cores. In the process I noticed something strange in my output. For coset 0 I get:
0 11 1 0 0
0 12 1 121477 121477
0 13 1 0 0
0 14 1 2981152 2981152
0 15 1 0 0
so I only have positions for coset 0 at even depths (12 and 14) and none at odd depths (11, 13 and 15). I get the same for coset 1:
1 11 12 4284 51408

God's Algorithm out to 14f*

Here are the results for postions at exactly that distance:

 d   mod M + inv          mod M       positions
-- -------------- --------------- ----------------
 9      183339529       366611212      17596479795
10     2419418798      4838564147     232248063316
11    31909900767     63818720716    3063288809012
12   420569653153    841134600018   40374425656248
13  5538068321152  11076115427897  531653418284628
14 72805484795034 145610854487909 6989320578825358
I had the good fortune to run a few test calculations on a brand new Cray XT6m with over 4000 Opteron cores. As I have done in the past I tried my own program for rubiks cube calculation. Results looked promising and after some optimisations I was able to complete the calculation out to 14 moves in the full turn metric in a about nine days. If I had been able to use the entire machine alone it should have taken a bit over a day.