Tip:
Highlight text to annotate it
X
Starting a few years ago a graduate student and I began researching to rubik cube multistep
solution methods, in finding averages for move balances. In the back of our minds we
were very interested in the God's algorithm problem. But, it was only this year that I
got involved with a team that was close to the solution and began working with them on
it.
There are four people on the team. John Deathridge is at Google, and Herbert Cochamonda he is
a mathematics teacher from Germany and Tom Rokiki he has a doctorate in computer science
from Stanford and he's the mastermind behind the project and he was reasonsible for the
recent improvements in the last few year, and the final push that got us to twenty,
the twenty move upperbound finally. So the upperbound is the maximum amount of moves
that you would need in any case. So for any position. So we proved that that's twenty.
The lower bound was already known to be twenty about fifteen years ago. So that would be
that there is a posistion known to require twenty.
And actually are work has discovered something in the range of one hundred million such postitions
that require twenty moves. What made this difficult was the sheer number of postitions
there are fourty three billion billion postitions to grapple with. And so we broke it into about
2.2 billion so called co-sets and each one of those contained almost twenty billion positions.
And then of the 2.2 billion co-sets we were able to further reduce that through mathematical
tricks down to just 56 million co-sets that we had to run individuallly. The machinery
that we tested each co-set could be run between twenty seconds and a minute, depending on
the hardware. That doesn't mean a human being can on the spot come up with a twenty move
solution. So its definitley a computer assisted proof, absolutley. Well, it feels different,
usually I'm just hiding out in my office and of course I teach and I do introduce the rubik
cube into my course work and students I think they like it, maybe not all of them. But,
it has been fun. The university has been very supportive of my working on this project,
even though it is off the beaten path. It was a big problem, an unsettled problem you
know for three decades in the area, computation group theory. And that's not exactly my established
area of expertise, which is number theory, but nonetheless it was a problem that I was
able to help with in the final run. We established that the God's number for the rubik cube is
equal to twenty. We have brought the upper bound to equal the lower bound of twenty.
So that's game over.