JAMES GRIME: They wanted to find out the number of moves
it would take to solve the most difficult combination.
And this number would be called God's number.
If you have perfect knowledge of how to do the Rubik's cube,
you would be able to solve the most difficult position in its
perfect, most efficient algorithm.
MATT PARKER: Obviously if you get a solved cube and you
twist one bit, you've just got to twist it back.
So it could be one, or it could be two twists, or it
could be five or so on.
But what's the most you're going to need?
It turns out, for a long time we didn't know.
JAMES GRIME: So they knew that the number of combinations for
the Rubik's cube was this huge number.
It was 43 quintillion.
And if you turn a piece 17 times, if you do 17 moves, the
number of combinations you can reach is less than this
massive number, 43 quintillion.
So if you want to be able to solve all combinations, it's
definitely more than 17 because there's so many you
can't even reach.
And they managed to work out that there was less than 30.
And over the years, they started to whittle this down,
closer and closer.
TONY JIANG: As you can tell, I'm not really fast, but I'm
not too slow, either.
MATT PARKER: It was 2010 was the first time we actually
knew for sure no matter how much you scramble up a Rubik's
cube, you can solve it in 20 or fewer twists.
It's often called God's number.
It's called God's number because you have to be some
kind of omniscient being to work out those 20 moves.
It's so difficult to calculate what those moves are.
KATIE STECKLES: I couldn't look at a cube and say, oh I
need to do these 12 moves or whatever.
But there are people who can.
So they do Rubik's cube solving competitions.
And they have, obviously, speed challenges to see who
can solve it the fastest.
But one of the other things that they do is a efficient
solve competition.
And the competition there is look at a Rubik's cube and
then just write down a list of moves that will solve it.
The world record for that is 23 moves.
And obviously that was for a particular
scramble of the cube.
And it may have been that the actual, most efficient way to
solve that was fewer than 20.
But a human can look at it and actually write down a list of
23, which I think is probably more impressive than people
who can solve it really quickly.
MATT PARKER: You might think, well how do we know?
How do we know that?
Did we just check all 43.25 billion billion different ways
of solving it?
And we effectively did that.
JAMES GRIME: A move, by the way, is a quarter turn, or
quarter turn the other way, or half turn.
That counts.
So anything that you move counts as a move.
All right, so a quarter turn, a quarter turn, or a half
turn, those all counts as one.
MATT PARKER: So guys got the Rubik's cube and they try to
look at all the possible combinations.
And they realized that actually you don't have to
check all of them, because some of them are the same.
And so they used arguments from symmetry, saying, in
fact, being mixed up this way is actually the same as being
mixed up that way.
It's the same way to solve it and so on and so on.
And so they managed to whittle down the number of ones they
have to check.
And this is one of those wonderful things where you do
a proof by exhaustion.
JAMES GRIME: They found a very difficult position.
It was called the superflip.
Now the superflip is essentially completely solved
except each edge position was flipped over.
Now that would be a very difficult position to solve.
They realized that you could solve that position, the
superflip, in 20 moves.
And they proved that you couldn't do it in anything
less than 20 moves.
So you couldn't do it in 19 or 18, nothing less.
So 20 moves.
So they thought, great.
Maybe 20 is God's number.
MATT PARKER: And to do a proof by exhaustion, you have to do
two things.
You've got to first of all reduce the number of cases you
need to check as much as you can.
Secondly, you've got to get very clever
ways of checking them.
And so they got better and better computer programs and
also more and more powerful computers.
So they just crossed.
So they had reduced the number of cases far enough.
They had a fast enough computer with a smart enough
program to check that many.
And they could run it.
I've been to the place where they actually did the
computation.
It was at the Google headquarters in San Francisco,
just outside San Francisco.
And Google, because it's run by benevolent nerds, let
people use their mind bogglingly powerful computer.
The amount of computer power that Google has is phenomenal.
They don't use it all of it all the time.
And so if you come up with an interesting enough reason,
they will let you come and play around on their
incredible computer processing power.
You've got prove that your code's not going to
run amok, et cetera.
And that's what these guys did.
They had their code that checked the
reduced number of cases.
They ran it on the Google servers.
And they did.
They exhaustively checked.
And we know now, for a fact--
JAMES GRIME: --that God's number is 20.
Every Rubik's puzzle can be solved in 20 or fewer moves.
MATT PARKER: I'm actually involved at the moment in a
attempt to set the world record for the most people
solving a Rubik's cube simultaneously.
So we're going to try and get 2000 school students into the
O2 venue in London.
And we're going to try and break the simultaneous solving
world record.
And it's for a charity.
So the DePaul charity has organized this.
Rubik's is sponsoring it.
And any school in the UK can enter.
It's on the 21st of November.
So if you go to the DePaul website--
Or I imagine, this is the internet.
We can probably hyperlink this information beneath the video.
Schools can get involved.
I'm involved.
It's the charity I do charity work for.
It's to stop young people from becoming homeless, which I
think is fair enough.
I'm hosting the event.
So I'll be there on the 21st wandering around talking about
math and how wonderful it is.
And I'm developing resources.
So I've developed videos and worksheets for teachers to use
to teach students how to solve the Rubik's cube.