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.
