Slashdot Log In
Rubik's Cube Proof Cut To 25 Moves
Posted by
samzenpus
on Wed Mar 26, 2008 10:44 PM
from the too-much-time-on-your-hands dept.
from the too-much-time-on-your-hands dept.
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."
Related Stories
[+]
Rubik's Cube Algorithm Cut Again, Down to 23 Moves 202 comments
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.
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.
Which 25 moves? (Score:5, Funny)
Re:Which 25 moves? (Score:5, Funny)
Left, right, right, down, down, left, up, right, up, up, left, down, down, right, up, down, left, right, up, left, down, down, right, up, left.
Just a guess ;)
Parent
Wow, it really works (Score:5, Funny)
Parent
Re:Wow, it really works (Score:5, Funny)
Parent
Re:Wow, it really works (Score:5, Insightful)
Parent
Re:Which 25 moves? (Score:5, Funny)
The old 26 move algorithm was the same except 'select' then 'start'
Parent
Re:Which 25 moves? (Score:5, Funny)
Those sound familiar, but I can't be sure - don't have anyone's thighs wrapped around my head at the moment...
Parent
Re:Which 25 moves? (Score:5, Insightful)
In other words, they are left as an exercise to the reader.
Parent
Re:Which 25 moves? (Score:5, Funny)
Parent
Re:Which 25 moves? (Score:5, Informative)
Parent
Re:Which 25 moves? (Score:5, Funny)
Parent
Re:Which 25 moves? (Score:5, Funny)
Parent
Theory versus practice (Score:5, Insightful)
This could make a good case study for business schools
Re:Theory versus practice (Score:5, Insightful)
Instead, it makes a great case for doing the research on the front end to eliminate lengthy repetition of useless iterations to shorten the overall time.
Parent
Zero moves.... (Score:5, Funny)
Suboptimal Nonsolution (Score:5, Funny)
"God's Algorithm" (Score:5, Interesting)
One, and only one vertex in this graph corresponds to the solved configuration of the cube.
Note that this graph represents all possible moves and positions--any scrambled cube is a vertex somewhere in the graph, and solving that cube is equivalent to traversing a path in this graph to the "solved" vertex. In general, many paths to the solution exist, some of which will be shorter than others.
The question of interest is this: Which vertex/vertices of this graph is/are farthest away (i.e., requiring the most edge traversals) from the solved vertex, and how far is it? As of this latest discovery, this maximum distance is 25. It means that every possible scrambled configuration of the cube can be solved in 25 moves or less.
Wikipedia notes that we know that at least 20 moves are required to solve the cube for every configuration--that is to say, we know that this maximum distance is at least 20 (there exists some vertex that is at least 20 steps away from the solved vertex). It is believed that the true "least upper bound" is closer to 20 than it is to 25.
Finally, we should clarify that a "single move" can either mean a rotation of a face by either a quarter- or half-turn, or it could mean a quarter-turn only. These different metrics of what constitutes a "move" leads to different answers.
Re:1.6ghz? (Score:5, Interesting)
In benchmarks, AMD CPUs tend to beat Intel CPUs on memory bound tasks, even though Intel CPUs win at CPU intensive tasks because the AMD CPUs integrate a faster memory controller on-die instead of relying on a slower FSB. Intel's weakness is less noticeable when the CPU is running at a clock speed closer to the FSB, and given that increases in CPU clock speed increase the power and heat usage geometrically, it wouldn't make sense to run the CPU at full clock for a task of this nature.
Parent
Re:1.6ghz? (Score:5, Funny)
Parent
Re:1.6ghz? (Score:5, Funny)
Parent
Re:Damn. (Score:5, Funny)
Parent
Re:Annoying my older brother (Score:5, Funny)
Parent
Re:You only need one (Score:5, Funny)
The answer is that it takes three licks to get to the center of a standard Rubik's cube.
Parent
Re:You only need one (Score:5, Interesting)
Fun trick: Take a solved cube, and on one of the inner edge pieces (the ones with two stickers), and swap the colors. Mix it up, and give it to someone to solve. Or take a corner piece and rotate it.
Hint: It's unsolvable. The Rubik's Cube, if taken apart and put back together randomly, will more often than not end up being unsolvable.
A great way to frustrate that showoff cuber at the office. Especially if they appreciate it when someone scrambles the cube and they'll have it solved in front of everyone. Just go and put it back together randomly, or do one of those devious swaps, and you'll have fun watching him try to solve it.
Parent
Re:Computational proofs (Score:5, Interesting)
I would guess that it is more common in fields like graph theory and other discrete math just because obviously the discrete lends itself well to computers, and many times it's not hard to whittle it down to a finite number of cases to check. The objects of study also tend to admit matrix representations and other things computers are good at working with. Even before computers you'd cut things into lots of cases that you needed to verify but now it's easier to handle proofs that need larger number of cases.
I've actually seen some really interesting proofs using computers to check things over continuous domains. The basic idea lots of times is if you can check things over a fine enough "net" of cases in some space and you can prove that the variance between each of these points is small enough, then you can cover your entire space by just checking a finite number of cases.
Given all this people still have a healthy amount of skepticism for computer aided proofs and would rather not if possible in most cases, especially when you're talking about billions of cases. Then again what is the potential for errors in a computer checking billions of cases based on a relatively small amount of code versus some of these enormous human-created decades-long behemoth [wikipedia.org] proofs?
Parent