Every position of Rubik's Cube can be solved in twenty moves or less

by selmnoo • 13 years ago

177 35 13 years ago

mumbi• 13 years ago

Very cool. I'm still amazed by people who try to solve Rubik's Cubes with the least moves possible. Unfortunately it seems the speed solvers get all the glory, though.

Stats: http://www.worldcubeassociation.org/results/e.php?i=333fm

laureny• 13 years ago

Right, there is some tension between the number of moves and speed. Having only 20 moves to solve the cube sounds like a great idea except that the calculations to find out these 20 moves take too long.

Speed cubists win despite having to make more moves because calculating these moves can be done very efficiently (and almost instantaneously) by our brains.

selmnoo3• 13 years ago

If more people, like me, don't have java plugins, here's a cool video about the 'superflip' to make up for the site-animation not loading: http://www.youtube.com/watch?v=BTyzE-NDga8

dopamean2• 13 years ago

That is very cool. I've never solved a Rubik's Cube (though I've never tried particularly hard) and this is making me feel stupid.

selmnoo3• 13 years ago

Don't let it make you feel stupid -- once you get the hang of an "algo" it's actually quite easy.

Approach it very methodically. Learn the algos. Practise. And that's really all. Here're two videos to get started: http://www.youtube.com/watch?v=mvhKNXHQqyM - http://www.youtube.com/watch?v=MaltgJGz-dU

Give yourself about 20 hours to learn and play around, by then you'll have gotten the hang of it and will probably be able to solve most arrangements with ease.

candydance• 13 years ago

It is much easier than you might imagine but it's not very "fun". To be able to dependably solve a cube you'll need to know a few algorithms for swapping key pieces around without effecting the rest of the cube. If you can remember those algorithms then you can solve any cube.

http://www.wikihow.com/Solve-a-Rubik%27s-Cube-%28Easy-Move-N...

grecy• 13 years ago

As others have said, it's not particularly hard. Just practice and memorization.

A few years ago I was determined to learn for some odd reason. From watching videos like those linked, I took a week of 2-3 hours after work to be able to reliably solve a cube using one popular simple method.

Now I seem to be able to get close, but can't remember the last couple of steps. Meh.

hkarthik• 13 years ago

If you're interested in learning to solve it, I highly recommend this talk: http://confreaks.com/videos/2670-gogaruco2013-solving-the-ru...

The accompanying Ruby Gem is pretty useful for learning the two-cycle solution (only requires memorizing 4 algorithms)

https://github.com/chrishunt/rubiks-cube

thearn42• 13 years ago

I know Morley Davidson, one of the mathematicians who worked this out. Well, I took seminars with him while working on my PhD at least.

His office is full of puzzle cubes. Now that I've got my own office, so is mine. They're kind of addicting.

jevinskie• 13 years ago

Do you solve them or just collect them?

thearn42• 13 years ago

Both. The higher order cubes aren't as hard as they might seem. Most strategies degenerate towards knowing how to solve the 3x3x3 case.

b0z0• 13 years ago

I was looking forward to a mathematical proof of how symmetrical cases can be solved, but I was surprised to find that they basically brute-forced it with a computer. I'd learned about how much controversy that approach generated with the Four Color Theorem, but I'm impressed with how much proofs have moved forward since then.

gamegoblin2• 13 years ago

There are mathematical proofs which can get the bound to 22 moves, so it's just a matter of time. But now that the proof is bruteforced, there isn't too much motivation.

http://en.wikipedia.org/wiki/Optimal_solutions_for_Rubik%27s...

trothamel• 13 years ago

An interesting thing about this is how Google donated years of CPU time to this project. It makes you wonder what else Google is using otherwise-unused CPU time for.

frostnovazzz3• 13 years ago

Years of CPU time is not a lot in google. You only need hundreds of CPUs to run for a couple of days.

Though not everyone has easy access to this resource, this project is meaningful enough to get approved for the resource allocation.

PilateDeGuerre• 13 years ago

This seems to be first rate academic wankery to me. If I am missing someething, please share with me what qualifies this project as "meaningful enough" in your view.

cecilpl• 13 years ago

Did you just learn this from the reddit ELI5 on Rubik's Cubes this morning? :)

gamegoblin2• 13 years ago

There was also a TIL post about it (presumably from someone who read the ELI5).

Zombieball• 13 years ago

Don't worry, OP will surely reply.

selmnoo3• 13 years ago

I saw something about Rubik's cube on Reddit, but I didn't click the link or the comments on Reddit. Later in the day a question popped into my head: do there exist known states that are very random, very 'distant' from a solved state, such that I could keep my Rubik's cube master friend busy for a good while? I googled around, found my way here: http://math.stackexchange.com/questions/150895/is-there-a-mo... -- and there I found the 'God's Number is 20' link (which I've submitted here, because I found it very interesting and thought you guys would too).

There. Happy?

codezero• 13 years ago

Why is the count of solutions for distance 19 and 20 lower than for 17 and 18?

alasano• 13 years ago

I was asking myself the same thing.. intuitively I feel like it's right but I'm no expert.

shalmanese• 13 years ago

An intuitive way of thinking about it is that if you have an arrangement with distance 20, any move you make is going to make it distance 19. Since there are 12 possible moves, every distance 20 arrangement has 12 distance 19 neighbors.

Someone2• 13 years ago

That logic has a flaw: for every 'distance 19' arrangement you find that way, there may be more than one 'distance 20' arrangement one can reach from it in one move.

For example, you have two parents, but that does not imply that, combined, you and all your siblings have more parents than there are in that group of siblings.

vbuterin• 13 years ago

Same reason why, given a point on a 100-dimensional cube, the number of points x steps away from that point starts decreasing for x > 50.

jorgem• 13 years ago

"Source Released".

Good scientist.

frostnovazzz3• 13 years ago

This is old news.

cranefly• 13 years ago

Well it's news to me!

haberman• 13 years ago

Wow, the code is written in CWEB, a literate programming system. You don't see that every day. The PDFs of the code are, from my brief scan over them, a really well-presented explanation of some seriously deep/mathematical code.

When I heard that the solution came from using 52 CPU-years of processing, I guessed that the code was a relatively boring brute-force search. But it appears I couldn't have been more wrong about that.

Every position of Rubik's Cube can be solved in twenty moves or less

Related Stories