Slashdot Mirror

← Back to Stories (view on slashdot.org)

Algorithm Solves Rubik's Cubes of Any Size

Posted by timothy on 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."

99 of 139 comments (clear)

  1. From TFA... by Lightborn · · Score: 3, Informative

    It's n^2/log n.

    --
    My .sigs are not what they used to be.
    1. Re:From TFA... by RussellSHarris · · Score: 5, Informative

      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.

    2. Re:From TFA... by arth1 · · Score: 4, Funny

      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.

    3. Re:From TFA... by Anonymous Coward · · Score: 1

      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.

    4. Re:From TFA... by SuperMonkeyCube · · Score: 1

      4/log(2) is 13.28, more than 11. 9/log(3) is 18.86, less than 20. This curve doesn't fit so great. Anybody do the math for the 4x4x4 already?

    5. Re:From TFA... by artor3 · · Score: 1

      That's not how big O notation works. If something is O(n) it doesn't mean that it can be solved in n calculations. It means it can be solved in C*n+D calculations, where C and D are constants.

    6. Re:From TFA... by FrootLoops · · Score: 1

      Sort of. The D is unnecessary, and to be clear C*n is an upper bound on the number of calculations needed. That bound also only has to hold for n larger than some threshold value n0, though this is an unimportant constraint in CS since you can just increase C to cover all positive integer n. The constant C can sometimes be found explicitly in cases like this, though it's often a horrific mess. From the God's Number calculation, one can conclude a lower bound on C, though, to prevent the false contradiction that started this thread :) (if you have it work for all positive integers).

    7. Re:From TFA... by maxwell+demon · · Score: 1

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

      --
      The Tao of math: The numbers you can count are not the real numbers.
    8. Re:From TFA... by Kamiza+Ikioi · · Score: 2

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

      --
      I8-D
    9. Re:From TFA... by Ed+Avis · · Score: 1

      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.

      --
      -- Ed Avis ed@membled.com
    10. Re:From TFA... by FredFredrickson · · Score: 1

      The 12 hour or 1/2 Day clock is an intended EVIL against humanity. The Cubed earth has 4 days in one time rotation, dunce.

      --
      Belief? Hope? Preference?The Existential Vortex
  2. Re:Pull off the stickers! by atari2600a · · Score: 1

    Fuck you. Every fucking time I have my cube on the streets HURR DURR STICKERS

  3. Yes, but... by Anonymous Coward · · Score: 3, Interesting

    Does it scale to >3 dimensions?

  4. Re:3x3x3 cube... 11x11x11 cube... by atari2600a · · Score: 1

    Kinda... http://en.wikipedia.org/wiki/Combination_puzzles#Irregular_cuboids

  5. Re:3x3x3 cube... 11x11x11 cube... by QuasiSteve · · Score: 1

    Only if you assume each cell is of the same dimension. You could very well have a cube that is 3x4x5 cells. Although it wouldn't work as a Rubik's Cube.

    Back on topic.. I'm pretty sure I saw a 50x50x50 or something solved by software on YouTube.. is this algorithm bringing something new to the table, or...?

  6. Re:Pull off the stickers! by Dayze!Confused · · Score: 1

    I can solve a Rubik's cube in less than 30 seconds. How long does it take to pull off the stickers and put them back on?

    --
    "All tyranny needs to gain a foothold is for people of good conscience to remain silent." [Thomas Jefferson]
  7. Re:Pull off the stickers! by El_Oscuro · · Score: 1

    Unfortunately, the stickers won't stick after awhile. I used to take it apart and put it back together again.

    --
    "Be grateful for what you have. You may never know when you may lose it."
  8. Re:Pull off the stickers! by Radtastic · · Score: 1

    If you can remove the 54 stickers on a 3X3 cube and re-attach them in 30 seconds, I may be more impressed than I am with this guy's algorithm.

    --
    You stereotypers are all the same...
  9. This can lead to impossible cubes by istartedi · · Score: 1

    Back in the 80s when the cube was new and popular, I was really into it. IIRC, I got my times down under 3 minutes. Yeah, I know. Pretty pathetic by today's standards.

    Anyway, somebody gave me a cube to solve once. After about 15 or 20 minutes it dawned on me that I had an impossible cube. Somebody who thinks they're moving closer to the solution by swapping stickers can do something like put the white sticker on a corner cubie with the blue sticker, not realizing that white and blue are always on opposite sides.

    --
    For all intensive purposes, "whom" is no longer a word. That begs the question, "who cares"?
    1. Re:This can lead to impossible cubes by starofale · · Score: 1

      Anyway, somebody gave me a cube to solve once. After about 15 or 20 minutes it dawned on me that I had an impossible cube. Somebody who thinks they're moving closer to the solution by swapping stickers can do something like put the white sticker on a corner cubie with the blue sticker, not realizing that white and blue are always on opposite sides.

      White is opposite yellow. Blue is opposite green. Are you sure you hadn't just forgotten how to solve a Rubik's Cubes?

    2. Re:This can lead to impossible cubes by istartedi · · Score: 1

      White is opposite yellow. Blue is opposite green. Are you sure you hadn't just forgotten how to solve a Rubik's Cubes?

      In jr. high, I knew what I was doing. Now? I forgot which color was opposite which and didn't bother to google-check it.

      --
      For all intensive purposes, "whom" is no longer a word. That begs the question, "who cares"?
    3. Re:This can lead to impossible cubes by Trunklebob · · Score: 2

      White is opposite yellow. Blue is opposite green. Are you sure you hadn't just forgotten how to solve a Rubik's Cubes?

      White/yellow is the Western color scheme; White/Blue was more common in Japan, but I've had one or two of them here in the States, too.

      http://www.speedsolving.com/wiki/index.php/Japanese_Color_Scheme

    4. Re:This can lead to impossible cubes by istartedi · · Score: 1

      Ah, so it's possible that my memory is not so flawed. I could have sworn blue was opposite white. Come to think of it, I do seem to recall that the colors were not rigidly standardized, and having seen what I thought were knock-offs. Maybe some of the Japanese cubes got sent to the US to meet demand, or I had an early cube made before the "Western" color scheme was adopted.

      --
      For all intensive purposes, "whom" is no longer a word. That begs the question, "who cares"?
    5. Re:This can lead to impossible cubes by jamesh · · Score: 1

      You can make a cube unsolvable just by rotating a single piece (eg not by completely disassembling it, just twisting one of the corners around). No amount of moving the cube around by the correct means can rotate only a single corner piece or flip a single edge piece - they have to be done in pairs or multiples of two.

    6. Re:This can lead to impossible cubes by Joce640k · · Score: 1

      I've seen both schemes...

      --
      No sig today...
    7. Re:This can lead to impossible cubes by Joce640k · · Score: 1

      Built-in parity checking!

      --
      No sig today...
  10. Well that's not good by Psychotria · · Score: 2

    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.

    1. Re:Well that's not good by Psychotria · · Score: 1

      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.

      What's funny about this is that when I was in college, my roommate was obsessed with Rubik's cubes. He wrote a program to simulate an arbitrarily sized cube, and would then sit there and solve it. The largest I remember him doing was 42x42x42.

      Your roommate is amazing. Anyway, after some deep contemplation I've gotten over the devastation I experienced when reading TFA. I shall now focus my efforts on my continuing efforts (12 years so far) to solve my 100 disk Towers of Hanoi puzzle that I've set up next to my bed in the basement. At least that should be solvable within a convenient amount of time, unlike the silly 60x60x60 Rubik's cube (what could I have been thinking?!) The cube is a bit cumbersome to use anyway as I constructed it out of wood and it weighs too much (8kg). Moving the disks for TOH is much easier and less likely to cause me to have a hernia or develop RSI.

    2. Re:Well that's not good by FrootLoops · · Score: 2

      If you started the Towers of Hanoi puzzle in the usual state, the minimum solution uses 2^100 - 1 moves. One move per second would take about 4*10^22 years, or about 3*10^12 times the age of the universe.

    3. Re:Well that's not good by Joce640k · · Score: 1

      He's fooling you. The number of twists needed to solve that would take years - longer if you're pointing and clicking with a mouse.

      --
      No sig today...
    4. Re:Well that's not good by ccabanne · · Score: 1

      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

    5. Re:Well that's not good by BeardedChimp · · Score: 3, Funny

      The man was devastated by the article and as soon as he overcomes his devastation you tell him his other 12 year life long pursuit is fruitless. He is not going to be having a good day.

  11. Re:Pull off the stickers! by Abstrackt · · Score: 1

    I used to do that too. Unfortunately the whole thing gets too loose if you pull it apart too many times.

    --
    They say a little knowledge is a dangerous thing, but it's not one half so bad as a lot of ignorance. - Terry Pratchett
  12. Re:Pull off the stickers! by Korin43 · · Score: 2

    According to this, at least 2700 people can solve a rubik's cube in 30 seconds. The fact that one of them is on Slashdot wouldn't be particularly surprising.

  13. Re:Solving != best solution by barrtender · · Score: 2

    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.

  14. Re:3x3x3 cube... 11x11x11 cube... by praxis · · Score: 1

    Why can a cube not be composed of 3x4x5 cells so long a the cells are sized such that the cube is well, a cube?

  15. Re:Pull off the stickers! by Galaga88 · · Score: 2

    What would be particularly surprising, would be if only one of them was on Slashdot.

  16. Re:Pull off the stickers! by lul_wat · · Score: 1

    I used to go out and buy a new rubix cube. Unfortunately you run out of money if you do it too many times.

    --
    Divide a cake by zero. Is it still a cake?
  17. General algorithm already known by Michael+Woodhams · · Score: 3, Informative

    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.

    --
    Quattuor res in hoc mundo sanctae sunt: libri, liberi, libertas et liberalitas.
    1. Re:General algorithm already known by Mogusha · · Score: 2

      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 extra center edge pieces, but with proper edge pairing that's usually a moot issue. But, I could always be wrong, the 4x4x4 and 5x5x5 algorithms might be needed for any cube larger than a 3x3x3. The real point is that anything above a certain point is the exact same algorithms.

    2. Re:General algorithm already known by kallisti · · Score: 2

      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 problem. But there are at least two new algorithm required to solve bigger cubes than 3 using this method.

      Now, if you don't use reduce-to-3, then you can solve any size cube with just 3 algorithms: one to cycle 3 edges with flipping, one to cycle 3 corners and one to swap center pieces, which are actually very easy because there are always 4 of them that look identical. The really trippy part is that this method was expanded to work on 4 and 5 dimensional cubes, too.

    3. Re:General algorithm already known by ewanm89 · · Score: 1

      There are parity solve algorithms that can be reduced to.

  18. Patent Pending by cultiv8 · · Score: 2, Funny

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

    --
    sysadmins and parents of newborns get the same amount of sleep.
  19. Re:3x3x3 cube... 11x11x11 cube... by Obfuscant · · Score: 1

    Why can a cube not be composed of 3x4x5 cells so long a the cells are sized such that the cube is well, a cube?

    Because when you try to rotate the five-cell face, e.g., you'll be trying to move some of the cubelets from the four-cell face to the 3-cell face and vice versa. You'll have four cells trying to match up to 3 cells and vice versa. That may work, but if you then try to rotate the four-cell face, you'll be trying to move fractional cubelets.

    Personally, I'll be impressed when the algorithm handles 50x50x50x50 Rubick's Hypercubes (patent pending).

  20. The solution? by tool462 · · Score: 4, Funny

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

  21. solve by Anonymous Coward · · Score: 1

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

  22. The cube problem solved? by byteherder · · Score: 1

    Has someone notified the Borg?

  23. It's time for Slashdot to support Unicode properly by eobanb · · Score: 4, Insightful

    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.

    --

    Take off every sig. For great justice.

  24. side n by Memroid · · Score: 1

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

  25. Mr Rubik by pinballer · · Score: 4, Funny

    I could only ever manage to get 5 out of the 6 sides :(

    1. Re:Mr Rubik by rubycodez · · Score: 1

      I'll bet you're a hit at parties, like an opened canister of Zyklon B lobbed into the room

    2. Re:Mr Rubik by SuperMonkeyCube · · Score: 1

      I know that I am typically no fun, I attribute that mostly to refusing to drink alcohol except on rare special occasions. The few times I am in social situations it is usually because I am obligated to be there. However, since Rubik's cube is one of my primary interests, I have one with me most of the time. In talking to other people about Rubik's cube (which is much easier for me than making small talk about myself) I have heard people make statements similar to the one above made by 'pinballer', and with complete seriousness. Since the serious comments by laypeople only illustrate how poorly most people perceive a very small, rigorous mathematical group, I am way past this being a funny statement, even in jest. (I was also confused by the placement of the frowny-face emoticon.)

    3. Re:Mr Rubik by FrootLoops · · Score: 1

      You definitely don't have to drink to be fun to be around. As far as I can tell, everything else you said or implied was perfectly rigorous and used flawlessly written English, both of which I appreciate. I'm curious about your confusion over the emoticon's placement. Isn't it clear that it's just adding the emotion of confusion to the post explicitly, and that putting it at the end is only done for the sake of convenience?

    4. Re:Mr Rubik by SuperMonkeyCube · · Score: 1

      You're right - I should clarify - my confusion had to do with the emoticon's existence, i.e. why was it placed there at all. Since sarcasm is an expected mode of conversation on slashdot, the addition of the frowny face made me wondered if we were supposed to take faux pity on the speaker, and the humor was contained there somehow - I couldn't find the humor there - or it was some new level of meta-sarcasm that I didn't get (but I am now suspecting to be the case). I realize most of the failure of language processing here is mine.

    5. Re:Mr Rubik by rubycodez · · Score: 1

      I have been to quite a few parties with no intoxicating substances present over the years, some were even geared for certain hobbies and interests as high energy physics, various open source OS and wares, sports such as canoeing, a certain musical genre and many others. "To party" doesn't necessary mean to get inebriated with frat boys possessing IQs below the range considered "dull normal".

    6. Re:Mr Rubik by SuperMonkeyCube · · Score: 1

      Normally I have something to contribute on Cube-related things, but I clearly failed. Since I clearly failed on sarcasm and humor before, is it any wonder that I took the primary definition of party as the assumed term? I _know_ I'm an idiot. (My wife had me listed as 'Dumbass' on her phone.) I'll make you a deal. If you would like to kick me from slashdot, go ahead. Otherwise I will stay off for a month.

    7. Re:Mr Rubik by rubycodez · · Score: 1

      By all means stay on Slashdot, it's a virtual party

    8. Re:Mr Rubik by FrootLoops · · Score: 1

      Oh, ok. Come to think of it, I'd say the frowny face's existence was used as a flag to say "I'm not stupid; this is a joke; I know this state is impossible to reach on a solvable cube", since without it the original post might just have been an honest mistake. The frowny face also has another meaning: (feigned) confusion used to support the joking atmosphere of the comment. Humor is often a social thing--if people around you find something funny, you'll find it funny--which is self-reinforcing. You can replace "funny" with many emotions. That helps explain why crowds need to be "warmed up" at concerts. But back to the comment, if the poster found it funny, that could help the reader find it funny. At least, I imagine that's the (probably partly unconscious) reasoning behind the emoticon's placement.

  26. Re:Solving != best solution by mark-t · · Score: 1

    Only if the sequence is infinitely long.

    --
    File under 'M' for 'Manic ranting'
  27. Re:Solving != best solution by mark-t · · Score: 1

    Now, it makes sense that any Rubik's cube can be solved

    You should probably qualify that a little... for example, any normal rubik's cube, or any rubik's cube that hasn't been tampered with, or something similar... it is actually very easy to make any rubik's cube completely and permanently unsolvable.

    --
    File under 'M' for 'Manic ranting'
  28. Re:Solving != best solution by RussellSHarris · · Score: 1

    it is actually very easy to make any rubik's cube completely and permanently unsolvable

    Only if "make" involves operations that "solve" does not. For instance, a freight train can very easily "make" a Rubik's cube completely and permanently unsolveable.

  29. Re:Solving != best solution by mark-t · · Score: 1

    So can gluing it with crazy glue in an unsolved position... as can taking it apart and switching the orientation of exactly piece. There are many ways to make a rubik's cube that looks perfectly fine impossible to solve.

    --
    File under 'M' for 'Manic ranting'
  30. What about a 3x3x3x3x3 "cube"? by Rich0 · · Score: 2

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

    1. Re:What about a 3x3x3x3x3 "cube"? by jamesh · · Score: 1

      I think you could do this by having an array of cubes somehow interlinked... or http://www.superliminal.com/cube/cube.htm

    2. Re:What about a 3x3x3x3x3 "cube"? by Garble+Snarky · · Score: 1

      Why stop there? Why not extend it to other platonic solid puzzles? Archimedean solid puzzles? Don't forget the square one.

    3. Re:What about a 3x3x3x3x3 "cube"? by istartedi · · Score: 1

      Integral dimensions. Booooring. Solve me a fractal cube.

      --
      For all intensive purposes, "whom" is no longer a word. That begs the question, "who cares"?
    4. Re:What about a 3x3x3x3x3 "cube"? by BrokenBeta · · Score: 1

      Actually I really want to see a 3x3 version. i would also be interested in owning just a 3 if anyone has one.

  31. Re:Solving != best solution by RussellSHarris · · Score: 1

    My point was more that any cube in any position that can be reached by standard moves is solveable by those same standard moves. Obviously, rearranging stickers, disassembling the cube, or introducing outside forces (crazy glue, freight trains) can make the cube "unsolveable" by any possible combination of standard moves.

    But that all begs the question: is a Rubik's cube still a Rubik's cube if it's been disassembled, modified, and/or re-assembled in a condition that would be impossible for a Rubik's cube to ever reach? Is a Rubik's cube just a toy with a set of specially interlocking cubes, or is it also a mathematical and geometrical set of rules? I'd say the latter. If you violate those rules, you don't have a Rubik's cube; you have something that superficially resembles a Rubik's cube, but isn't one. Therefore there's no reason to make special exclusion for tampered cubes when you make general statements such as:

    Now, it makes sense that any Rubik's cube can be solved

    -because it goes without saying.

  32. Re:Pull off the stickers! by jamesh · · Score: 1

    I can do it in under a 90 seconds sometimes (and under 60 seconds consistently when I was a kid), and i'm nowhere near the fastest person I know at solving them. 30 seconds isn't unreasonable for someone who is actually good at it.

  33. Re:Solving != best solution by MrEricSir · · Score: 1

    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.

    --
    There's no -1 for "I don't get it."
  34. Is that base ten or base e? by colinrichardday · · Score: 1

    In the latter case, log 3=1.09, and 11.9/1.09=10.9. . . Although the article says the upper bound is proportional to n^2/log n.

    1. Re:Is that base ten or base e? by Rockoon · · Score: 1

      'log' is always base-2 when talking about computational complexity. 'ln' is reserved for the natural logarithms and is almost never appropriate.

      ..and that only matters when you are trying to get specific values out of the complexity, which is also almost never appropriate.

      --
      "His name was James Damore."
    2. Re:Is that base ten or base e? by maxwell+demon · · Score: 1

      When talking about computational complexity, fixing a base of the logarithm makes no sense at all. Changing base just means a constant factor, and constant factors are ignored for complexity considerations.

      --
      The Tao of math: The numbers you can count are not the real numbers.
    3. Re:Is that base ten or base e? by Rockoon · · Score: 1

      Just because you discard constants in Big-O notation, that does not mean that they are irrelevant in computational complexity. Base matters, and constants matter.

      --
      "His name was James Damore."
    4. Re:Is that base ten or base e? by colinrichardday · · Score: 1

      Not according to Wikipedia http://en.wikipedia.org/wiki/Logarithm_of_the_base_2.

      In any case, log_2 3 = 1.584. . . and 11.9/1.584 is about 7.5.

  35. Re:The algorithm by Garble+Snarky · · Score: 1

    Does anyone actually think this is funny?

  36. Demaine's first task is completed? by KenT9 · · Score: 1

    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 number of moves = 1.1 n^2/logn (approximately) and Demaine's first task is completed unless he needs exact numbers for each n.

  37. Re:It's time for Slashdot to support Unicode prope by tlhIngan · · Score: 1

    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 characters together followed with a normal character (some strange millions-comma thing).

    And it's a pain in the butt, too - you can't search for it, certain operations destroy the characters, so you get very strange behavior.

  38. Re:Solving != best solution by Nerdos · · Score: 1

    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.

  39. Re:Pull off the stickers! by Joce640k · · Score: 1

    He's trying to be 'funny' by saying he does it by pulling the stickers off.

    (I bet it takes longer than 30 seconds though...)

    --
    No sig today...
  40. Re:Pull off the stickers! by Joce640k · · Score: 1

    I used to do it in 30 seconds back in the '80s but last time I tried on it took more like a minute.

    There's quite a few people out there who can do it in about 15 seconds average using newer methods. That's probably about the limit for humans.

    If you see times lower than that it's because somebody got lucky on one particular solve. Sometimes the pieces just fall into place. I once did it in 19 seconds in front of a crowd of people but it was mostly luck (not that I told anybody that at the time...)

    --
    No sig today...
  41. Re:Solving != best solution by wisty · · Score: 1

    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.

  42. Re:The algorithm by Joce640k · · Score: 1

    Not to anybody with an IQ larger than their shoe size.

    --
    No sig today...
  43. Re:Pull off the stickers! by The+Clockwork+Troll · · Score: 1

    You really only need to pull off at most 48 of them.

    --

    There are no karma whores, only moderation johns
  44. Re:3x3x3 cube... 11x11x11 cube... by kmoser · · Score: 1

    Yes, but theirs goes up to 11x11x11.

  45. Re:Pull off the stickers! by G3ckoG33k · · Score: 1

    But then it would be no challenge.

  46. Re:Pull off the stickers! by Stalks · · Score: 1

    Some people can do it under 60 seconds ... with their feet.

    http://www.worldcubeassociation.org/results/e.php?i=333ft

  47. Already done! by ewanm89 · · Score: 1

    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.

    1. Re:Already done! by tompaulco · · Score: 1

      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 grade school. I was no marvel, though. I think I managed 47 seconds once. I certainly am not able to solve it blindfolded like some people.

      --
      If you are not allowed to question your government then the government has answered your question.
  48. Re:It's time for Slashdot to support Unicode prope by Archibald+Buttle · · Score: 1

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

    If they can't even manage to do basic counting, I fear there's bugger all chance they'll manage to do unicode any time soon.

  49. Re:Pull off the stickers! by maxwell+demon · · Score: 1

    I see, the challenge is in remembering the position of the colors on the cube, to avoid someone detecting your cheating after the fact because two colors which were on opposite sides of the cube before now aren't.

    --
    The Tao of math: The numbers you can count are not the real numbers.
  50. Re:3x3x3 cube... 11x11x11 cube... by QuasiSteve · · Score: 1

    Draw a square. Now draw a line 1/3rd of the way along the horizontal axis parallel to the vertical axis. Draw another line 1/3rd of the way along the vertical axis parallel to the horizontal axis. You should now have a square that is divided into 1 smaller square, 1 larger square, and 2 equally-sized rectangles. Those rectangles aren't squares, true, but the outer square you began with is still a square.

    Extrapolate that to a cube. Cut it up in any way you wish and each individually cut piece may not be a cube itself, but the original shape remains a cube.

    Obfuscant already answered the question I figured would follow; why couldn't it be a Rubik's Cube? So I refer you to his post for the answer.

  51. Why need "x3x3?" by Infiniti2000 · · Score: 1

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

  52. Sketchy Journalism by FrootLoops · · Score: 1
    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?

    1. Re:Sketchy Journalism by SuperMonkeyCube · · Score: 1

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

  53. Re:Pull off the stickers! by Dayze!Confused · · Score: 1

    Currently the record is a person averaging under 7s at the official competitions. I attended one once and saw a guy who averaged around 9s, most people competing (really competing) were around 10-15s, then there was me around 30s (just thought it'd be fun to try). The only girl who showed up to compete got around 2mins.

    --
    "All tyranny needs to gain a foothold is for people of good conscience to remain silent." [Thomas Jefferson]
  54. Snake oil by leifbork · · Score: 1

    Anyone knows solving a Rubik's cube is impossible.

  55. No by leifbork · · Score: 1

    Actually I may be lying, I believe the one-sized Rubik's cube may be solved for at least dimension 2.

  56. Re:3x3x3 cube... 11x11x11 cube... by QuasiSteve · · Score: 1

    Any piece which can be shifted into another piece's place has to be the same size and shape as the other piece, or it doesn't work right. Yours fails that.

    Yes, I'm pretty sure we covered that when I initially said that it wouldn't work for a Rubik's Cube. I though it was made more obvious when Obfuscant explained that to somebody else, too ;) Thanks for the contribution, though