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!
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
Well, that explains it; considering how fast the technology is changing, they probably didn't have 2.4 GHz versions 62 days ago.
And if you put the corner on twisted by a third of a turn, then scramble it up again, you have an insoluble puzzle to leave lying about to drive people nuts. B-)
Bantam Dominique roosters crow a four-note song. Once you've heard it as "Happy BIRTHday" you can't NOT hear it that way
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.
Practically speaking, this is more a memory intensive than a CPU intensive problem. Given that the Q6600 supports an FSB speed of only 1066 MHz, if the computations generally require a fetch from RAM (i.e. the on-die cache is insufficient to the task, as in most memory bound tasks) then you can't operate at the full speed of the chip since it is constantly waiting on the memory controller.
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.
One..Two..Three..CRUNCH...Ouch
The answer is that it takes three licks to get to the center of a standard Rubik's cube.
Fascism trolls keeping me up every night. When I starts a preachin', he HITS ME WITH HIS REICH!
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.
Wait, how did this get modded Interesting? A solved cube is indeed a member of all starting point, and it would be the only member of its set of essentially similar ones (and, for that matter, the member of the only set of essentially similar ones solvable in zero moves). I fail to see anything interesting about that.
Want a high quality FOSS RTS game? Try Warzone 2100!
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.
Hint: For this prank to work, the stickers should be different colors.
After all, I am strangely colored.
If the fan has a diameter exceeding 3 1/8 inches, it would be the sound of fan blades of infinite mass traveling backwards in time.
-
- - You can't take something off the Internet! That's like trying to take pee out of a swimming pool.
Unfortunately the "Interesting" moderation is not finest grain.
There are at least two subtypes of interesting:
- Interesting to someone with joint degrees in math and computer science
- Interesting to someone who has smoked two joints
Any thread involving Rubik's cube is going to pull both, sorry.
There are no karma whores, only moderation johns