Forgot your password?
typodupeerror
Image

Rubik's Cube Now Solvable in 20 Moves 309

Posted by CmdrTaco
from the good-use-of-spare-time dept.
A few years ago we reported that it had been proven that Rubik's Cubes could be solved in 23 moves. Well now that number is down to just 20. Proving it required 35 years of computer time donated by Google to get it done.
This discussion has been archived. No new comments can be posted.

Rubik's Cube Now Solvable in 20 Moves

Comments Filter:
  • Enough! (Score:5, Funny)

    by 2names (531755) on Monday August 09, 2010 @11:34AM (#33189528)
    Enough with the Rubik's cube junk, someone please tell us how to unhook a bra with *1* move.
  • by Drakkenmensch (1255800) on Monday August 09, 2010 @11:34AM (#33189542)

    Moves 1 through 19: repeatedly hit cube with hammer

    Move 20: reassemble the smashed bits into a solved cube.

    Warning: Your cube may or may not remain functional through use of this solution.

  • by calderra (1034658) on Monday August 09, 2010 @11:36AM (#33189558)
    I know it won't stem the tide, but this is good research. I'm sure there are a million other algorithms in the world that can benefit from this. Shortcuts they had to invent to make sure they were using minimal processing time, full understanding of how much money and time it really took to get this process done to make other projects more practical, etc etc. This sort of thinking, even if silly on its own, has a broad range of applications.
  • by dmomo (256005) on Monday August 09, 2010 @11:38AM (#33189586) Homepage

    The shortest path between any two configurations (be them solved or not) on a graph of all possibilities will be no greater than 20.

  • I got a team working on solving Rubik's cube in 1 move.
    The proof only need 30 years of computering to be proven, however as we only got one computer we won't release is before 2040 (and then we'll claim we were that close to the solution, but due to a timestamp bug we had to restart from scratch in 2038).

    • Actually 1 move isn't hard, because there are only 12 possible moves, thus 12^1 = 12 permutations. It does not take much processing power to find one rubik's cube that none of the 12 permutations will solve.
      • by Rhaban (987410)

        The computer time is necessary to find the move that isn't one of the 12 we usually think of, and will solve any cube.

        • 1) Turn the lights off.

          The cube now exists in an entangled solved/unsolved state.

  • by Culture20 (968837) on Monday August 09, 2010 @11:38AM (#33189598)
    How about measuring that in actual computer usage? X MHz on Y cores per Z nodes over A hours? Or at least say it would have taken one X MHz processor 35 years to compute it. Computer-hours are nothing line man-hours or horse-power. At least those have good limits to their vagueness. Computer-time might as well be arthropod-lengths (are we talking dust mites or ancient giant sea-scorpions?).
    • by pspahn (1175617)
      What about Moore's Law? Do they consider that in their equation? 35 years of computer time is only 17.5 years of computer time a couple years or so from now.
    • And considering the processor speeds from 35 years ago, I'm not sure if I would want an application such as this running that long, anyway.

    • Re: (Score:3, Informative)

      by rawler (1005089)

      Except clock-cycles, which is what you get from your equation, is also not a good measurement of "computer usage".

      However, Google Tech Talks had a rather nice explanation of the algorithm and core mechanics for solving the problem a couple of years ago. Quite interesting for anyone in supercomputing, or just plain old curiosity.

      http://www.youtube.com/watch?v=WQw7c-PliB4 [youtube.com]

  • by Romario77 (1844904) on Monday August 09, 2010 @11:41AM (#33189656)
    They give the distance and number of positions for the cube here: http://www.cube20.org/ [cube20.org] What I don't understand is why they have only approximate number 20 moves - from the article on the link above I understand that they solved all of the 20-moves combinations so they must know the exact number of those combinations
    • Re: (Score:3, Insightful)

      by thehickcoder (620326)
      I believe the article said their solution algorithm did not search for optimal solutions, only for those that are 20 moves or less. (It has already been proven that there exist positions that can not be solved in less than 20 moves)
      So, they can probably give an upper bound on the number of positions solvable in 20 moves, but not an exact number.
    • Re: (Score:3, Informative)

      by grimJester (890090)
      They quit testing moves when they found a solution in 20 moves for a given starting state. This means they don't know if a given starting state requires 20 moves. There may be an 18-move solution that they missed.
  • I wouldn't say they're cheating, but I am a bit dissatisfied with their way of counting moves. Rotating a face by 180 degrees is not an elementary move to me. I'd like to know god's number in elementary moves.
    • Re: (Score:3, Informative)

      They are just different metrics. What you're talking about is the quarter turn metric, and this proof is about the face turn metric. There is apparently a position that is known to be a distance 26 quarter turns from solved, so your answer would be at least 26.
  • 35 years (Score:2, Funny)

    by redmond (611823)
    I've also been working on solving the Rubik's cube for 35 years. It's taken me 63,412,452,120 moves and I have one side solved and a line on another side.
  • ...But why the hell is the demo avi on the web page (cube20.org) showing the process in reverse?
  • Step 1: Remove the stickers.
    Step 2: Reapply the stickers,

  • Plot the count vs. distance table on a chart and set the count to a log scale. Up to 17 it's almost perfectly linear. I wonder why that is?

    -S

  • by Entropius (188861) on Monday August 09, 2010 @12:22PM (#33190376)

    35 years is about 300k core-hours, a standard measure of computing resources. This is a big pile of computer time, but is not unreasonable.

    So how much does this cost?

    A typical supercomputer, Ranger [utexas.edu], cost $59 million to build and operate for four years. It's got about 60k cores, so $59 million delivers 240k core-years; they used 35 core-years to do this computation. Doing the division, you get $9000 of computer time -- not all that bad. Plugging in the cost numbers for another production supercomputer, Kraken [sciencedaily.com], gives a slightly lower cost.

  • by johny42 (1087173) on Monday August 09, 2010 @04:53PM (#33195450)

    Actually, this is a much more important result than the summary claims. Until now, there was always a gap between the proved lower bound and upper bound on necessary moves. They now proved that the known lower bound (20, proved in 1995) is also an upper bound (ie. there is no position which requires 21 or more moves to solve) and thus concluded research that lasted for 30 years.

    This article could very well be listed on the Slashdot main page, it has nothing to do in Idle. The algorithms that were designed during this research are nothing to laugh at and will surely advance other research fields as well.

1 + 1 = 3, for large values of 1.

Working...