Catch up on stories from the past week (and beyond) at the Slashdot story archive

 


Forgot your password?
Close
typodupeerror
×
Math Puzzle Games (Games) Entertainment Games

Rubik's Cube Algorithm Cut Again, Down to 23 Moves 202

Posted by timothy from the at-this-rate-one-will-soon-be-enough dept.
Bryan writes "The number of moves necessary to solve an arbitrary Rubik's cube configuration has been cut down to 23 moves, according to an update on Tomas Rokicki's homepage (and here). As reported in March, Rokicki developed a very efficient strategy for studying cube solvability, which he used it to show that 25 moves are sufficient to solve any (solvable) Rubik's cube. Since then, he's upgraded from 8GB of memory and a Q6600 CPU, to the supercomputers at Sony Pictures Imageworks (his latest result was produced during idle-time between productions). Combined with some of Rokicki's earlier work, this new result implies that for any arbitrary cube configuration, a solution exists in either 21, 22, or 23 moves. This is in agreement with informal group-theoretic arguments (see Hofstadter 1996, ch. 14) suggesting that the necessary and sufficient number of moves should be in the low 20s. From the producers of Spiderman 3 and Surf's Up, we bring you: 2 steps closer to God's Algorithm!"
This discussion has been archived. No new comments can be posted.

Rubik's Cube Algorithm Cut Again, Down to 23 Moves More

Rubik's Cube Algorithm Cut Again, Down to 23 Moves

Comments Filter:

  • I still can't do it. (Score:5, Funny)

    by ASMworkz ( 1302279 ) on Thursday June 05, 2008 @06:09PM (#23675935) Homepage
    Call me when it's down to 10 moves! :)

  • That's quick (Score:5, Funny)

    by ricebowl ( 999467 ) on Thursday June 05, 2008 @06:10PM (#23675947)
    And here I used to think my method was faster; but since there's more than 23 stickers on the cube I guess it ain't any more...

  • I can always do it.... (Score:5, Funny)

    by Brad1138 ( 590148 ) * <brad1138@yahoo.com> on Thursday June 05, 2008 @06:13PM (#23675995)
    in 48 moves or less. Luckily the center sticker is always in the right place so I don't need to move that one.

    • Re:I can always do it.... (Score:4, Insightful)

      by tangent3 ( 449222 ) on Thursday June 05, 2008 @08:02PM (#23676989)
      With 6 colours and 9 squares per face, there will always be 2 squares of the same colour per face, so it can always be done in 42 moves or less.

    • Re: (Score:2)

      by syousef ( 465911 )
      in 48 moves or less. Luckily the center sticker is always in the right place so I don't need to move that one.

      You don't need to remove all 48 stickers. At least one of the outer 8 stickers will match the center on at least one side. So you don't have to unstick them all. So I can do it in 47 moves or less. Nyer!
    • MAN, that's Forty Six & Two!

  • Or... (Score:5, Insightful)

    by Anonymous Coward on Thursday June 05, 2008 @06:15PM (#23676023)
    "Combined with with some of Rokicki's earlier work, this new result implies that for any arbitrary cube configuration, a solution exists in either 21, 22, or and 23 moves"

    Or 1 or 2 or 3 or 4 or 5 or 6 or 7 or 8 or 9 or 10 or 11 or 12 or 13 or 14 or 15 or 16 or 17 or 18 or 19 or and 20 moves.

    • Re:Or... (Score:5, Funny)

      by this great guy ( 922511 ) on Friday June 06, 2008 @03:25AM (#23679497)
      You could share the script you used to output that sentence...

      #!/bin/sh echo "Or 1 or 2 or 3 or 4 or 5 or 6 or 7 or 8 or 9 or 10 or 11 or 12 or 13 or 14 or 15 or 16 or 17 or 18 or 19 or and 20 moves."

  • 18 moves is the limit (Score:4, Informative)

    by BadAnalogyGuy ( 945258 ) <BadAnalogyGuy@gmail.com> on Thursday June 05, 2008 @06:18PM (#23676047)
    Mathematically, the limit is a hard 18 (by faces): 6^2 / 2. alternatively by squares per face: ((9 * 6) / 3) ^ 2 / (2^2)

    The math isn't hard. It's finding those correct 18 moves that is.

    • Re: (Score:2, Informative)

      by BadAnalogyGuy ( 945258 )
      Sorry, that second one is from another algo.

      It should be 2(3^3)/3

    • Re:18 moves is the limit (Score:5, Informative)

      by IWannaBeAnAC ( 653701 ) on Thursday June 05, 2008 @06:33PM (#23676193)
      No, that is just a lower bound: by counting the number of possible configurations it can be shown that there exists at least one configuration that takes 18 or more steps to solve. It says nothing about an upper bound, which could (and is!) somewhat larger.
      • And who said abstract math isn't useful?

    • Re: (Score:3, Interesting)

      by mikael ( 484 )
      But there is more than one solution - the centre cube on each face can have any one of four orientations. If you were to paint arrows onto each cube, scrambled the cube, and then solved it, the arrows would not necessarily be aligned with the rest of the cubes on that side.

      So there might be actually 4^6 solutions (4096).

  • Solvable? (Score:5, Interesting)

    by CastrTroy ( 595695 ) on Thursday June 05, 2008 @06:20PM (#23676071)
    The summary says for every solvable cube. What does that mean. Every configuration is a solvable one. If you remove a corner and rotate it, and place it back in the cube, the cube is no longer solvable, but I would argue that it's no longer a rubik's cube either.

    • Re:Solvable? (Score:5, Funny)

      by pwnies ( 1034518 ) * <j@jjcm.org> on Thursday June 05, 2008 @06:28PM (#23676149) Homepage Journal
      It may not be a rubiks cube, but it would be quite humorous if strategically placed in an "Obsessive Compulsive Puzzle Solvers Anonymous" meeting.

      • Re:Solvable? (Score:5, Insightful)

        by ampathee ( 682788 ) on Thursday June 05, 2008 @06:40PM (#23676265)
        Not really. Anyone who could solve a cube would find the rotated corner in a minute or two. My group of friends were into rubiks cubes a few years ago, and that trick got old fast.

      • Re: (Score:3, Insightful)

        by Kjella ( 173770 )
        Not for very long. While nowhere near the minimum number of steps, there are fairly simple techniques to solve a Rubik's cube so they'd quite quickly conclude it's been tampered with.
        • Yeah, when they first come out with books containing solutions I decided to fix a cube so that it was unsolvable and leave it out for someone who had memorized the solution to try and solve it. They always figured out the tampering within a minute or so.

          Sadly, it was not nearly as amusing as I had hoped.

          At least I still had my RPN calculator to lend to the smartass premeds in chem lab. (Furious punching of keys followed by "Where's the Equals?")

          • At least I still had my RPN calculator to lend to the smartass premeds in chem lab. (Furious punching of keys followed by "Where's the Equals?")
            I had a guy try that on me. He was rather put out when he found I knew how to use it.
            • When I forgot my trusty TI-81 in a calculus class, a friend tried to do that to me by handing me an HP calculator. I was very confused at first, and my friend had a laugh, but he didn't know how much assembly programming I had done and manipulating stacks wasn't exactly foreign to me.

              That's my "i'm smart" story since I have to admit I was never very good at Rubik's Cube. :(

              • That's my "i'm smart" story since I have to admit I was never very good at Rubik's Cube. :(
                Oh, I never actually solved the thing, unless you count prying it apart and re-assembling it in the correct order!

      • Re: (Score:3, Funny)

        by Deanalator ( 806515 )
        I once spent and hour or so working on a cube before I realized that one of the two color pieces had two colors from opposite sides of the cube :-(

        It is pretty annoying when people do the sticker trick to only solve one side of a cube.
    • But if you're given an arbitrary cube, how do you know if it's been tampered with such that it's no longer solvable? It may be the case that the simplest way to determine that, that works in every case, is to try and solve the cube and discover you can't. I don't believe it's a trivial problem to stare at a cube and figure out if a simple change like a rotated corner has been made to it.

      • Re: (Score:2, Informative)

        by Anonymous Coward
        Nah. It's pretty easy to tell if a scrambled cube is solvable. You can see which individual edge pieces are "flipped" and which corner pieces are correct or rotated (either clockwise or counter-clockwise). In a solvable cube, you must have either 0 flips or an even number of flipped "edge" pieces. If you assign a value of 1 to clockwise turned corner pieces and a value of 2 to counterclockwise pieces, adding up the values must be divisible by 3. Assuming these criteria are met, a scrambled cube can be

    • Re: (Score:3, Insightful)

      by Kjella ( 173770 )
      Probably because it's more work to find what all the permutations starting from a solved rubik's cube are, instead you start with a general cube and quickly eliminate the unsolvable ones. Techincally you're solving a slightly more general problem with the rubik's cube as a special case, so "solvable cube" is probably correct in the paper but equals rubik's cube in practical life.
    • It really depends if solvability is implied in the definition of a rubik's cube. The game of Solitaire is not always winnable from initial given cards - does that mean that the dealt cards aren't a legal Solitaire game, or just not winnable?
      • A Rubik's cube is one of 12 possible (similar looking) cubes you can make if you start with all the pieces taken apart. The set of all possible cube configurations is separated into 12 orbits and a Rubik's cube can only reach configurations within the orbit that it's already in when it's solved. I wouldn't call the other 11 cubes Rubik's cubes. You start by scrambling a solved cube like a normal person, not assembling an unsolved cube from parts to see if you're going to "win" or "lose" with the cube you ma

    • Every configuration is a solvable one.

      If you take a cube apart and put it back together in random order, it may not be solvable. IIRC there are twelve sets of configurations where it is possible to get between configurations in the same set, but not between configurations not in the same set. (This obviously ignores configurations where you just took the stickers off and repasted them.)

  • LET THERE BE THREE moves... (Score:3, Funny)

    by davidsyes ( 765062 ) on Thursday June 05, 2008 @06:23PM (#23676101) Homepage Journal
    1. Pour paint on Cube
    2. Let Dry
    3. PROPHET

  • Maybe he should next try and find the minimum number of edits to fix the grammar in a Slashdot article submission.

    After that, solve for the max number of edits a Slashdot editor will actually do before just posting the article anyway.
  • I know it's not a Rubik's cube, but I can solve any Mastermind puzzle in seven moves.

    http://en.wikipedia.org/wiki/Mastermind_(board_game) [wikipedia.org]
  • that 4th dimensional rotational axis means you have to reach forward in time in order to solve one side in the present, without affecting any other sides you solved in the past, meaning you can't twist it to the present, without affecting what you've already solved in the future

    rubik's hypercube has me stumped
    • A 4 spatial dimension hypercube as been solved. There are giant algorithms that allow humans to solve them given enough time (I think its around 1000 moves). A 5d version is also around (and also solved. by computers only I think).

  • Only one move required... (Score:5, Funny)

    by FoolsGold ( 1139759 ) on Thursday June 05, 2008 @07:02PM (#23676515)
    Blend the fucker - http://www.youtube.com/watch?v=NrqHHBibRvs [youtube.com]

    There, saved you from another 22 pointless moves.

  • Slightly offtopic (Score:3, Interesting)

    by KokorHekkus ( 986906 ) on Thursday June 05, 2008 @07:10PM (#23676573)
    I actually found one of the solutions (obviously not uniquely) for the Rubiks Cube myself. It ended up to be the "corners first"-type of solution which I think is quite a natural way to reach a solution (it's basically a divide and conquer algorithm). If you can put the corners in their right place you only need to use a 8 move permutation to solve the rest which I call "the cross"-pieces.

    So I'm curious if anyone else has experienced this as being the obvious but not perfect solution?
    • Ehum, of course I meant the same 8 move permutation applied many times, not just once. Sorry.
    • Yes, corners first. I don't know about the same 8 move combination but IMO there are only 8 pieces that aren't obvious how to position.

      First you do four corners on a face - anybody can do this without any "method". (at least I could)

      Then you position the second four corners and rotate them as necessary - this is more tricky.

      Then you position the eight edges on opposite faces (leaving the middle slice unsolved). (How to do this was completely obvious to me, YMMV)

      Then you need to position and rotate the remai
      • The eight move permutation I use on a Rubiks cube with the corners done is:

        Turn "right side" a quarter turn towards you
        Turn "bottom layer" a quarter turn to the left
        Turn "right side" a quarter turn away from you
        Turn "center layer" a quarter turn to the right
        Turn "right side" a quarter turn towards you
        Turn "bottom layer" a quarter turn to the right
        Turn "right side" a quarter turn away from you
        Turn "middle layer" a quarter to the left


        Those 8 moves will shift places of 3 edge pieces, the two in th

    • Re: (Score:2, Interesting)

      by SuperMonkeyCube ( 982998 )
      Corners first, when initially stumbled upon by accidentally solving the corners, does seem rather obvious. Many of the people that were fast in the early days of cubing were using corners first solutions. Any of us that were trying to make funny patterns on the cube were familiar with moving groups of edges around that didn't disturb the corners. Also, the easiest move to flip edges left everything else undisturbed, and flipped one edge on the top layer and three in the middle layer. (That would be RERER
  • This is just using a powerful computer to solve it by brute force... it's not really an algorithm, it's just a proof of a new upper bound.

    (I know, technically speaking, brute force probably does count as an algorithm, but it's not a very impressive one.)

    • Re: (Score:2, Informative)

      by rokicki ( 132380 )
      This result required the use of *many* computers to solve *many* positions (approximately four million billion positions), and each found solution was 20 moves or less.

      Yes, in some terms it was brute force, but consider how big a number four million billion is, and how long it takes to solve just a single position in 20 moves or less.

    • The art in using brute force is in pruning down the search space.

      For example, calculating the optimal tic-tac-toe game by hand is a lot easier once you notice and exploit the symmetries.

      Some "brute force" algorithms move from exponential to cubic or better once you trim them down properly. So any new tricks for improving brute force are of interest.

    • Re: (Score:2)

      by phliar ( 87116 )

      Beauty is in the eye of the beholder....

      This is not about using brute-force solvers. Given some problem space, there are many interesting things to think about: optimal algorithms -- in time, and in memory -- of course; but also exploring the structure of the space itself. Interesting symmetries, upper and lower bounds on path and cycle lengths, ... . The possibilities are boundless.

      And no one would consider using a brute-force solver, but writing one would be interesting. Give it a try.

  • Hofstadter (Score:3, Informative)

    by pez ( 54 ) * on Thursday June 05, 2008 @07:53PM (#23676923) Journal
    Perhaps slightly off-topic, but the Hofstadter cited (via Metamagical Themas) is the same Douglas Scott Hofstader that wrote Goedel, Escher, Bach -- one of the greatest books ever written.
    • Anyone who has only read GEB is really missing out - both Metamagical Themas and The Minds I are also real mind openers. They take the themes raised in GEB and explore them further.
       
      Fluid Concepts       and Le Ton Beau De Marot are highly skippable.
    • A real Hofstadter fan/pedant would have complained about the "Hofstadter 1996" knowing it was off by a decade.

  • Recapping what it means (Score:5, Informative)

    by Anonymous Coward on Thursday June 05, 2008 @09:58PM (#23677923)
    When the limit was proved to be no worse than 25, there were lots of comments on Slashdot that misunderstood various aspects of what this means.

    Here are clarifications for some common points of confusion:

    1. What Tom has shown, that "an arbitrary cube can be solved in 23 moves", it means the nastiest legal cube needs no more than 23 face turns to solve. Obviously many starting configurations can be done in less.

    2. This type of research doesn't tell you WHICH 23 moves. Only that it's 100% certain that there exists a 23-moves-or-shorter solution, for any legal cube.

    3. It's easy to figure out the total number of permutations of the cube. Given that, it can be determined that 17 face-turns doesn't produce enough different permutations, but 18 does, so there is a definite lower bound of 18 moves, that is, there exists at least some configurations that MUST be 18 moves or more away from solved.

    4. Specific configurations have been found that provably need 20 face turns to solve. So the worst-case will never get better than that.

    5. It may be possible to narrow the limit further, showing that all cubes can be solved in 22 face turns or less. Maybe 21. Maybe 20. It will never get lower than that.

    Put succinctly, as of today, the worst-case number of face-turns to solve a cube is no worse than 23. It's been known for a while that the worst case is no better than 20.
    • Can a face turn be 180 degrees, or is that 2 turns? My guess from a normal person perspective is that a 180 degree turn is one move. The programmer and armchair mathematician in me says that a 180 degree turn is two moves, as it passes through one configuration on the way to another. So what is the generally agreed upon definition of a move?

      On a related note, when I was a kid some people thought sliding a middle slice was a move, when it was clear to me that it was really 2 "face turns". From the terminolo

  • You know, if you want to make faster progress I suggest you consult the experts of all things cube [timecube.com].
  • I remember "Computer Tom" sitting near the back of the class with headphones on, programming in BASIC on a SHARP. When the prof dared ask Tom a question, Tom invariably got it right and often pointed out a mistake earlier in the problem. I wonder if he recalls the "Nun-inverting" amplifier?

    If you read this Tom, hope we didn't take up too much of your valuable programming time and thanks for the VAX account elevation. :)
  • So much brainpower spent on trying to figure out a toy.
  • I just take them apart and reassemble them as solved.

Slashdot Top Deals

No spitting on the Bus! Thank you, The Mgt.

Close