Follow Slashdot blog updates by subscribing to our blog RSS feed

 


Forgot your password?
Close
typodupeerror
×
Math Science

Algorithm Solves Rubik's Cubes of Any Size 139

Posted by timothy from the gordian-knot-sledgehammer dept.
An anonymous reader writes with this excerpt from New Scientist: "Only the most hardcore puzzle-solvers ever go beyond the standard 3x3x3 Rubik's cube, attempting much larger ones. Now an algorithm has been developed that can solve a Rubik's cube of any size. It might offer clues to humans trying to deal with these tricky beasts. Erik Demaine, a computer scientist at the Massachusetts Institute of Technology has found that the maximum number of moves that will ever be required for a cube of side n is proportional to n/log n. 'It gives me a couple of ideas how to solve this thing faster,' says Stewart Clark, a Rubik's cube enthusiast who owns an 11x11x11 cube."
This discussion has been archived. No new comments can be posted.

Algorithm Solves Rubik's Cubes of Any Size More

Algorithm Solves Rubik's Cubes of Any Size

Comments Filter:

  • From TFA... (Score:3, Informative)

    by Lightborn ( 7556 ) on Thursday June 30, 2011 @06:03PM (#36628938)

    It's n^2/log n.

    • Re:From TFA... (Score:5, Informative)

      by RussellSHarris ( 1385323 ) on Thursday June 30, 2011 @06:07PM (#36628984)

      Actually, it's n²/log n, but since Slashdot doesn't like Unicode it just eats that ² character and you end up with n/log n. Which, of course, is wrong.

      • Re:From TFA... (Score:5, Funny)

        by arth1 ( 260657 ) on Thursday June 30, 2011 @07:46PM (#36629664) Homepage Journal

        Yeah, I kind of wondered about that. It would imply that a standard 3x3 cube would always be solvable in 7 moves or less, which is clearly wrong, unless these are gentoo moves.

        • Re: (Score:1)

          by Anonymous Coward

          That wouldn't imply that anyways since we're talking asymptotics here. It doesn't say anything about how fast you can solve a specifically sized cube, only the relationship between the difficulties in solving different sized ones.

        • Well, for a sufficiently general definition of "move", each cube is solvable in a single move. :-)

        • Time Cube cannot be solved in 7 moves with stupid educators.

        • Re: (Score:1)

          by Ed Avis ( 5917 )
          He said *proportional* to n^2/log n. That doesn't tell you anything about exactly how many moves are needed for any particular size of n.

  • Yes, but... (Score:3, Interesting)

    by Anonymous Coward on Thursday June 30, 2011 @06:06PM (#36628972)

    Does it scale to >3 dimensions?

  • The headline claims they can "solve" any Rubik's cube, but who cares? You can solve it just by performing random moves.

    The import part is NOT solving it, it's that they can do it in the minimum number of moves.

    • The headline claims they can "solve" any Rubik's cube, but who cares? You can solve it just by performing random moves.

      The import part is NOT solving it, it's that they can do it in the minimum number of moves.

      Can you prove that?

      Hint: Random moves has a number of infinite move cases that never get solved.

      • A Rubik's cube has a finite number of states and a finite number of moves. So I don't understand how performing infinite moves wouldn't eventually result in the solution.

        • Re: (Score:1)

          by Nerdos ( 1960936 )
          Easier example. Say you're 10 meters away from your house. If there's exactly a 50% chance to easier take a step forward or backward, the probability that you will never reach your house is greater then 0. If the chance to take a step forward is 50% + epsilon, then that probability goes down to zero.

          • Re: (Score:2)

            by wisty ( 1335733 )

            No. That's simply not true. If there is a 99% chance of you stepping *back* and a 1% chance of you stepping *forward*, the probability of you *eventually* reaching your house approaches 100%, eventually. The average time for you to reach your house, however, is really quite long.

  • Well that's not good (Score:3)

    by Psychotria ( 953670 ) on Thursday June 30, 2011 @06:43PM (#36629246)

    I've been working on my 60x60x60 cube for 17 years now and have 5 cublets in place on one side. This news has ruined my day :-( At my current rate I am never going to finish according to TFA, especially since I am essentially just doing random moves. Damn.

    • I've been working on my 60x60x60 cube for 17 years now and have 5 cublets in place on one side. This news has ruined my day :-( At my current rate I am never going to finish according to TFA, especially since I am essentially just doing random moves. Damn.

      hahahahahahahaha aaaaahhhhhhh

  • General algorithm already known (Score:4, Informative)

    by Michael Woodhams ( 112247 ) on Thursday June 30, 2011 @07:10PM (#36629454) Journal

    Once you can solve a size 4 and size 5 cube, all larger sizes are obvious generalizations of the same algorithm. (At least, for the algorithm I use it is so.) I've seen an edited video of someone solving a (computer simulated) size 100 cube. So the fact of a "general algorithm" is not news.

    That it is an efficient algorithm and sets a new* upper bound on how many moves you need is interesting. (This upper bound is proportional to (n^2/log n), not (n/log n) as stated in the summary.)

    * I don't follow cubology that closely, so I'm taking their word for it that this is a new upper bound.

    • It's not even a generalization. It's the exact same algorithms. Once you can solve a 4x4x4 there is no extra algorithms needed at all to solve any cubes of any higher degree.

      The typical idea is to solve the cube to the point of being a 3x3x3 with all the centers and edges solved. When solving the edges if you're trying to get the edges in place any portion of the edges can be grouped to look like a cube with a smaller degree.

      Someone could argue that the 5x5x5 and 4x4x4 algorithms are needed, because of the

      • Re: (Score:3)

        by kallisti ( 20737 )

        Reducing to a size 3 cube is only one way of solving the cube. It has the drawback of a parity error where your reduced 3 cube can't be solved by using standard methods. For instance, on a size 4 cube you can get to a position where two adjacent edge pieces are swapped and inverted, as if the size 3 cube had one edge flipped, which is impossible. You can also have two corners swapped. There are some known moves to fix these errors, and most (all?) speed cubers use reduce-to-3 so it isn't a major proble

  • Patent Pending (Score:3, Funny)

    by cultiv8 ( 1660093 ) on Thursday June 30, 2011 @07:16PM (#36629478) Homepage
    This system and method for solving a Rubik's cube is a social media networking plug-in widget that synergizes, optimizes, and rightsizes the Rubik cube solving experience, utilizing HTML5/CSS3/JS code in a novel and innovative way to provide end-users with a single, solidified and parsimonious User Interface (UI), optimized for the User Experience (UX), utilizing Information Architecture (IA), over 256bit SSL security. It is built on a 100% cloud-based, distributed OS, independent architectural framework and uses the actual "internet" to facilitate communication between said end-user's "keyboard", to our proprietary "software", and back to end-user's "monitor".

  • The solution? (Score:5, Funny)

    by tool462 ( 677306 ) on Thursday June 30, 2011 @07:24PM (#36629524)

    -After the researchers solve the 3x3x3-

    Buttercup: We'll never succeed. We may as well die here.

    Westley: No, no. We have already succeeded. I mean, what are the three terrors of the General Cube Solution? One, the pieces coming off - no problem. There's a popping sound preceding each; we can avoid that. Two, the stickers peeling off, which you were clever enough to discover what that looks like, so in the future we can avoid that too.

    Buttercup: Westley, what about the R.O.U.S.'s?

    Westley: Rubik's Of Unusual Size? I don't think they exist.

    -- Immediately, Westley is attacked by a 4x4x4 cube --

  • solve (Score:1)

    by Anonymous Coward

    I once solved a 1x1x1 rubik's cube!
    (I cheated and took the stickers off ;-;)

  • Has someone notified the Borg?

  • It's time for Slashdot to support Unicode properly (Score:5, Insightful)

    by eobanb ( 823187 ) on Thursday June 30, 2011 @07:41PM (#36629638) Homepage

    Lack of support for 20 year-old standard is usually just annoying as hell, but in this case it's actually caused the summary to be wrong. For a site that frequently discusses such topics as technology, math and language (for all of which Unicode is an important part—at least insofar as even being able to TALK about these subjects) there is absolutely no excuse for not doing Unicode.

    As far as I'm concerned Slashdot ought to be able to render MathML too.

    • Re: (Score:2)

      by tlhIngan ( 30335 )

      Lack of support for 20 year-old standard is usually just annoying as hell, but in this case it's actually caused the summary to be wrong.

      It did, at one point. The problem was the trolls went and ruined it for all of us by embedding all sorts of control characters in post that ended up destroying the flow of a web page and making the text unreadable.

      Hell, I think most blogs probably aren't immune to the problem. There used to be one common indication of this because people would force 4 or 5 unicode control

    • Agreed entirely.

      Slashdot's codebase often feels like a joke to me. My own pet peeve is the discussion threshold slider - it's numbers are *never* correct. Right now on a different browser tab a discussion is saying there's "10 Full, 3 Abbreviated" - whereas it's actually displaying 7 full, and 0 abbreviated. Another is telling me "16 Full, 0 Abbreviated" - that one has the abbreviated count right, but there's only 6 comments visible. The numbers are often so wildly out that they're completely meaningles

  • required for a cube of side n

    I don't even want to think about solving a cube with n sides. Not to mention, how a cube ever got n sides to begin with...

  • Mr Rubik (Score:4, Funny)

    by pinballer ( 655113 ) on Thursday June 30, 2011 @08:33PM (#36629874)
    I could only ever manage to get 5 out of the 6 sides :(

  • What about a 3x3x3x3x3 "cube"? (Score:3)

    by Rich0 ( 548339 ) on Thursday June 30, 2011 @08:58PM (#36629972) Homepage

    It seems boring to me to just extend the size in 3 dimensions. What about extending it beyond three dimensions?

  • The article says "the maximum number of moves that will ever be required for a cube of side n is proportional to n^2/logn". It also says "standard Rubik's cube can be solved in 20 moves or less" and then it says Demaine's "first task is to work out how to turn that into an exact number for given sizes of cube." but if the number of moves for n=3 is 20 and the number of moves is proportional to n^2/logn then the number of moves for cubes of any length =kn^2/logn where k=20/(3^2/LOG(3)) = 1.1 . So maximum num

  • The Demaine father (Martin) and son (Erik) are a very impressive couple.

    I congratulate both of them.

    Let me suggest that they tackle "The current status of work on the origin of life" http://indico.cern.ch/conferenceDisplay.py?confId=137302 [indico.cern.ch]

    "Work on the Origin of Life is poised to converge onto a fourth phase and, many of us hope, success. The first phase concerned prebiotic synthesis of the small molecules, amino acids, nucleotides, lipids and others, essential for life and spanned some forty years. The seco

  • If one can solve the 3x3, 4x4 and 5,5 it's relatively simple to solve any sized cube by splitting it into overlapping subcubes and expanding the algorithms. The only real thing, is time, it takes a lot of it.
    • Not just that, if you can solve the 3X3, then every cube above it can be solved by first making it into a 3X3 cube. Granted there are probably some new algorithms required to do that, but when I first got my 4X4, I though it was going to be really hard, but converting it to a 3X3 was intuitive compared to solving the 3X3. And then I realized that any higher order cubes were just going to be an extension of this and not anything more complex.
      I used to charge people to solve their cubes for them back in grad
  • It's a fucking CUBE, why do you need to specify the size of all the dimensions? One dimension is enough for crying out loud. Do you really think you can have a 3x4x5 cube?!
  • From TFA:

    "Suppose someone takes a solved 20x20x20 Rubik's cube and makes five moves - can you figure out [from that scrambled state] what those five moves were?" he asks. In other words, can you solve it in five moves? He suspects that you cannot, but has yet to prove it. "We don't know."

    Of course you can solve this cube in five moves--use brute force. It's getting little things like this wrong that makes me dislike journalists so much. If they misinterpret such an apparently simple comment, how wrong is the stuff I can't easily verify or refute?

    • On a 20x20x20 cube, five random moves would be trivial to solve by inspection plus a tiny bit of brute force. Most kids with decent spatial skills can undo three or four moves on a regular cube without much trouble. What move or moves remained after what was easy to backtrack would only take a few attempts to discover. 20 moves might be a little bit more of a problem on a 20x20x20 cube - not enough moves to get to every possible state on a cube that size, but possibly too many moves to do by visual inspec
  • Anyone knows solving a Rubik's cube is impossible.
  • Actually I may be lying, I believe the one-sized Rubik's cube may be solved for at least dimension 2.

Slashdot Top Deals

Business is a good game -- lots of competition and minimum of rules. You keep score with money. -- Nolan Bushnell, founder of Atari

Close