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

## Comment viewing options

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

### Can you elaborate on this? C

Submitted by rokicki on Wed, 09/15/2010 - 18:27.

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

Submitted by brac37 on Thu, 09/16/2010 - 16:48.

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,R

^{2},L^{2},F^{2},B^{2}> and restrict to the subgroup <U,D,R,L,F^{2},B^{2}>. You can either solve this subgroup in itself (no F, F', B, B') or in the whole group, or both and compare.### Ahh

Submitted by rokicki on Mon, 09/20/2010 - 15:07.

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.

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

Submitted by brac37 on Mon, 09/20/2010 - 18:15.

Another thing is that positions in (U,D,R,L,F

By way of sampling, one can already compare solving (U,D,R

^{2},B^{2}) might solve optimally within the subgroup itself in many cases. If this is the case for QTM, then (U,D,R,L,F^{2},B^{2}) might be a good subgroup for a suboptimal solver for QTM, just as (U,D,R^{2},L^{2},F^{2},B^{2}) 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,R

^{2},L^{2},F^{2},B^{2}) within itself to solving with all face turns. The 24q* of superflip and the 26q* position suggest that positions within (U,D,R^{2},L^{2},F^{2},B^{2}) are easier to solve than generic positions in QTM.### Confused

Submitted by rokicki on Mon, 09/20/2010 - 15:00.

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.

-tom

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.

-tom

### Amazing! What about QTM?

Submitted by brac37 on Thu, 08/19/2010 - 11:34.

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)?

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)?

### QTM

Submitted by rokicki on Sun, 08/22/2010 - 01:19.

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.

### 20

Submitted by crepeau on Wed, 08/11/2010 - 07:24.

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 !

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 !

### video of the announcement available

Submitted by Bruce Norskog on Mon, 08/09/2010 - 11:07.

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.

### Congratulations!

Submitted by Rafoo on Mon, 08/09/2010 - 02:53.

Congratulations!

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.

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.

## Solving cosets optimally.

^{2},B^{2}> instead, an interesting subgroup.