"But to want to repeat the Cube - that is not the way to live." - Erno Rubik

August 9, 2010 5:28 AM

Every position of Rubik's Cube™ can be solved in twenty moves or less.
posted by Cat Pie Hurts (50 comments total)

They say: "We did not find optimal solutions to each position, but instead only solutions of length 20 or less."

If so, then what does that table on the lower right represent? The non-optimal solution they happened to find for each position?

Also, it looks like Michael Reid had already proved, in 1995, that God's Number is at least 20. These guys proved it was exactly 20.
posted by vacapinta at 5:36 AM on August 9, 2010 [1 favorite]

These guys proved it was exactly 20.

Only for very specific universes that are made up of 3x3x3 grids.
posted by Civil_Disobedient at 5:38 AM on August 9, 2010 [1 favorite]

I have successfully proven that the only way to win is not to play.

Stupid cube!
posted by blue_beetle at 5:43 AM on August 9, 2010 [5 favorites]

First, P is not equal to NP... now this.

I hate Mondays.
posted by Joe Beese at 5:44 AM on August 9, 2010 [1 favorite]

Wait, so P really is equal to NP? I'm confused.
posted by kipmanley at 5:45 AM on August 9, 2010

Damn you Joe Beese!
posted by kipmanley at 5:46 AM on August 9, 2010

How did the other attempts prove it was at least 23 or at least 24? Did they check the entire set but have a less efficient algorithm?
posted by smackfu at 5:48 AM on August 9, 2010

Sorry, at most 23 or 24. It was already proven to be at least 20.
posted by smackfu at 5:48 AM on August 9, 2010

How did they do it?

"We partitioned the positions into 2,217,093,120 sets of 19,508,428,800 positions each."

*smacks forehead* Of course! Why didn't I think of that!

But seriously, I like it when applied mathematics works out like this. I wonder if these 20-step solutions could be turned into rules a human could use ("if you need this element to move there, do this") or if they are so highly optimized that you'd need a chart of all positions to look up the correct 20-move sequence.
posted by PontifexPrimus at 5:50 AM on August 9, 2010

if you need this element to move there...

Then you turn the middle side topwise. Topwise!
posted by DU at 5:54 AM on August 9, 2010 [7 favorites]

The distribution of required-move solutions is pretty interesting. Hits a peak at 18 and then drops off a cliff.
posted by Blazecock Pileon at 6:06 AM on August 9, 2010

It only takes one step to solve the rubix cube - set it down and walk away.
posted by fuq at 6:13 AM on August 9, 2010 [1 favorite]

So when I was in college, I proctored a study of ADHD drugs. We had participants (mostly teenage boys) come in for several trials during which they would perform various tasks that were intended to measure their focus, presumably. In one of the tasks, I would give them a Rubik's Cube, turn the video camera on, then watch them try to solve it for something like 5 or 10 minutes. Tedious work, in general. For motivation, the participants were offered, let's say, $100 if they completed the puzzle in the time given. Most of the participants would halfheartedly fiddle with the Cube until I called time, especially when they were off their medication. In contrast, one of our participants totally gamed the system by researching some system whereby you repeat the same sequence of movements enough times to solve any Cube in relatively short order. He managed to make probably around $900 by the time his trials were over. I will admit that the first time he did it I was pretty mesmerized. He tried to explain it to me, but honestly I wasn't motivated to learn. The kid even had a printout showing the technique and he would study it before each trial. I never asked the doctor who was running the study if that was a useful data point, since it certainly took focus to research Rubik's Cube solutions and then execute them under time constraints. I'm almost certain that the doctor wasn't expecting any of his subjects to take that route.

I feel like I should send him this link...
posted by This Guy at 6:26 AM on August 9, 2010 [15 favorites]

I think it's interesting how commonplace this exhaustive proof-by-computer technique has become. Back when the Four Color Theorem was proven it was hugely controversial, now it's just /shrug. There's a lot of human work involved in simplifying the problem down, but when you get to "only needs 35 years of CPU time" there's not much point in doing more hard work.
posted by Nelson at 6:53 AM on August 9, 2010 [2 favorites]

They actually ship them now with solutions that are pretty easy to memorize. Solving them using human-memorizable algorithms take a lot more than 20 steps, of course. The most popular is solving them in "layers". You solve one layer (face), which you don't need an algorithm for. Then solve the middle layer, which is only 4 actual edge-pieces, by using a single algorithm that can rotate them around without messing up your work on the first layer. Then the final layer is done with a handful of more complicated ones for swapping bricks around without affecting your previously solved spots. Depending on the state of the cube, this method can take hundreds of turns, or just a handful. The more algorithms you memorize, the faster you can do it. Pretty cool stuff if that's your thing.
posted by cj_ at 6:53 AM on August 9, 2010

The distribution of required-move solutions is pretty interesting. Hits a peak at 18 and then drops off a cliff.

This is typical of the depth distributions for almost all twisty puzzles, and it's a consequence of the fact that there are relatively few move sequences of any given length that result in the identity permutation (meaning that the move sequence ultimately leaves the state of the cube unchanged). What that means, roughly, is that you get something like exponential growth in the number of available positions open after n twists, almost up until you've exhausted the entire set of positions. The 2x2x2 cube, the skewb, and the pyraminix all have had their depth-distribution tables worked out completely, and you'll see the same phenomenon.
posted by Wolfdog at 6:54 AM on August 9, 2010 [7 favorites]

When in high school I once solved it in 13 seconds, more by fluke of the mix than speed, although I had a lubricated the cube to reduce the friction.

After that I quit trying to improve. Nowadays I just solve it for fun (though always in far more than 20 moves).
posted by bwg at 6:59 AM on August 9, 2010

By the way, if you're tired of twisting your usual Rubik's cube, try the Little Chop. I found it very resistant to my usual techniques for developing a practical solving algorithm.
posted by Wolfdog at 7:03 AM on August 9, 2010

Oops, rats, wrong link; I meant the Little Chop.
posted by Wolfdog at 7:06 AM on August 9, 2010

I was picturing something more like the Slap Chop, which is admittedly more of a Gordian Knot-style method of solving the cube...
posted by Mr. Bad Example at 7:27 AM on August 9, 2010 [2 favorites]

This Guy: Actually it is pretty simple. (part 1, part 2)
posted by contessa at 7:28 AM on August 9, 2010 [1 favorite]

AskMe inspired me to learn to cube last summer, starting with the "beginner's method" and quickly moving on to F2L intuitive w/ a 4LLL... Enough to routinely solve any cube in about 50 seconds.

I see some people scoff at the idea of memorizing algorithms as opposed to solving the entire thing by one's own brute intelligence, but that doesn't happen any more. That was mostly the culture in the 80s when people were devising the best methods and swapping ideas via newsletters and whatnot. Occasionally you'll hear of a new method or move to solve the cube but pretty much the majority of solvers use the Fridrich Method or the simplified versions of it - the 4LLL is a simplified method of that. The entire method involves hundreds of algorithms, but there's also a middle ground of 53 most common algorithms. Even those have similar structure. I'd love to learn them, but keeping practice on 53 different patterns must be tough.

Why do I continuously solve one? For me, it's satisfying to turn chaos into order and see organized colored faces emerge in seconds. It's almost like magic, even after the thousandth time. For similar reasons, I enjoy Spider Solitaire, not for the challenge -I often cheat and un-do moves- but for the meditative act of organizing 52 cards in formations King through Ace. Larger cubes, v-cubes and minxes heighten that chaos-to-order paradigm, although I have found that too large of a puzzle breaks down that sense of an emerging transformation.

Anyway, this reminds me of my favorite story about speed-solving and algorithms:

I remember one really funny story that happened to me on a train when I commuted to college from my home town. A guy was sitting next to me playing with the cube. I asked him about his system. He said: "I am using the Fridrich method." I asked with a surprise in my voice: "You actually memorized ALL algorithms?" His answer was: "No, that's too much. I know only some of them." I replied with: "Well, you need to memorize all of them otherwise you are not really utilizing its strength." He looked at me frawning and said with his mouth half open: "Yeah, so what's your system?" I answered with a big smile: "I use the Fridrich method, too, because I am Fridrich." He did not blink an eye, did not say anything and handed me his messed-up cube. I solved the cube in about 20 seconds to prove my words and we both laughed at the coincidence.
posted by yeti at 7:35 AM on August 9, 2010 [9 favorites]

try the Little Chop

The helicopter cube has a similar diagonal movement and is the one puzzle I own that I haven't solved.
posted by yeti at 7:45 AM on August 9, 2010

It can be solved in six moves. Take a red marker and color one side. Take a yellow marker and color another side. Repeat for the remaining sides using blue, green, white and orange markers.
posted by dances_with_sneetches at 7:45 AM on August 9, 2010

Hell isn't burning sulphur and flaming pitchforks. It's not an endless black abyss. It's eternity trapped in a room with an unsolvable Rubik's cube.
posted by The Winsome Parker Lewis at 7:52 AM on August 9, 2010

Helicopter is not so bad! I made the high scores for both time and number of moves (though obviously that is because people haven't made that particular puzzle very competitive yet). I really really want a physical version of that one (and little chop, too). There's a guy that's made nice helicopter cubes and has been promising them for sale for some time now, but so far... only vapor.
posted by Wolfdog at 7:55 AM on August 9, 2010

Whee! I just found a helicopter cube on eBay.
posted by Wolfdog at 8:03 AM on August 9, 2010

awesome! it is done. I'm glad there is certainty about this.
posted by milestogo at 8:05 AM on August 9, 2010

Wolfdog, I got one through Mefferts which is now selling them through the Twisty Store.
posted by yeti at 8:08 AM on August 9, 2010

Now, even faster.
posted by applemeat at 8:19 AM on August 9, 2010

Yes, I'm pretty sure the one I just bought is ultimately from the same source. Meffert's store drives me up a wall with its nonorganization and "look at all these lovely puzzles! you want this one? haha! out of stock!" issues.
posted by Wolfdog at 8:20 AM on August 9, 2010

This is very timely because I just spent my weekend at the 2010 US Rubik's Cube National Championship. The number of very smart people who are totally obsessed with this puzzle is sort of astounding.

For me, the blindfold solving is the craziest thing. Oh, and the clever event t-shirts (that was from 2006 nationals, but they are equally, uh, witty every time).
posted by alphasunhat at 9:13 AM on August 9, 2010

When I was a kid I had a two-step process for solving my Rubik's Cube:
1. Take it apart.
2. Re-assemble it in the correct configuration.
posted by howling fantods at 9:22 AM on August 9, 2010

Yeah, I freaked my parents out really badly when I was about two by presenting them with a "solved" cube. I'd peeled off the stickers and replaced them, of course.
posted by Pope Guilty at 9:42 AM on August 9, 2010

Through some "random permutation" algorithm I accidentally solved a friend's cube back in the days before the Rubik's Cube knock-off brought them to a price I could afford on my paper route salary. When asked to do it again I declined on the premise that the puzzle bored me. Which is to say, I lied through my teeth.

From the time I could afford my own and work it in private, I have never repeated that feat--not that I've tried in the past several decades. Come to find out there are algorithms and strats to the whole thing. Kind of de-mystifies the whole puzzle in my mind.
posted by Fezboy! at 9:51 AM on August 9, 2010

alphasunhat: That shirt is indeed dreadful, but the logo of a Rubik's cube on an anvil is pretty good.

I haven't ever studied how to solve a cube, nor am I particularly familiar with the mathematical side of it (though I do know that if you take apart a cube and put it back together there are 12 distinct ways you can do it that you can't change between without taking it back apart again). Does anyone know if it's just coincidence that 20 is also the number of movable pieces in a Rubik's cube? (3x3x3, minus the core*, and minus the 6 fixed centers of each face)

* It's pretty much universally accepted (except for the occasional crackpot) that Rubik's cubes have a core of superdense superheated molten plastic, upon which the plates on the surface are able to smoothly glide.
posted by aubilenon at 9:57 AM on August 9, 2010

Now how many positions are there to solve for in the 4-D Cube? That's right... RUBIK'S TESSERACT.
posted by FatherDagon at 10:10 AM on August 9, 2010

Does anyone know if it's just coincidence that 20 is also the number of movable pieces in a Rubik's cube?
That is just a coincidence.
posted by Wolfdog at 10:12 AM on August 9, 2010

I flew to Minneapolis in July and brought along in my carry-on my teraminx to solve for the first time. The TSA looked at the x-ray quizzically and separated me for a closer inspection before being allowed to pass.

On my flight back, I took it out of my bag as I would a laptop. A TSA agent saw it and cheerfully walked over to ask what in the world it was. Don't say terror-minx. Don't say terror-minx, I thought to myself, as I replied:

"TERROR-MINX! I mean ummm uhhh ter-a-minx. Like a rubik's cube only bigger."
posted by yeti at 11:23 AM on August 9, 2010 [1 favorite]

I used to bust 'em apart and put 'em back together right. No algorithms needed.
posted by Xoebe at 11:24 AM on August 9, 2010

I don't know if they have video available, but the Rubik's cube US Nationals just happened here in Cambridge.

I'm kind of amazed that one of the 2x2 speed solvers is actually notably faster than the others.
posted by nat at 11:28 AM on August 9, 2010

Correction: There are no coincidences.
posted by kaibutsu at 12:12 PM on August 9, 2010

aubilenon: I've never been good at math but aren't there 26 movable pieces? 3x3x3-1 isn't 20.
posted by The Winsome Parker Lewis at 3:18 PM on August 9, 2010

it's a consequence of the fact that there are relatively few move sequences of any given length that result in the identity permutation (meaning that the move sequence ultimately leaves the state of the cube unchanged)

Thanks for the explanation, fascinating stuff.
posted by Blazecock Pileon at 3:46 PM on August 9, 2010

I've never been good at math but aren't there 26 movable pieces? 3x3x3-1 isn't 20

There is an un-moveable piece on every face -- the center square, all it does is rotate around. So 3*3*3 - 1(core) - 6(center tiles).

It makes more sense If you take it apart. You'll have 8 corner pieces (3 faces) and 12 edge pieces (2 faces) and a structure 3d frame that looks like this.
posted by cj_ at 9:33 PM on August 9, 2010

Why do I continuously solve one? For me, it's satisfying to turn chaos into order and see organized colored faces emerge in seconds.

Yeah, I feel the same way. Solving them is very relaxing and stress-relieving. Sadly, you have to keep doing it or even the most simple algorithms fall right out of your head, or at least they do for me. I've relearned the basic method 3 different times, and more advanced ones the first time when I discovered you could even do so, with this book (Rubik's Cubic Compendium (Recreations in Mathematics)) by Ernö Rubik and a few other mathematicians. It's a great read that describes the mathematical theory/implications along with the solutions, though I have no doubt it's way out of date now as far as optimal solutions go.
posted by cj_ at 9:41 PM on August 9, 2010

but it would take a good desktop PC (Intel Nehalem, four-core, 2.8GHz) 1.1 billion seconds, or about 35 CPU years, to perform this calculation.

How much is that in BTUs?
posted by neuron at 10:02 PM on August 9, 2010

As much as if you'd burned 3,141,592 Libraries of Congress.
posted by obiwanwasabi at 2:45 AM on August 10, 2010

I used to bust 'em apart and put 'em back together right. No algorithms needed.
posted by Xoebe

I redefine the puzzle so that the desired end-state is the state it happens to be in at the moment. Problem solved in 0 moves.
posted by vacapinta at 4:20 AM on August 10, 2010 [2 favorites]

I got my helicopter cube! It's really well made, too.
posted by Wolfdog at 2:46 AM on August 14, 2010