News for hackers. Stuff that matters.
Re:Every position of Rubik's Cube can be solved in twenty mo... by haberman on Saturday October 19, 2013 @03:18AM (#6575658)
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.

Re:Every position of Rubik's Cube can be solved in twenty mo... by selmnoo on Friday October 18, 2013 @07:47PM (#6574676)
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
Re:Every position of Rubik's Cube can be solved in twenty mo... by dopamean on Saturday October 19, 2013 @12:05AM (#6575290)
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.
Re:Every position of Rubik's Cube can be solved in twenty mo... by selmnoo on Saturday October 19, 2013 @12:12AM (#6575301)
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.

Re:Every position of Rubik's Cube can be solved in twenty mo... by Someone on Saturday October 19, 2013 @04:25AM (#6575773)
NO! Solving the cube is boring, discovering how to solve it is not. The journey is the reward. What you should do is learn a tiny bit of algebra. In particular, learn about commutators (http://en.wikipedia.org/wiki/Commutator)

Then, experiment with commutators on the cube to look for ones that have very localized effects. Those are those 'algos' others want you to learn from a book. For example, check the simplest commutator LTL'T' and figure out how to use that as part of a larger commutator that permutes the three corners of a cube.

Yes, it will probably take more than those 20 hours (that can be done faster, I think. You need at most 4 tricks (permute three corners, permute three edges, flip two corners, flip two edges should do), each maybe ten turns to solve any cube), but it will be more fun.

It took me way more than 20 hours to solve my first cube, but the first two times I did it, I didn't even know how to solve it yet.

Re:Every position of Rubik's Cube can be solved in twenty mo... by aidos on Saturday October 19, 2013 @05:12AM (#6575854)
Couldn't agree with this more. It took me a year of chipping away at it to come up with a solution. Finally finished it the first time while my flight was touching down in thailand.

I've heard mine is not the normal algorithm people are taught. The one I use is totally suboptimal - but that's a wonderful thing. There's forever more to discover. It's actually a brilliant problem for the types of people that haunt HN. I implore those of you who have never tried to give it a shot. And remember, if you look online, you're only cheating yourself.

Re:Every position of Rubik's Cube can be solved in twenty mo... by dopamean on Monday October 21, 2013 @03:52PM (#6587794)
Thanks for the suggestion!
Re:Every position of Rubik's Cube can be solved in twenty mo... by grecy on Saturday October 19, 2013 @01:10AM (#6575429)
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.

Re:Every position of Rubik's Cube can be solved in twenty mo... by hkarthik on Saturday October 19, 2013 @10:51AM (#6576582)
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

Re:Every position of Rubik's Cube can be solved in twenty mo... by candydance on Saturday October 19, 2013 @12:23AM (#6575330)
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...

Re:Every position of Rubik's Cube can be solved in twenty mo... by trothamel on Friday October 18, 2013 @09:03PM (#6574899)
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.
Re:Every position of Rubik's Cube can be solved in twenty mo... by frostnovazzz on Saturday October 19, 2013 @01:32AM (#6575471)
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.

Re:Every position of Rubik's Cube can be solved in twenty mo... by PilateDeGuerre on Saturday October 19, 2013 @02:59PM (#6577388)
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.
Re:Every position of Rubik's Cube can be solved in twenty mo... by frostnovazzz on Sunday October 20, 2013 @11:18AM (#6580141)
At least there are a countless number of people who want to know the answer.
Re:Every position of Rubik's Cube can be solved in twenty mo... by thearn4 on Friday October 18, 2013 @08:22PM (#6574785)
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.

Re:Every position of Rubik's Cube can be solved in twenty mo... by jevinskie on Friday October 18, 2013 @09:11PM (#6574923)
Do you solve them or just collect them?
Re:Every position of Rubik's Cube can be solved in twenty mo... by thearn4 on Friday October 18, 2013 @10:01PM (#6575047)
Both. The higher order cubes aren't as hard as they might seem. Most strategies degenerate towards knowing how to solve the 3x3x3 case.
Re:Every position of Rubik's Cube can be solved in twenty mo... by VladRussian2 on Saturday October 19, 2013 @01:19PM (#6577057)
How about 3x3x3x3 cube?
Re:Every position of Rubik's Cube can be solved in twenty mo... by rmidthun on Saturday October 19, 2013 @11:50PM (#6578869)
Ok, how about it? http://www.superliminal.com/cube/cube.htm

There's also a 5 dimensional one and links to all kinds of crazy.

Interestingly, solving higher dimensional cubes isn't more difficult from an algorithm view. Understanding what you're looking at might be a different story!

There used to be a solution online called the "Ultimate solution", the web page I got it from is now sadly defunct. It showed you how to solve the cube with only two moves. The first was a simple commutator, of form FRF'R' and showed how you can use just this one move to get all the edges in place.

If you then place two of these moves together with a similar structure, you get a move that cycles corners. This is of the form (X)U(X')U', where X is an edge commutator like FRF' (example (FRF')D(F'R'F)D'). This one move properly applied will move 3 corners without disrupting edges.

So, the trick to the fourth dimension is to learn a move on the order (C)W(C')W', where C is the inner part (no final move) of the corner commuter above. And so it goes, each dimension only requiring one more move in the same fashion.

Of course, figuring out exactly how to make that move with the interface is the hard part. And the fun.

Re:Every position of Rubik's Cube can be solved in twenty mo... by b0z0 on Friday October 18, 2013 @08:49PM (#6574868)
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.
Re:Every position of Rubik's Cube can be solved in twenty mo... by gamegoblin on Friday October 18, 2013 @11:00PM (#6575157)
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...

Re:Every position of Rubik's Cube can be solved in twenty mo... by jorgem on Saturday October 19, 2013 @01:21AM (#6575454)
"Source Released".

Good scientist.

Re:Every position of Rubik's Cube can be solved in twenty mo... by cecilpl on Friday October 18, 2013 @09:41PM (#6574992)
Did you just learn this from the reddit ELI5 on Rubik's Cubes this morning? :)
Re:Every position of Rubik's Cube can be solved in twenty mo... by gamegoblin on Friday October 18, 2013 @10:59PM (#6575154)
There was also a TIL post about it (presumably from someone who read the ELI5).
Re:Every position of Rubik's Cube can be solved in twenty mo... by Zombieball on Friday October 18, 2013 @11:29PM (#6575211)
Don't worry, OP will surely reply.
Re:Every position of Rubik's Cube can be solved in twenty mo... by selmnoo on Saturday October 19, 2013 @12:02AM (#6575283)
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?

Re:Every position of Rubik's Cube can be solved in twenty mo... by codezero on Saturday October 19, 2013 @12:25AM (#6575333)
Why is the count of solutions for distance 19 and 20 lower than for 17 and 18?
Re:Every position of Rubik's Cube can be solved in twenty mo... by alasano on Saturday October 19, 2013 @12:41AM (#6575361)
I was asking myself the same thing.. intuitively I feel like it's right but I'm no expert.
Re:Every position of Rubik's Cube can be solved in twenty mo... by shalmanese on Saturday October 19, 2013 @03:21AM (#6575661)
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.
Re:Every position of Rubik's Cube can be solved in twenty mo... by Someone on Saturday October 19, 2013 @10:33AM (#6576519)
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.

Re:Every position of Rubik's Cube can be solved in twenty mo... by vbuterin on Saturday October 19, 2013 @06:11AM (#6575936)
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.
Re:Every position of Rubik's Cube can be solved in twenty mo... by mumbi on Friday October 18, 2013 @07:32PM (#6574628)
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

Re:Every position of Rubik's Cube can be solved in twenty mo... by laureny on Friday October 18, 2013 @08:26PM (#6574798)
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.

Re:Every position of Rubik's Cube can be solved in twenty mo... by frostnovazzz on Saturday October 19, 2013 @01:28AM (#6575467)
This is old news.
Re:Every position of Rubik's Cube can be solved in twenty mo... by cranefly on Saturday October 19, 2013 @03:20AM (#6575659)
Well it's news to me!