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!"
I can do it in zero, I just declare that it's fine just the way it is and accuse anyone that tries to argue otherwise for being segregationists trying to keep all the different colors apart.
This method has firm group theoretic underpinnings too. An alternate way to view this excellent solution is to realize that moves don't matter. Thus, you can say all states of the Cube linked by moves are equivalent in their state of fineness and hence the entire orbit is a single equivalence class of acceptability. This reduces the overly complex and uninteresting problem to a trivial one. Perfectly mathematical thing to do.
lol, have that one on my shelf still sealed like that too. Totally amazed i remembered the name to google....
Are the ones that need to be a specific direction a lot more moves? The Pacman cube i have is a killer cause all the little ghosts and stuff started out upright 20? years ago and have been laying down sideways ever since:(
As a kid my best time was 1 min !
Used to just take off all the stickers on all faces and put them back in correct order.
Friends were confused though as to why i want to solve it alone in a room and not in front of them.
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...
So that would be, um, each face is three by three, um, nine stickers on each face. Then multiply that times the number of sides, so six times nine would be, uh,...
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.
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.
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.
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.
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.
My friends decided to flip two pieces without telling me, thinking that would really annoy me. They were quite disappointed when I solved the cube, as the second flip perfectly counteracted the effect of the first.
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.
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.
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
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?
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
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?
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.
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.
I still can't do it. (Score:5, Funny)
Re:I still can't do it. (Score:5, Funny)
I can do it in one .... I outsource it.
Parent
Re:I still can't do it. (Score:5, Funny)
Parent
Re:I still can't do it. (Score:4, Funny)
Parent
Re:I still can't do it. (Score:5, Funny)
I can do it in one .... I outsource it.
I can solve it faster .... I defenestrate [merriam-webster.com] it.
Parent
Re:I still can't do it. (Score:5, Funny)
Please, disregard the previous sentence.
Please, disregard the previous sentence.
Parent
Re:I still can't do it. (Score:5, Funny)
Parent
Re:I still can't do it. (Score:4, Funny)
When I was a kid I had a rubix cube which one day resulted in this,
Angry Kid + Teacher(target) + Rubix Cube = defenestrate + one half rubix cube + dozens little pieces of a cube.
Afterwards I felt pretty bad about the whole thing...
Parent
Re:I still can't do it. (Score:4, Funny)
Parent
Re:I still can't do it. (Score:5, Funny)
Parent
Re: (Score:2)
http://www.puzzle-shop.de/aggie-cube.html [puzzle-shop.de]
lol, have that one on my shelf still sealed like that too. Totally amazed i remembered the name to google....
Are the ones that need to be a specific direction a lot more moves? The Pacman cube i have is a killer cause all the little ghosts and stuff started out upright 20? years ago and have been laying down sideways ever since
Easy (Score:5, Funny)
Step 1: Drop cube in can of paint. Done.
Parent
Re: (Score:3, Funny)
Paint is so 1987. Sears now sells powder coaters for $150.
There is nothing that can't be improved with a little powder coating. Pencils, silverware, desks...
my best time -1 min (Score:5, Funny)
Parent
That's quick (Score:5, Funny)
Re: (Score:3, Funny)
Try spray paint.
Re:That's quick (Score:5, Funny)
This would definitely faster than my method of taking it apart and reassembling it in the correct order.
Parent
Re:That's quick (Score:5, Funny)
Parent
Do the math, quick! (Score:5, Funny)
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...
So that would be, um, each face is three by three, um, nine stickers on each face. Then multiply that times the number of sides, so six times nine would be, uh, ...
Forty two.
Parent
Re: (Score:3, Funny)
It's 42.
Trust me.
I can always do it.... (Score:5, Funny)
Re:I can always do it.... (Score:4, Insightful)
Parent
Or... (Score:5, Insightful)
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)
Parent
Re: (Score:3, Informative)
Well, he did say any arbitrary configuration.
It is currently known that there is at least one configuration that is not solvable in 20 moves or less.
The point being: it is possible to solve a cube from any arbitrary configuration in N moves, where N is 21, 22 or 23 (it's not yet known which).
18 moves is the limit (Score:4, Informative)
The math isn't hard. It's finding those correct 18 moves that is.
Re: (Score:2, Informative)
It should be 2(3^3)/3
Re:18 moves is the limit (Score:5, Informative)
Parent
Re: (Score:3, Insightful)
1) "there exists" a configuration for which the minimum number of steps is "18".
2) "for all" configurations, "there exists" a solution that takes less than XX steps to solve.
We are trying to find the answer to #2. We know that #1 exists, so we know that the lower bound of a perfect solver (#2) is 18.
The article seems to be saying that the upper bound of #2 is 21-23.
Re: (Score:3, Interesting)
So there might be actually 4^6 solutions (4096).
Solvable? (Score:5, Interesting)
Re:Solvable? (Score:5, Funny)
Parent
Re:Solvable? (Score:5, Insightful)
Parent
Re:Solvable? (Score:4, Funny)
Parent
Re: (Score:3, Insightful)
Re: (Score:3, Funny)
It is pretty annoying when people do the sticker trick to only solve one side of a cube.
Re: (Score:2)
Re: (Score:2, Informative)
Re: (Score:3, Insightful)
Definitions (Score:2)
LET THERE BE THREE moves... (Score:3, Funny)
2. Let Dry
3. PROPHET
I can do it in 2... (Score:4, Funny)
Parent
Re:LET THERE BE THREE moves... (Score:4, Funny)
Parent
That's great. (Score:2)
After that, solve for the max number of edits a Slashdot editor will actually do before just posting the article anyway.
Mastermind (Score:2)
http://en.wikipedia.org/wiki/Mastermind_(board_game) [wikipedia.org]
but rubik's hypercube remains unsolved (Score:2)
rubik's hypercube has me stumped
Only one move required... (Score:5, Funny)
There, saved you from another 22 pointless moves.
Slightly offtopic (Score:3, Interesting)
So I'm curious if anyone else has experienced this as being the obvious but not perfect solution?
Hofstadter (Score:3, Informative)
Recapping what it means (Score:5, Informative)
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.