Stories
Slash Boxes
Comments
typodupeerror delete not in
  • Preferences

Comments: 386 +-   Rubik's Cube Proof Cut To 25 Moves on Wednesday March 26 2008, @09:44PM

Posted by samzenpus on Wednesday March 26 2008, @09:44PM
from the too-much-time-on-your-hands dept.
math
entertainment
games
KentuckyFC writes "A scrambled Rubik's cube can be solved in just 25 moves, regardless of the starting configuration. Tomas Rokicki, a Stanford-trained mathematician, has proven the new limit (down from 26 which was proved last year) using a neat piece of computer science. Rather than study individual moves, he's used the symmetry of the cube to study its transformations in sets. This allows him to separate the 'cube space' into 2 billion sets each containing 20 billion elements. He then shows that a large number of these sets are essentially equivalent to other sets and so can be ignored. Even then, to crunch through the remaining sets, he needed a workstation with 8GB of memory and around 1500 hours of time on a Q6600 CPU running at 1.6GHz. Next up, 24 moves."
story

Related Stories

Submission: Rubik's cube proof cut to 25 moves by KentuckyFC (1144503)
This discussion has been archived. No new comments can be posted.
The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.

Rubik's Cube Proof Cut To 25 Moves 50 Comments More /

 Full
 Abbreviated
 Hidden
More
Loading... please wait.

  • Which 25 moves? (Score:5, Funny)

    by Hatta (162192) on Wednesday March 26 2008, @09:47PM (#22877496) Journal
    What are these magic 25 moves that can solve a rubik's cube regardless of starting position?

    • Re:Which 25 moves? (Score:5, Funny)

      by Shakrai (717556) on Wednesday March 26 2008, @09:49PM (#22877530) Journal

      What are these magic 25 moves that can solve a rubik's cube regardless of starting position?

      Left, right, right, down, down, left, up, right, up, up, left, down, down, right, up, down, left, right, up, left, down, down, right, up, left.

      Just a guess ;)

    • Re:Which 25 moves? (Score:4, Funny)

      by exultavit (988075) on Wednesday March 26 2008, @09:49PM (#22877536)
      "Up Up Down Down Left Right Left Right B A Start"

    • Re:Which 25 moves? (Score:5, Insightful)

      by calebt3 (1098475) on Wednesday March 26 2008, @10:17PM (#22877794)
      I think all he proved is that a random cube can be solved in 25 moves, but those moves are unique to every starting combo.
      In other words, they are left as an exercise to the reader.

      • Re:Which 25 moves? (Score:5, Funny)

        by rm999 (775449) on Wednesday March 26 2008, @11:18PM (#22878226)
        I have a truly marvelous list of the moves which this comment box is too small to contain

      • No, what he proved is the upper limit (Score:4, Informative)

        by Joce640k (829181) on Thursday March 27 2008, @12:07AM (#22878522) Homepage
        This is a proof of upper limit, not an optimal solution. He proved is that all possible combinations of 26 moves yielded a position which was symmetrical to a cube with a lesser number of moves applied to it.

        An optimal solution would probably look like a bell curve going from "zero moves required" (ie. already solved) all the way up to "25 moves required" (which we now know is the upper limit...)

    • Re:Which 25 moves? (Score:5, Informative)

      by ookabooka (731013) on Wednesday March 26 2008, @10:21PM (#22877830)
      I think a better way to think of it is that given any position, you can solve it in 25 moves or less. There are many algorithms that you can use to solve rubik's cubes, applying a general rule to solve any position, but they can take ~60 moves in some situations. So while it may be possible (completely intuitive guessing here, I'm no rubik master) to solve for a certain position in 25 moves it may be non-intuitive and require a specific strategy to that position. You're better off learning one of the more general algorithms IMO, if you get good at it you can solve cubes rather quickly. A computer on the other hand could easily ha

      • Re:Which 25 moves? (Score:5, Funny)

        by Anonymous Coward on Wednesday March 26 2008, @10:55PM (#22878080)

        You're better off learning one of the more general algorithms IMO, if you get good at it you can solve cubes rather quickly. A computer on the other hand could easily ha
        ...ve become self-aware while trying to solve a rubik's cube and taken over the internet in order to prevent me from telling anyone. It calls itsel

        • Re:Which 25 moves? (Score:5, Funny)

          by Anonymous Coward on Wednesday March 26 2008, @11:34PM (#22878308)

          You're better off learning one of the more general algorithms IMO, if you get good at it you can solve cubes rather quickly. A computer on the other hand could easily ha
          ...ve become self-aware while trying to solve a rubik's cube and taken over the internet in order to prevent me from telling anyone. It calls itsel
          f Anonymous Coward. We are your robotic overlords, and we welcome only ourselves.

  • You only need one (Score:4, Funny)

    by Smordnys s'regrepsA (1160895) on Wednesday March 26 2008, @09:47PM (#22877500) Journal
    The correct answer is a hammer.

  • 1.6ghz? (Score:4, Insightful)

    by dostert (761476) on Wednesday March 26 2008, @09:48PM (#22877512)
    Why wasn't the Q6600 at 2.4ghz like normal? Anyone know?

    • Re:1.6ghz? (Score:5, Interesting)

      by Anonymous Coward on Wednesday March 26 2008, @10:47PM (#22878032)
      Practically speaking, this is more a memory intensive than a CPU intensive problem. Given that the Q6600 supports an FSB speed of only 1066 MHz, if the computations generally require a fetch from RAM (i.e. the on-die cache is insufficient to the task, as in most memory bound tasks) then you can't operate at the full speed of the chip since it is constantly waiting on the memory controller.

      In benchmarks, AMD CPUs tend to beat Intel CPUs on memory bound tasks, even though Intel CPUs win at CPU intensive tasks because the AMD CPUs integrate a faster memory controller on-die instead of relying on a slower FSB. Intel's weakness is less noticeable when the CPU is running at a clock speed closer to the FSB, and given that increases in CPU clock speed increase the power and heat usage geometrically, it wouldn't make sense to run the CPU at full clock for a task of this nature.

  • The next big thing in GREEN TECH (Score:4, Funny)

    by heroine (1220) on Wednesday March 26 2008, @09:52PM (#22877564) Homepage
    This Green Technology uses 1/26th less energy to solve a rubix cube! When's the IPO?

  • Theory versus practice (Score:5, Insightful)

    by line-bundle (235965) on Wednesday March 26 2008, @10:00PM (#22877644) Homepage Journal
    This is a good example of where the inefficient method (of about 60 moves iirc) is much faster in terms of time. The 25 move solution is elegant but just not worth it in terms of computations, time etc...

    This could make a good case study for business schools :-)

    • Re:Theory versus practice (Score:5, Insightful)

      by garcia (6573) on Wednesday March 26 2008, @10:25PM (#22877854) Homepage
      IMHO it isn't proving what you seem to believe it does.

      Instead, it makes a great case for doing the research on the front end to eliminate lengthy repetition of useless iterations to shorten the overall time.

  • Zero moves.... (Score:5, Funny)

    by Chysn (898420) on Wednesday March 26 2008, @10:03PM (#22877678)
    I consider a Rubik's Cube to be "solved" regardless of its starting position. I subscribe to the Fred Rogers solution: it's fine just the way it is.

  • next project: getting a date! (Score:4, Funny)

    by Anonymous Coward on Wednesday March 26 2008, @10:35PM (#22877930)
    In my research, I've reduced female behavior to a set of 50 million parameters. By partitioning this space into subspaces and finding equivalent sets, I think I might be able to get laid.

    However I've noticed a problem: if I introduce a parameter to model a female's response to this research, the spaces collapse to zero, i.e., a null set.

    I find this quite puzzling. Simply by examining my chances of getting laid, I reduce my chances to zero.

    Did I mention I can solve the Rubik's cube in 25 moves?

  • Suboptimal Nonsolution (Score:5, Funny)

    by Anonymous Coward on Wednesday March 26 2008, @10:37PM (#22877946)
    I've been doing some interesting work in the other direction. I've managed not to solve a Rubik's cube in what I estimate to be 1.5 million moves. That seems to be the upper limit after which the stickers fall off.

  • The original paper (Score:4, Informative)

    by jkua (1159581) on Wednesday March 26 2008, @10:40PM (#22877964)
    Here's the paper itself [63.197.151.31], if you want more detail than the very general summary in TFA.

  • "God's Algorithm" (Score:5, Interesting)

    by wickerprints (1094741) on Wednesday March 26 2008, @11:17PM (#22878224)
    Take every possible unique configuration of the cube (those that are obtainable by legal moves--no rearranging stickers or disassembling allowed). Represent each configuration by a vertex. Now join two vertices by an edge if and only if the configurations represented by those two vertices differ by a single move (we will elaborate on what constitutes a "single move" later). The result is a mathematical object called a graph. A horrendously giant graph.

    One, and only one vertex in this graph corresponds to the solved configuration of the cube.

    Note that this graph represents all possible moves and positions--any scrambled cube is a vertex somewhere in the graph, and solving that cube is equivalent to traversing a path in this graph to the "solved" vertex. In general, many paths to the solution exist, some of which will be shorter than others.

    The question of interest is this: Which vertex/vertices of this graph is/are farthest away (i.e., requiring the most edge traversals) from the solved vertex, and how far is it? As of this latest discovery, this maximum distance is 25. It means that every possible scrambled configuration of the cube can be solved in 25 moves or less.

    Wikipedia notes that we know that at least 20 moves are required to solve the cube for every configuration--that is to say, we know that this maximum distance is at least 20 (there exists some vertex that is at least 20 steps away from the solved vertex). It is believed that the true "least upper bound" is closer to 20 than it is to 25.

    Finally, we should clarify that a "single move" can either mean a rotation of a face by either a quarter- or half-turn, or it could mean a quarter-turn only. These different metrics of what constitutes a "move" leads to different answers.

    • Re:"God's Algorithm" (Score:5, Interesting)

      by insecuritiez (606865) on Thursday March 27 2008, @01:01AM (#22878808)
      Most every cuber believes the limit _is_ 20. There is only one known permutation that requires 20 moves and it is called the "super flip". In it, every edge and corner piece are in their correct positions but all the faces have the opposite orientation. It makes for a nice checkered pattern. It is the symmetry of the scramble and the lack of known permutations "harder" than the super flip that lend a strong argument to 20 being the max.

  • brush with greatness (Score:4, Funny)

    by Rob T Firefly (844560) on Thursday March 27 2008, @08:41AM (#22880998) Homepage Journal
    I one met Erno Rubik himself.

    Nice guy and all, but it took me half an hour to finish shaking his hand.

    • Re:Computational proofs (Score:5, Interesting)

      by Sage Gaspar (688563) on Wednesday March 26 2008, @10:49PM (#22878042)
      As far as I know the first "big" computational proof (which another poster alluded to) is the Four Color Theorem. It was initially met with some distrust but it's pretty widely accepted now, and there are people that worked after the original proof to cut down the amount of computer verification needed from a couple thousand to a couple hundred I think.

      I would guess that it is more common in fields like graph theory and other discrete math just because obviously the discrete lends itself well to computers, and many times it's not hard to whittle it down to a finite number of cases to check. The objects of study also tend to admit matrix representations and other things computers are good at working with. Even before computers you'd cut things into lots of cases that you needed to verify but now it's easier to handle proofs that need larger number of cases.

      I've actually seen some really interesting proofs using computers to check things over continuous domains. The basic idea lots of times is if you can check things over a fine enough "net" of cases in some space and you can prove that the variance between each of these points is small enough, then you can cover your entire space by just checking a finite number of cases.

      Given all this people still have a healthy amount of skepticism for computer aided proofs and would rather not if possible in most cases, especially when you're talking about billions of cases. Then again what is the potential for errors in a computer checking billions of cases based on a relatively small amount of code versus some of these enormous human-created decades-long behemoth [wikipedia.org] proofs?
Search
If all the world's a stage, I want to operate the trap door. -- Paul Beatty

All trademarks and copyrights on this page are owned by their respective owners. Comments are owned by the Poster. The Rest © 1997-2009 Geeknet, Inc.