Note: Where available, the PDF/Word icon below is provided to view the complete and fully formatted document
Disclaimer: The Parliamentary Library does not warrant or accept liability for the accuracy or usefulness of the transcripts. These are copied directly from the broadcaster's website.
God's Algorithm -

God's Algorithm

Close to the Rubik's Cube's 30th birthday it was also announced that the holy grail of cubing had
been found. It's called "God's Number" - the fewest number of moves it takes to solve the cube from
any starting point. If you thought solving the cube was hard for your tiny brain, be reassured that
it took a network of computers years to find "God's Number"

NARRATION

Back in the 80's, it seemed everyone wanted to solve a Rubik's Cube.

Molly Meldrum

Do any of you know how to do this thing?

Audience

Yeah.

NARRATION

So much so, it's inventor - Professor Erno Rubik, was treated like a rock star. But even he
couldn't solve the cube's greatest mathematical mystery.

It's generated a problem that's taken some great minds three decades to bust.

NARRATION

It's called "God's Number". Why? Well, it's the idea that if you asked God to solve a mixed up
cube, he'd always be able to do it in the least number of moves. For the simplest mix-up, it takes
just one.

Dr Graham Phillips

But what about the hardest, most scrambled cube possible? How many moves would that take? Well
that's what's known as Gods number.

I've twisted that cube three times, that can't be solved in only two moves- so God's number can't
be two it has to be more than two, so by finding complicated cubes you can keep pushing god's
number up and up and up.

NARRATION

The problem is there are 43 quintillion possible combinations - and finding the perfect solution
for each one is beyond even the most talented mere mortal.

Dr Graham Phillips

How many moves do you solve it in?

Felix Zemdegs

Usually it would take me about 50, 55 moves to solve it.

NARRATION

Fifteen year old Feliks Zemdegs is the fastest cube solver on the planet - his world record stands
at 6.65 seconds. And to reach that speed, he has just fractions of a second to choose a number of
algorithms from the hundred or so he's memorised.

Felix Zemdegs

Algorithm is basically a sequence of moves, it could be anywhere from one move to 20 moves or so
that does a particular thing that you want it to do, like move the three corners around, in a
particular way or something like that.

We've known for a long time that there was a cube that took 20 moves to solve. And then we come at
it from above showing that every cube could be solved in 70 moves, in 56, in 28 and you slowly
bring those numbers together and eventually you trap the number from above and below.

NARRATION

It had taken 25 years to prove that any cube could be solved in just 26 moves when Californian
computer programmer Tom Rockeki took on the challenge. He lost sleep in the process!

Tom Rokicki

For five years solid, every night as I lie down I was always thinking what's the next step? How can
I make this faster? What's the next improvement I can make.

NARRATION

Tom's first three attempts brought the upper limit on God's number down to 22 moves. Then in one
last try he put together a team that included John Dethridge, an Australian computer programmer

John Dethridge

We discussed back and forth a lot of the algorithms he was working on and I eventually said think
big Tom, if you are going to prove the actual number, how much computer time would you need and he
said about 35 years at home and I said well at Google we've got plenty of left over computer time
that we can donate to that.

Dr Graham Phillips

Now 43 billion billion different combinations is even too many for Google's computers so the first
thing the guys had to do is break that number down into a number of manageable pieces.

Tom Rokicki

By breaking it up into 55 million problems, each of which worked on billions of positions, you
could distribute it on a whole bunch of computers and that was really the key thing.

NARRATION

Thirty five years worth of computing time later, Tom and his team had the answer.

NARRATION

So what is God's number?

Tom Rokicki

God's number is 20.

Dr Graham Phillips

So what was it like coming up with God's number?

Tom Rokicki

It was really a nice crossing of the finish line as it were but in a way it was almost bitter sweet
because I was really hoping there would be a position that took 21 - that was harder than anybody
knew and that didn't come through no but it's been amazing. We got an email from Erno Rubik.

John Dethridge

Rubik sent us an email. He'd been wondering himself!