back to article 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 …

COMMENTS

This topic is closed for new posts.
  1. awjr
    Go

    Probably Google's App Engine

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

    It is unlikely to be anything else.

  2. Sir Runcible Spoon

    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?

    1. Loyal Commenter Silver badge
      Boffin

      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?

      1. Loyal Commenter Silver badge

        Erratum

        I should have said, 'only PROVEN for'

  3. Liam Johnson
    Joke

    Maximum number of moves

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

    1. LinkOfHyrule
      Joke

      Claim you prize from

      Claim your prize from the university of East Anglia hahahaha!

  4. DavCrav
    Boffin

    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.

    1. Destroy All Monsters Silver badge
      Thumb Up

      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.

  5. Anonymous Coward
    Anonymous Coward

    A trickier question to answer is..

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

  6. heyrick Silver badge

    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.

  7. Disco-Legend-Zeke

    Can Be Done In...

    ...5 or 10. But step one is: disassemble cube.

    1. Loyal Commenter Silver badge
      Coat

      Nah,

      Step 1: Remove coloured stickers

      1. CADmonkey
        Paris Hilton

        Nope

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

        1. lpopman
          Coat

          titular optimisation

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

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

  8. Anonymous Cowherd 3

    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.

    1. Geoff Mackenzie

      That's not what they did

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

  9. Anonymous Coward
    Happy

    Wow!

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

  10. Daniel B.
    Boffin

    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?

    1. MeRp

      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.

    2. Rex Alfie Lee
      FAIL

      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.

  11. Geoff Mackenzie
    Boffin

    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.

  12. Majid
    Joke

    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.

  13. Michael Wojcik Silver badge

    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"?

  14. Anonymous Coward
    Anonymous Coward

    20, huh?

    Step 1: Disassemble scrambled Rubik's Cube

    Step 2: Reassemble Rubik's Cube unscrambled

    Do I get £1m?

  15. Raspy32

    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.

    1. Rex Alfie Lee
      FAIL

      Ha ha ha ha ha... tool

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

  16. John F***ing Stepp

    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.

    1. Kamal Hashmi

      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.

  17. William Boyle

    N-1

    And, if you let your wife change the bulb, the number has to be N-1... :-)

  18. alien anthropologist
    FAIL

    I have..

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

  19. MarkieMark1
    Boffin

    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

    1. DavCrav

      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)

  20. Telecide
    Megaphone

    The solution in 2 easy steps

    1. Move out of your parents house.

    2. Get a girlfriend

  21. Trygve Henriksen

    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'...

    1. ravenviz Silver badge
      Coat

      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

  22. MarkieMark1
    Paris Hilton

    @Telecide

    2. I'm not sure my wife would approve :-)

  23. Anonymous Coward
    Pint

    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!

This topic is closed for new posts.

Other stories you might like