Slashdot Mirror
Rubik's Cube Proof Cut To 25 Moves
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."
What are these magic 25 moves that can solve a rubik's cube regardless of starting position?
Give me Classic Slashdot or give me death!
The correct answer is a hammer.
Just -1, Troll talking to another.
Why wasn't the Q6600 at 2.4ghz like normal? Anyone know?
When I was little, I still remember annoying the crap out of my older brother by "solving" his Rubik's cube removing and replacing the stickers in the correct location. Eventually the glue would wear off the dots and you would suddenly have a slightly easier puzzle to solve.
This Green Technology uses 1/26th less energy to solve a rubix cube! When's the IPO?
he took 1500 hrs to solve that damn thing. I take a minute. have a random chinese guy and the cube orders itself. Dammit! sorry. i just took calculus test and my caffeine dosage is nondecreasing at exponential rate.
This is a good example of where the inefficient method (of about 60 moves iirc) is much faster in terms of time. The 25 move solution is elegant but just not worth it in terms of computations, time etc...
:-)
This could make a good case study for business schools
I consider a Rubik's Cube to be "solved" regardless of its starting position. I subscribe to the Fred Rogers solution: it's fine just the way it is.
--I'm so big, my sig has its own sig.
-- See?
Is this becoming common for proofs to be done by searching through billions of combinations (albeit, reduced to that number only through some clever observations about symmetry) and simply showing that each one is possible because your computer found a solution? Sometimes we talk about the number of steps in a proof, this proof must have trillions of steps. Not complaining, it just seems like a uniquely computer-age technique. I know of no reason to assume that every true thing that can be proven has a concise, elegant proof - in fact I'm sure that cannot be true because there are only so many small numbers to go around!
No, just make the rubix cube out of the oled keys of the optimus keyboard. Integrate with bluetooth and "solve" the rubix in a single button press.
Well.. maybe. Or Maybe not. But Definitely not sort of.
Since it took just a few months for someone to do this on one computer, this seems like an ideal candidate for a small-scale distributed computing project. TFA says his program's working on 24, so he already has an algorithm. Assuming it's massively parallelizable, which from the description of the method seems very likely, it shouldn't take too many computers to get to 24 in a matter of days. Anyone care to implement the algorithm in one of the open-source distributed computing frameworks out there?
I painted all 6 sides the same colour on mine.
I am a free slashdotter. I will not be modded, blogged, DRM'd, patented, podcasted or RFID'd. My life is my own.
In my research, I've reduced female behavior to a set of 50 million parameters. By partitioning this space into subspaces and finding equivalent sets, I think I might be able to get laid.
However I've noticed a problem: if I introduce a parameter to model a female's response to this research, the spaces collapse to zero, i.e., a null set.
I find this quite puzzling. Simply by examining my chances of getting laid, I reduce my chances to zero.
Did I mention I can solve the Rubik's cube in 25 moves?
I've been doing some interesting work in the other direction. I've managed not to solve a Rubik's cube in what I estimate to be 1.5 million moves. That seems to be the upper limit after which the stickers fall off.
Here's the paper itself, if you want more detail than the very general summary in TFA.
I started with a solved cube and now it looks totally scrambled.
....or a girlfriend.
and around 1500 hours of time
pfffft... Java
Take every possible unique configuration of the cube (those that are obtainable by legal moves--no rearranging stickers or disassembling allowed). Represent each configuration by a vertex. Now join two vertices by an edge if and only if the configurations represented by those two vertices differ by a single move (we will elaborate on what constitutes a "single move" later). The result is a mathematical object called a graph. A horrendously giant graph.
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.
This is a proof of upper limit, not an optimal solution. He proved is that all possible combinations of 26 moves yielded a position which was symmetrical to a cube with a lesser number of moves applied to it.
An optimal solution would probably look like a bell curve going from "zero moves required" (ie. already solved) all the way up to "25 moves required" (which we now know is the upper limit...)
No sig today...
He or she did suggest 25 moves, no more, no less. I counted them myself so that you don't have to.
http://truckbearingkibble.com/comic/2008/03/10/eureka%C2%B3/
In light of a certain parallel programming news item a few days ago, I'd like to see him use the same code, same CPU on this one: http://www.youtube.com/watch?v=UrjmeYdVTlc. Hold your breath for that solution.
.
David Joyner has a book which explores some of the math behind the Rubik's cube: http://www.amazon.com/Adventures-Group-Theory-Merlins-Mathematical/dp/0801869471
If you are interested in playing around with the symmetry group associated to the Rubik's cube, Sage (http://www.sagemath.org) has good support for it; the documentation can be found at http://www.sagemath.org/doc/html/ref/module-sage.groups.perm-gps.cubegroup.html . Sage also includes a number of efficient solvers for the Rubik's cube.
I have to admit, in reading the summary, Tomas Rokicki's name seemed very familiar....
And of course! He's the author of dvips! So we have him to thank not only for this cutting-edge breakthrough in mathematical solutions to Rubik's Cube, but also for turning our not-overly-portable DVI files into beautiful, beautiful Postscript.
iSKUNK!
A "perfect" solution in 25 moves would be impossible for a human, it would basically mean knowing all possible combinations of the cube and how to get there (and that's an awful lot of combinations!)
I actually solved the cube all by myself back in the 80's. I'm amazed that so much effort is still being put into it and some of the methods used by the record breakers need an awful lot of dedication to learn.
No sig today...
RTFS dude. He didn't solve a cube, he proved that a cube can be solved from any starting position in 25 moves or less.
A *human* can solve a cube in seconds - it's not impressive for a computer to do it.
Moving colored stickers? Amateurs! I can solve any cube in three moves... with a can of spray paint. Point, spray, spin.
When our name is on the back of your car, we're behind you all the way!
I one met Erno Rubik himself.
Nice guy and all, but it took me half an hour to finish shaking his hand.
Slashdot Burying Stories About Slashdot Media Owned
Perhaps it can't be reduced to 19 moves. But then again, Kociemba's algorithm has not yet provided a proof that the diameter of the cube group is indeed 20 (in face counting). We won't have such a proof until an optimal solver is used, something that could take years of run time on current hardware. Application for a grid perhaps?
Hello. I do not have Asperger Syndrome and therefore could not understand what was just written in the synopsis. Worst yet, I do not even understand why it is important that a person can solve a Rubiks cube in 25 moves. I feel really left out and as a result I am starting a Persons without Asperger Support Group. If you too are totally lost by this article and fell left out, please join.
You don't have to be smart to use a Mac, you just have to be smart enough to buy one