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."

Re:1.6ghz?

[RabidJackal]

Speaking from personal experience, a Q6600 at 100% load on all four cores gets incredibly hot, even with a good cooler. Perhaps he did not wish to risk overheating at the expense of his experiment?

Then again, it could just be an error in the article.

I still beat him!

[holywarrior21c]

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.

Computational proofs

[timeOday]

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!

Distributed computing

[Anonymous Coward]

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?

Re:Which 25 moves?

[Brian Gordon]

Building the rainbow tables would be insane. And no need to hash; that would take extra time and use a non-efficient amount of key space. Just search by the configuration of the cube.

Re:1.6ghz?

[Anonymous Coward]

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.

Re:Computational proofs

[Sage Gaspar]

As far as I know the first "big" computational proof (which another poster alluded to) is the Four Color Theorem. It was initially met with some distrust but it's pretty widely accepted now, and there are people that worked after the original proof to cut down the amount of computer verification needed from a couple thousand to a couple hundred I think.

I would guess that it is more common in fields like graph theory and other discrete math just because obviously the discrete lends itself well to computers, and many times it's not hard to whittle it down to a finite number of cases to check. The objects of study also tend to admit matrix representations and other things computers are good at working with. Even before computers you'd cut things into lots of cases that you needed to verify but now it's easier to handle proofs that need larger number of cases.

I've actually seen some really interesting proofs using computers to check things over continuous domains. The basic idea lots of times is if you can check things over a fine enough "net" of cases in some space and you can prove that the variance between each of these points is small enough, then you can cover your entire space by just checking a finite number of cases.

Given all this people still have a healthy amount of skepticism for computer aided proofs and would rather not if possible in most cases, especially when you're talking about billions of cases. Then again what is the potential for errors in a computer checking billions of cases based on a relatively small amount of code versus some of these enormous human-created decades-long behemoth [wikipedia.org] proofs?

Re:Wow, it really works

[JonathanR]

Interesting point. Should a solved cube be a member of the set of all starting points, and also would it also be a member of the set of essentially similar ones?

Re:Theory versus practice

[seanadams.com]

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...

Proving that ALL cubes can be solved in 25 moves is not the same as solving A cube in 25 moves. I'd imagine if he can crunch the entire problem space of 400 billion configurations in 1500 hours, he can solve a single cube pretty damn quick.

"God's Algorithm"

[wickerprints]

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.

Re:You only need one

[tlhIngan]

It's much easier to pull the stickers off. Though less fun I suppose.

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.

So the comic was right!!

[Spy der Mann]

http://truckbearingkibble.com/comic/2008/03/10/eureka%C2%B3/ [truckbearingkibble.com]

Solve This!

[kramulous]

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 [youtube.com]. Hold your breath for that solution.

Re:"God's Algorithm"

[insecuritiez]

Most every cuber believes the limit _is_ 20. There is only one known permutation that requires 20 moves and it is called the "super flip". In it, every edge and corner piece are in their correct positions but all the faces have the opposite orientation. It makes for a nice checkered pattern. It is the symmetry of the scramble and the lack of known permutations "harder" than the super flip that lend a strong argument to 20 being the max.

Re:Which 25 moves?

[Anonymous Coward]

In fact, it is pretty likely every cube can be solved in as few as 21 moves (or less),
as someone (Dik Winter) has already written a program that does just that.
Source: http://mathworld.wolfram.com/RubiksCube.html [wolfram.com]

"may be non-intuitive"

[Joce640k]

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.

Re:"God's Algorithm"

[Anonymous Coward]

> There is only one known permutation that requires 20 moves and it is called the "super flip".

That's not correct, there are a lot of such positions found. Superflip is perhaps the most well known, but certainly not the only one.

Re:Wow, it really works

[The Clockwork Troll]

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.

Re:Wow, it really works

[Chris Mattern]

What's really amusing is that you can take a Rubik's Cube apart and reassemble it so it *can't* be solved. Possibility for hours of fun here...

Re:Wow, it really works

[tomhudson]

That rather depends on your intuition. I personally would intuit an upper bound of (3^9)/2 which would be further reduced by the fact that abs(n(o) - n(x)) <= 1 where n represents the number of each marker on the board.

No intuition. My numbers are based on a program I wrote a decade ago that generated all possible solutions. It generated static html pages such that you chose to go first or second, and you'd click on the square, and it would load the appropriate next page. 2000 pages to cover every possibility where it won, or, if not a win, then a draw. It never lost :-)

Taking into account mirrors and rotations, another program got it down to under 500, iirc. (it may have been slightly over - can't recall for sure).

It was really neat - a tic-tac-toe-playing set of web pages with no javascript, no programming on the server or the client - just 2,000 static pages.