God's Number is 20
Submitted by rokicki on Sun, 08/08/2010 - 15:58.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/.
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
Submitted by B MacKenzie on Thu, 08/05/2010 - 23:42.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
» 24 comments | read more
15f* = 91365146187124313
Submitted by rokicki on Thu, 07/29/2010 - 00:34.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.
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
Submitted by kociemba on Thu, 07/15/2010 - 05:10.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.
» 5 comments | read more
God's Algorithm out to 17q*
Submitted by tscheunemann on Wed, 07/14/2010 - 15:25.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
» 9 comments | read more
God's Algorithm out to 16q*
Submitted by tscheunemann on Fri, 07/09/2010 - 05:06.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.
» 9 comments | read more
even and odd cube positions
Submitted by tscheunemann on Tue, 07/06/2010 - 12:00.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 0so 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
» 8 comments | read more
God's Algorithm out to 14f*
Submitted by tscheunemann on Wed, 06/23/2010 - 15:13.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 6989320578825358I 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.
» 12 comments | read more
3-face subgroup of the 3x3x3 cube
Submitted by secondmouse on Fri, 05/07/2010 - 08:36.Somewhat surprisingly I was unable to find any tables for
the number of positions of various lengths in ascending order
for this order 170659735142400 group w.r.t. three mutually orthogonal face generators such as U,F and R, i.e.
This is seemingly beyond the reach of conventional software tools to solve, so I am appealing to the seemingly large number of contributors who have developed their own bespoke utilities. I'd be grateful if a table could be posted here. In particular is the diameter of the Cayley graph for this known?