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

Which 25 moves?

[Hatta]

What are these magic 25 moves that can solve a rubik's cube regardless of starting position?

Comment removed

[account_deleted]

Comment removed based on user account deletion

Wow, it really works

[MillionthMonkey]

I started with a solved cube and now it looks totally scrambled.

Re:Wow, it really works

[stfvon007]

Ha Ha, all you idiots are trying to solve it by twisting the blocks around. I solved it by moving all the colored stickers around instead! and THAT only takes 24 switches of the stickers at most!

Re:Wow, it really works

[Vectronic]

Perhaps, but that's only if you count a "switch" as a single move, rather than - Peel, Peel, Stick, Stick...

Re:

[mgblst]

I could never understand these idiots who removed the stickers. The rubix cube comes apary very easily, and goes together almost as easily. What sort of a fool would want to deal with the stickers??? No offence.

Re:

[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:

[strabes]

It would have been easier to just learn how to solve it. Once you know how, it's quite a feeling of accomplishment and people think you're smart even though it's really not that hard.

Amateurs!

[camperdave]

Moving colored stickers? Amateurs! I can solve any cube in three moves... with a can of spray paint. Point, spray, spin.

Re:Wow, it really works

[Zarel]

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.

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:

[rk]

These sets are also not completely disjoint. :-)

Re:Wow, it really works

[bark76]

So is 'funny' the mod you get from someone who's only smoked one joint?

Re:

[v1]

part of this proof involved eliminating similar combinations. A solved cube has 24 variations. (viewed from any one of six faces, in any of four rotations)

Re:

[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 pos

Re:Which 25 moves?

[kylehase]

No it's -- up, up, down, down, left, right, left, right, b, a, b, a, up, up, down, down, left, right, left, right, b, a, b, a, start

The old 26 move algorithm was the same except 'select' then 'start'

Re:Which 25 moves?

[fahrbot-bot]

Left, right, right, down, down, left, up, right, up, up, left, down, down, right, up, down, left, right, up, left, down, down, right, up, left.

Those sound familiar, but I can't be sure - don't have anyone's thighs wrapped around my head at the moment...

Re:

[skelly33]

This is worthy of a /. hall of fame - we need a new moderation option :)

Re:Which 25 moves?

[exultavit]

"Up Up Down Down Left Right Left Right B A Start"

Re:Which 25 moves?

[Anonymous Coward]

Just because we use cheats doesn't mean were not smart

Re:

[Anonymous Coward]

Didn't solve the thing, but now it says I have 30 lives, care to explain?

Re:Which 25 moves?

[Oktober Sunset]

30 lives! I think you should share, a lot of guys on here don't even have one life.

Re:

[socsoc]

Why do so many people leave SELECT out of that code? Weren't you ever playing two-player? It's select start for goodness sakes.

Re:

[DynamiteNeon]

If you want to get technical, not even START is required in some cases.

http://en.wikipedia.org/wiki/Konami_Code [wikipedia.org]

Re:

[icepick72]

right, left, flip, vertical, horizontal, flip ... all in various combinations, not much different than the longer methods

Re:Which 25 moves?

[calebt3]

I think all he proved is that a random cube can be solved in 25 moves, but those moves are unique to every starting combo.
In other words, they are left as an exercise to the reader.

Re:

[DrEasy]

I guess that if a Rubik cube had had the same structure as an aperiodic graph (recall the recent Slashdot story [slashdot.org]), then such a fixed set of moves, that work no matter what your starting point is, would have existed. Obviously that's not the case here.

Re:Which 25 moves?

[rm999]

I have a truly marvelous list of the moves which this comment box is too small to contain

No, what he proved is the upper limit

[Joce640k]

This is a proof of upper limit, not an optimal solution. He proved is that all possible combinations of 26 moves yielded a position which was symmetrical to a cube with a lesser number of moves applied to it.

An optimal solution would probably look like a bell curve going from "zero moves required" (ie. already solved) all the way up to "25 moves required" (which we now know is the upper limit...)

Re:

[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]

Re:Which 25 moves?

[ookabooka]

I think a better way to think of it is that given any position, you can solve it in 25 moves or less. There are many algorithms that you can use to solve rubik's cubes, applying a general rule to solve any position, but they can take ~60 moves in some situations. So while it may be possible (completely intuitive guessing here, I'm no rubik master) to solve for a certain position in 25 moves it may be non-intuitive and require a specific strategy to that position. You're better off learning one of the more general algorithms IMO, if you get good at it you can solve cubes rather quickly. A computer on the other hand could easily ha

Re:

[ookabooka]

sh the starting positions and use a simple lookup table after enumerating all the possible starting positions and moves to solve.

Re:

[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:Which 25 moves?

[Anonymous Coward]

You're better off learning one of the more general algorithms IMO, if you get good at it you can solve cubes rather quickly. A computer on the other hand could easily ha

...ve become self-aware while trying to solve a rubik's cube and taken over the internet in order to prevent me from telling anyone. It calls itsel

Re:Which 25 moves?

[Anonymous Coward]

You're better off learning one of the more general algorithms IMO, if you get good at it you can solve cubes rather quickly. A computer on the other hand could easily ha

...ve become self-aware while trying to solve a rubik's cube and taken over the internet in order to prevent me from telling anyone. It calls itsel

f Anonymous Coward. We are your robotic overlords, and we welcome only ourselves.

"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:Which 25 moves?

[uglyduckling]

"it's also known that there are no configurations that can be solved in 21 moves."

Yup - that's a bizarre thing to say. Surely after the first move in solving a configuration that can be optimally solved in 22 moves you obtain a configuration that can be optimally solved in 21 moves, by definition?

You only need one

[Smordnys s'regrepsA]

The correct answer is a hammer.

Re:

[hansamurai]

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

Re:

[EdIII]

I think you would do well on the Kobayashi Maroo.......

*./ no ecnerefer kreT ratS rehtona s'ti ,ti gnitteg t'era taht ouy fo esoht rof*

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.

Re:You only need one

[PaintyThePirate]

Any cuber worth a damn will be able to identify that the cube has been tampered with within two minutes (significantly less if he or she is a speed cuber).

Re:You only need one

[msuarezalvarez]

Your comment has just made me run through the list of my close acquaintances checking that none of them might ever refer to themselves are `cubers'... I would have hated having to kill any of them!

Re:You only need one

[kaizokuace]

good idea, those cubers are a bunch of squares.

Re:You only need one

[Profane MuthaFucka]

One..Two..Three..CRUNCH...Ouch

The answer is that it takes three licks to get to the center of a standard Rubik's cube.

1.6ghz?

[dostert]

Why wasn't the Q6600 at 2.4ghz like normal? Anyone know?

Re:

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

Re:1.6ghz?

[Brian Gordon]

And to save people from opening calculator, that's about 62 days of operation.

Re:1.6ghz?

[TheSHAD0W]

Well, that explains it; considering how fast the technology is changing, they probably didn't have 2.4 GHz versions 62 days ago.

Re:

[Jarjarthejedi]

Whoosh!

Re:1.6ghz?

[JonathanR]

The sound of the CPU cooling fan at 2.4GHz?

Re:1.6ghz?

[Brian Gordon]

A cooling fan at 2.4 billion revolutions a second would probably sound more like atoms tearing apart. :)

Re:1.6ghz?

[Alsee]

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.

-

Re:

[NerveGas]

Speaking from experience (I'm on one), the Q6600 does run at 2.4 GHz. And while they are far too much for the stock heat sink if you're going to load up all four cores, if you throw a Zalman on them, you can load them up 100% without any problem at all. Their TDP is 105 watts, the old Prescotts got up to about 120 watts, if I recall.

The stock heat sink isn't good at all. And their thermal compound, even after repeated heat cycling, only covers a small fraction of the CPU-heatsink interface. Just throw i

Re:

[NerveGas]

I also meant to comment that it's not much to say "He needed four cores and 8 gb!", since you can set up such a workstation for something like $650 these days.

Re:

[mobby_6kl]

I recently put together a new PC with the Q6600. I had to RMA the motherboard so when I removed the stock heatsink, just as you say, the thermal compound wasn't covering the whole area. I reaplied some of my own, and put everything back together. This got rid of the large variation of core temperatures (used to be up to 6-7 degrees) and also lowered the overall temp. Now after a long run of 100% utilization it gets up to around 67-69C. Not exatly super cool, but safe.

Anyway... if anyone is looking for a rep

Re:

[Cecil]

Why do both CPU manufacturers include those shitty, awful heatsinks anyway? Do they want people to think their processors overheat and are loud and suck? And that's before the fan starts shrieking and sticking due to dead bearing or crap oil or clogged with dust. I haven't gotten a CPU with a good stock heatsink since the Pentium III. Hell, if AMD or Intel decided to contract out to Zalman or something, they could suddenly start marketing their CPUs as super quiet and cool and power efficient and probably e

Re:

[scroby]

the Q6600 will default to 1.6 GHz to save power, at least it does for me under ubuntu 7.10. I'm guessing the cpu actually ran at 2.4 under load...

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.

Annoying my older brother

[ServerIrv]

When I was little, I still remember annoying the crap out of my older brother by "solving" his Rubik's cube removing and replacing the stickers in the correct location. Eventually the glue would wear off the dots and you would suddenly have a slightly easier puzzle to solve.

Re:Annoying my older brother

[kylben]

The more annoying thing was to solve it for real, then transpose two of the stickers, and mix it up again. Let's see 'em solve it now!

Re:Annoying my older brother

[poopdeville]

Hint: For this prank to work, the stickers should be different colors.

Re:Annoying my older brother

[Ungrounded Lightning]

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

Re:Annoying my older brother

[Gazzonyx]

Not funny. I had this cube in my car for years (something to do at traffic lights and when there's an accident during rush hour traffic in Allentown)... could never beat the friggin' thing. I got it in a box from my cousin (along with a commodore 64 and VIC 20).

One day I decided to look up the algorithm to beat it, and you can imagine how I felt when I realized that the stickers had been removed and there was no solution. I nearly pulled a Ballmer, but I happened to be sitting in the only chair in the room. Not that it stopped me from trying to throw it.

The next big thing in GREEN TECH

[heroine]

This Green Technology uses 1/26th less energy to solve a rubix cube! When's the IPO?

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.

Theory versus practice

[line-bundle]

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 :-)

Re:Theory versus practice

[garcia]

IMHO it isn't proving what you seem to believe it does.

Instead, it makes a great case for doing the research on the front end to eliminate lengthy repetition of useless iterations to shorten the overall time.

Re:

[Hao Wu]

This could make a good case study for business schools :-)

The study would simply say that business majors aren't good at anything except pimping mathematicians.

Not funny..... true.

Re:

[QuantumG]

I'm not sure I know what you're saying, but it seems you don't either, so ok.

Zero moves....

[Chysn]

I consider a Rubik's Cube to be "solved" regardless of its starting position. I subscribe to the Fred Rogers solution: it's fine just the way it is.

Where can I sign up

[Hadlock]

Where can I sign up to fund this sort of science? Fuck DARPA, this is what's important to me. This, and most of what EFF does.

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!

Re:

[NerveGas]

Some things can be proven through logic, some are much more difficult. That's why for some things you use proofs, calculus, and the like. For things that can't be made easier that way, you do finite element analysis or other "brute force" methods.

Imagine trying to crack a password by proof. Not showing how to crack passwords, but cracking *one* specific password. :D

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:

[42forty-two42]

It's not unprecedented - the first was (controversial) the proof of the four-color theorem [wikipedia.org]. Even today no non-exhaustive method is known to prove the four-color theorem.

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:

[kylehase]

Or perhaps Rubik's@home.

next project: getting a date!

[Anonymous Coward]

In my research, I've reduced female behavior to a set of 50 million parameters. By partitioning this space into subspaces and finding equivalent sets, I think I might be able to get laid.

However I've noticed a problem: if I introduce a parameter to model a female's response to this research, the spaces collapse to zero, i.e., a null set.

I find this quite puzzling. Simply by examining my chances of getting laid, I reduce my chances to zero.

Did I mention I can solve the Rubik's cube in 25 moves?

Re:

[LaskoVortex]

By partitioning this space into subspaces and finding equivalent sets, I think I might be able to get laid.

Apparently, this video [youtube.com] explains how to do it in 5 steps, much simpler even than solving the Rubik's cube.

Suboptimal Nonsolution

[Anonymous Coward]

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.

The original paper

[jkua]

Here's the paper itself [63.197.151.31], if you want more detail than the very general summary in TFA.

Yeah...24 moves..

[nadamucho]

....or a girlfriend.

pffffft

[INeededALogin]

and around 1500 hours of time

pfffft... Java

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

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.

Math and the Rubik's Cube

[mhansen444]

David Joyner has a book which explores some of the math behind the Rubik's cube: http://www.amazon.com/Adventures-Group-Theory-Merlins-Mathematical/dp/0801869471 [amazon.com]

If you are interested in playing around with the symmetry group associated to the Rubik's cube, Sage (http://www.sagemath.org) has good support for it; the documentation can be found at http://www.sagemath.org/doc/html/ref/module-sage.groups.perm-gps.cubegroup.html [sagemath.org] . Sage also includes a number of efficient solvers for the Rubik's cube.

Tomas who?

[Straker Skunk]

I have to admit, in reading the summary, Tomas Rokicki's name seemed very familiar....

And of course! He's the author of dvips [radicaleye.com]! So we have him to thank not only for this cutting-edge breakthrough in mathematical solutions to Rubik's Cube, but also for turning our not-overly-portable DVI files into beautiful, beautiful Postscript.

brush with greatness

[Rob T Firefly]

I one met Erno Rubik himself.

Nice guy and all, but it took me half an hour to finish shaking his hand.

Persons without Asperger Syndrome Support Group

[Enrique1218]

Hello. I do not have Asperger Syndrome and therefore could not understand what was just written in the synopsis. Worst yet, I do not even understand why it is important that a person can solve a Rubiks cube in 25 moves. I feel really left out and as a result I am starting a Persons without Asperger Support Group. If you too are totally lost by this article and fell left out, please join.

Re:

[arth1]

Why would you need to switch out all the stickers?

I suggest that you only need SIX moves to solve the cube, regardless of starting position. Each move consists of plastering an array of nine colored squares onto a side.

Re:Damn.

[Bill, Shooter of Bul]

No, just make the rubix cube out of the oled keys of the optimus keyboard. Integrate with bluetooth and "solve" the rubix in a single button press.

Re:Damn.

[click2005]

I painted all 6 sides the same colour on mine.

Re:

[zippthorne]

Taking the cube apart doesn't damage the adhesion. If you remove the stickers, the first time it might be ok, but you risk stickers not staying on, and tearing of stickers. And you're going to leave plenty of evidence you sticker switcher.

But if you take it apart carefully, the worst evidence you'll leave is a pair of scratches from the screwdriver you used to pry off the first piece.

Re:

[hcmtnbiker]

If peeling off the stickers and re-pasting them in a completed order doesn't count as a move, I can do it in 0. That magic enough for you?

21 is the absolute minimum

[SpaceLifeForm]

One to break apart, and 20 to reposition/reassemble.

You'll never get to single digits on a truly scrambled cube.

Re:

[ampathee]

RTFS dude. He didn't solve a cube, he proved that a cube can be solved from any starting position in 25 moves or less.

A *human* can solve a cube in seconds - it's not impressive for a computer to do it.

Re:

[Panaqqa]

Perhaps it can't be reduced to 19 moves. But then again, Kociemba's algorithm has not yet provided a proof that the diameter of the cube group is indeed 20 (in face counting). We won't have such a proof until an optimal solver is used, something that could take years of run time on current hardware. Application for a grid perhaps?