# Google, boffins crack Rubik's Cube mystery

Has Google finally cracked it? Revealed today, courtesy of the massed ranks of Google computing, the answer to the ultimate question – not the old one about Life the Universe and Everything – is 20! We’re talking God’s Number here, or more prosaically the maximum number of moves required to solve the Rubik's Cube no matter what …

#### Probably Google's App Engine

http://code.google.com/appengine/

It is unlikely to be anything else.

#### Sir

"Therefore, by induction, for all n in the positive integers, n mathematicians can change a light bulb"

Does that mean they can also power it?

#### Sir,

Yes, but only for positive integer powers, since the set of positive integer powers of positive integers lies within the set of positive integers. Clear?

#### Maximum number of moves

I am sure I can solve the cube in more that 20 moves - where do I get my prize?

#### A correction

Neither Thistlethwaite nor Kloosterman claimed that the diameter of the Cayley graph of the Rubik-cube group -- the minimum number of moves required to solve any position -- is their respective number, merely that it was *at most* that. Thus, contrary to the implications of the article, they weren't wrong.

Also, "...2.2 billion groups, known as cosets..." this is really really bad. Use collections or some other synonym rather than groups, because these cosets themselves lie in a group (in the technical sense of the word).

Finally, this is a dull problem which, now that it has been finally solved, can be safely ignored for the rest of time. This differs from the P = NP problem in this respect, as well as this solution being probably true and the P = NP solution being probably false.

#### Quite so...

Well, you can brute-force this problem instance, so it's definitely known now, in the same ways as the four-colour theorem.

I remember at least two papers by Douglas Hofstaedter on Rubik's cube. They are probably only available on the Dark Internet, but if not, links would be appreciated.

#### A trickier question to answer is..

.. why should anyone care and why have people wasted their lives with this?

#### Very good, but...

...how many people can actually do a rubik's in 20 moves? I had one many years ago, and after several hundred moves it still looked the same.

#### Nope

48 moves to stick them all back on again (assuming you leave the middle ones alone)

#### titular optimisation

It can be done by me in one move...

A horizontal one, passing it over to my nerdy "friend" :)

#### Not very inspiring

Essentially they appear to have solved the problem by checking every combination to see if it takes more than 20 moves.

The brute processing power is undoubtedly impressive, but it doesn't give us any transferrable knowledge so it's not really that interesting.

#### That's not what they did

They used cleverness plus grunt, not just grunt. It's in the article.

#### Wow!

Now I dare you maths bods to find out the number of people who give a flipping monkey's about this!

#### Redacting error, maybe?

Given that I haven't been able to solve a Rubik cube after a zillion moves, I somehow doubt that 20 is the *maximum* number of moves needed to solve it. Would it rather be the *minimum* number of moves the one that has been calculated?

#### It is all about being a local...

I believe they are referring to the local maximum; when you consider only the set of minimum moves required to solve all given possible initial states of a Rubik's cube, 20 is the maximum value of that set.

If they were talking minimums, that value is 0; if the Rubik's cube's initial state is already solved, then you do not have to make any moves to get it to a solved state. Not only that, but both you and I could successfully solve it, given that particular initial state.

#### Nil comprehende, ya?

What the article says is that 20 is the largest possible minimum number of moves required from any feasible combination of the cube. That makes it, being the largest possible minimum, the maximum.

#### no it's zero.

You just shouldn't try to move the blocks.. just move the space around the blocks.

Remember, there is no cube.

#### Fantastic!

They figured out a way to figure out the maximum number of steps to figure out a puzzle.

I'd just like to say without a trace of sarcasm that I am mightilty impressed by these people.

Oh, and @Daniel B., it's the maximum of minima. The minimum is zero, or one if you exclude already solved starting states.

#### lightbulb result correction

A mathematician may have any non-negative number of imaginary friends, who may also be (imaginary) mathematicians. Thus shouldn't the answer to your lightbulb problem be "any complex integer where the real part is positive and the imaginary part non-negative"?

#### 20, huh?

Step 1: Disassemble scrambled Rubik's Cube

Step 2: Reassemble Rubik's Cube unscrambled

Do I get £1m?

#### Takes me three moves.....

.....to finish a Rubik's cube.

1) Reach arm outwards

2) Release Cube

3) Walk in opposite direction

In all my life I could never understand the attraction.

#### Ha ha ha ha ha... tool

Then why read the article? You twat! You give away your covert awe.

#### I would guess that nobody but me took

The damn thing apart; moved one sub cube to make it unsolvable and left it laying around to drive my 'too clever by half' friends nuts.

You can also do that with the two dimensional sliding puzzles; hours of entertainment.

#### others too

Doesn't work unless they're dumb people who just learnt the moves. Someone did this in the Maths coffee bar in 1982 and everyone recognised what had been done while solving the cube.

David Singmaster wrote an interesting note about the Cube and Group Theory about that time.

If you're bored of just solving it then get someone to randomly make 5 or so moves and then try and get in back in the same number of moves.

#### I have..

.. a rubik's cube and a tube of superglue that says your 20 moves is a fail. ;-)

#### rubik's cube NP?

so is rubik's cube polynomial-time after all? Everyone seems to say it's NP-complete, yet the algorithms in the books/pamphlets that were produced at the time give bounded time ways of solving it, now it looks as though the upper bound / the degree of the polynomial is 20?

Hence we may be proving that in fact P = NP rather than P != NP :-D

#### Rubik's cube is not NP

Rubik's cube is a finite problem. NP and P deals with problems that vary with some input. For example, with factorizing numbers*, how long it takes you to do depends on how big the numbers are. Rubik's cube is 3x3x3, and is fixed. You can consider n x n x n Rubik's cubes, and ask whether there is a polynomial-time (in n) algorithm to solve them. My guess is yes, but I cannot be bothered to prove this or even look it up, because nobody cares.

*although it's NP but not necessarily NP-complete (in fact, I can't remember whether it is known to not be)

#### that was the 3x3x3, but...

How many moes to solve a 4x4x4 or 5x5x5?

I need to know because these are MUCH more fiddly to put together, so the usual diassembly/reassembly strategy is 'not optimum'...

#### Re: that was the 3x3x3, but...

It's obvious:

2πn^(n - 2) + 1 for n > 1

where n, is the number of tiles on a side:

3 x 3 x 3 = 2.π.3^1 + 1 = 19.85 (20 whole moves)

and so on:

4 102

5 786

6 8144

7 105602

8 1647100

9 30052282

10 628318532

PS a 2x2 cube can be done in 7 moves.

Mine's the one with the Fortean Times in the pocket

#### Lightbulb

First!

Oops, sorry!

First you ask "How many mathematicians does it take to screw in a light bulb?"

The answer to that is 2 (or more), given a) a sufficiently large lightbulb or b) sufficiently small mathematicians, given of course that it takes two to (ahem) tango, and given non-Hermaphroditic mathematicians. NB I'm assuming that mathematicians would generally prefer a bed and not a lightbulb, but I have no proof of that.

Subsequently, you go on about changing a lightbulb. I humbly suggest that changing a light bulb is not the same as screwing in a light bulb. So whilst it may have been shown that "for all n in the positive integers, n mathematicians can change a light bulb.", that is not the answer to "How many mathematicians does it take to screw in a light bulb?"

QED!