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

Comment viewing options

Select your preferred way to display the comments and click 'Save settings' to activate your changes.

Solving cosets optimally.

You claim that solving cosets optimally takes 500 times longer. But you can reduce the number of cosets by a factor 2048 by looking at <U,D,R,L,F2,B2> instead, an interesting subgroup.

Can you elaborate on this? C

Can you elaborate on this? Clearly, yes, the count of cosets can be reduced by using a larger group, such as the one you suggest, but in this case the coset is so much larger that a bitmap no longer fits in memory. For the subgroup you suggest, a single bitmap would require 5TB RAM, which is more than I have on any of my machines.

oh no, just your coset

My 'trick' of reducing cosets is just to be modest enough not to do the whole cube. I just meant you use your cosets of <U,D,R2,L2,F2,B2> and restrict to the subgroup <U,D,R,L,F2,B2>. You can either solve this subgroup in itself (no F, F', B, B') or in the whole group, or both and compare.


You know, I may just now understand what you mean. You mean, since the whole cube is still "out of reach" for a full enumeration of the distance spectrum, it would be interesting and perhaps attainable to instead give the distance spectrum for the subgroup (U,D,R,L,F^2,B^2), which is larger than any subgroup solved yet, yet small enough to probably be solved in its entirety at the moment.

That is definitely true, and very interesting. I'd have to calculate a different cover (probably) to handle this efficiently, but I think that's an interesting exploration.

And as you say, there are two distinct problems here: calculate the distance spectrum staying completely within the subgroup (which, for this subgroup, my program is not yet set up to do, but modifications could be made) and calculate the distance spectrum allowing arbitrary HTM moves (which the program can presently do).

Yes, I think this would be a useful thing to investigate.

Yes, that is what I mean

Another thing is that positions in (U,D,R,L,F2,B2) might solve optimally within the subgroup itself in many cases. If this is the case for QTM, then (U,D,R,L,F2,B2) might be a good subgroup for a suboptimal solver for QTM, just as (U,D,R2,L2,F2,B2) is a good subgroup for a suboptimal solver with FTM. A good suboptimal solver for QTM is crucial for a program to compute God's number for QTM.

By way of sampling, one can already compare solving (U,D,R2,L2,F2,B2) within itself to solving with all face turns. The 24q* of superflip and the 26q* position suggest that positions within (U,D,R2,L2,F2,B2) are easier to solve than generic positions in QTM.


I'm terribly sorry. I have no idea what your comment means, or indeed, what overall problem you are trying to solve.

Can you break it down into small chunks for me so I can understand? Perhaps there is some context I am forgetting, or something, but somehow I am just not "getting it".

Maybe if you start with a statement of what you are trying to accomplish, followed by a description of precisely how your approach differs from what has come before, that might clue me in.


Amazing! What about QTM?

Wow! I did not expected this result so soon. What a surprise. Congrats.

What about 26q? Or can I even expect 25q within a year (i.e. a list of all distances > 25 and the number of cube positions belonging to those distances)?


Heh, I'm trying to see if QTM is reasonably feasible. I think there is definitely some low-hanging fruit (I did the 29 bound on my personal machines, so access to a reasonable cluster could probably get 28 fairly easily). But more important is getting the 20f* paper submitted.


Wow ! I find your result absolutely terrific ! I have hoped for this result for many years. Congratulations...
If you are looking for another challenge... find the general formula for Rubik(n) = the number of rotations that are necessary and sufficient to solve an nxnxn Rubik cube... So far we know
Rubik(1) = 0
Rubik(2) = 11
Rubik(3) = 20
Good luck !


As far as I know, we don't even have a 4×4×4 optimal solver. (do we?) So even finding a good lower bound for Rubik(4) won't be easy.

I think QTM-God's Number is a more reasonable goal to reach.

video of the announcement available

I give my congratulations to the team that pulled off this long-awaited achievement.

I have a video of the announcement at the U.S. Nationals Rubik's Cube Championships on YouTube at http://www.youtube.com/watch?v=lvYPrrADHko.


You just solve the most interesting problem ever!

Why did you chose a 22f sequence for superflip applet?

P.S. : http://en.wikipedia.org/wiki/Optimal_solutions_for_Rubik%27s_Cube has to be updated.


Heh, I just put up the sequence that I've had stored under the
filename "superflip" for years; I never updated it to be optimal.
I'll have to fix that; thanks!


If you want to have choice : http://www.mementoslangues.fr/CubeDesign/3xCubes/Superflip.pdf

That's the most complete paper about superflip I know.


Congratulations guys! This is a wonderful achievement, to complete the solution to this central problem after 30 years work.