Slashdot Log In
Rubik's Cube Algorithm Cut Again, Down to 23 Moves
Posted by
timothy
on Thu Jun 05, 2008 07:08 PM
from the at-this-rate-one-will-soon-be-enough dept.
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!"
Related Stories
[+]
Rubik's Cube Proof Cut To 25 Moves 386 comments
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."
Firehose:Rubik's Cube Algorithm Cut Again, Down To 23 Moves by Anonymous Coward
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.
Full
Abbreviated
Hidden
Loading... please wait.
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: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:5, Funny)
Parent
Easy (Score:5, Funny)
Step 1: Drop cube in can of paint. Done.
Parent
my best time -1 min (Score:5, Funny)
Parent
That's quick (Score:5, Funny)
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
I can always do it.... (Score:5, Funny)
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
18 moves is the limit (Score:4, Informative)
The math isn't hard. It's finding those correct 18 moves that is.
Re:18 moves is the limit (Score:5, Informative)
Parent
Solvable? (Score:5, Interesting)
Re:Solvable? (Score:5, Funny)
Parent
Re:Solvable? (Score:5, Insightful)
Parent
Only one move required... (Score:5, Funny)
There, saved you from another 22 pointless moves.
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.
I can do it in 2... (Score:4, Funny)
Parent
Re:LET THERE BE THREE moves... (Score:4, Funny)
Parent