« Cloudy Crystal Balls | Main | Calculating the Word Spurt »

Cracking the Cube

By Julie J. Rehmeyer

Daniel Kunkle can solve a Rubik's Cube in 26 moves. Or at least his computer can.

Kunkle, a computer scientist at Northeastern University in Boston, has proved that 26 moves are enough to solve any Rubik's Cube, no matter how scrambled. That's one move below the previous record. In the process of cracking the cube, he developed algorithms that can be useful for problems as disparate as scheduling air flights and determining how proteins will fold.

Rubik's Cube has approximately 43 quintillion possible configurations. Even a supercomputer can't search through every possible configuration to find the quickest way to unscramble a given starting arrangement in a reasonable amount of time. So Kunkle and his advisor Gene Cooperman developed some clever mathematical and computational strategies to make the puzzle more manageable.

f8722_1321.gif

To solve a Rubik's Cube, rotate the "facelets" so that each side of the cube is all one color.
Courtesy of Matthew Fisher

Kunkle and Cooperman started by applying various mathematical tricks. If each side of the cube is one color, the puzzle is solved regardless of which color is on which side. By considering configurations to be equivalent if they differ only in having two colors interchanged, the computer scientists managed to reduce the number of truly distinct configurations to just over a quintillion.

Next, they looked at a simpler problem: they considered only configurations that could be solved by twisting facelets through half-turns only, with no quarter-turns. Only about 15,000 of the quintillion configurations can be solved in this way. A standard PC can find the shortest way to unscramble each of this relatively small number of configurations in less than a day, simply by searching through all possible moves. The team found that any puzzle in one of those special configurations could be solved in 13 moves or fewer.

Then they figured out how many steps are required to turn any random configuration into one of the 15,000 special configurations. To do this, they first classified the configurations into sets, each containing configurations that can be transformed among themselves using only half-turns. These sets were constructed in such a way that a series of moves that gets from one member of any set to one of the special configurations will also turn any other member of the set into a special configuration. They ended up with 1.4 trillion of these sets, so they now had only 1.4 trillion problems to solve—far fewer than the original 43 quintillion, but still a formidable number.

Now they put a supercomputer on the job and applied clever computational strategies to speed up the search. Because it takes computers a very long time to search for information stored on a hard drive, Kunkle and Cooperman developed ways to store the information in precisely the order the computer would later need it. That way, the computer could read the information off the drive without searching for it.

"These kinds of techniques can be applied to any combinatorial problem that you want to solve," Kunkle says. He points to checkers, chess, scheduling of air flights, and protein folding as examples. A somewhat similar set of computational techniques was recently used to find the best strategies for playing checkers (SN: 7/21/07, p. 36).

After 63 hours of calculation, the supercomputer found that it took no more than 16 steps to turn any random configuration into a special configuration that can be solved using only half-turns. And since those special puzzles can be solved in no more than 13 steps, this approach showed that 29 steps were enough to solve any Rubik's Cube.

But this answer wasn't good enough to set a new record. Last year, Silviu Radu of the Lund Institute of Technology in Sweden showed that any Rubik's Cube can be solved in no more than 27 steps. Kunkle and Cooperman realized that to set a new record, they would need to eliminate three steps.

Their existing method had established that all but about 80 million sets of configurations could be solved in 26 steps or fewer. By searching through all possible moves starting from those relatively few configurations, they succeeded in finding a solution for each one that took 26 steps or fewer.

They presented their result July 29 at the International Symposium on Symbolic and Algebraic Computation in Waterloo, Ontario.

Kunkle and Cooperman now hope to knock the maximum number of steps down to 25. They think they can use their brute-force search method on all of the configurations that require 26 steps to find a quicker way to solve them.

Even if they manage this feat, however, it will probably leave room for improvement. Most researchers believe that just 20 steps are enough to solve any Rubik's Cube, but no one has proved it yet.


References:

Kunkle, D. and G. Cooperman. 2007. Twenty-six moves suffice for Rubik's Cube. International Symposium on Symbolic and Algebraic Computation, 2007. July 29. Waterloo, Ontario. Available at http://www.ccs.neu.edu/home/gene/papers/rubik.pdf.

Radu, S. 2006. Rubik can be solved in 27f. Available at http://cubezzz.homelinux.org/drupal/?q=node/view/53.

Rehmeyer, J. 2007. Check on checkers: In perfect game, there's no winner. Science News 172(July 21):36. Available at www.sciencenews.org/articles/20070721/fob4.asp.

For more information on Rubik's Cube, go to http://en.wikipedia.org/wiki/Rubik's_Cube.

Comments

Okay, convert these techniques into AMD Stream Computing code using ATI cards and then set them loose on the Cube and protein folding problems.

A supercomputer may be able to perform this feat. However, has anyone actually been able to use so few turns to solve a real Rubik's Cube regardless of its starting configuration?

>>A supercomputer may be able to perform this feat. However, has anyone actually been able to use so few turns to solve a real Rubik's Cube regardless of its starting configuration?

You don't understand. What they did was to come up with an algorithm that solved *all* of the possible configurations of the puzzle in 26 moves (or less). That means by using the set of steps prescribed in the algorithm, no matter what configuration the cube is in, you will solve it in 26 steps (or less).

The problem of brute force solving for the entire cube is too computationally complex to do with current computers (even a lot of them), but by simplifying the problem and removing 4 orders of magnitude from the problem space, they solved it. (and it still took 66 hours on a supercomputer).

err make that 7 orders of magnitude, I could have sworn it said "quadrillion" and not "quintillion".

"What they did was to come up with an algorithm that solved *all* of the possible configurations of the puzzle in 26 moves (or less)."

That actually makes no sense whatsoever. I know how to solve the cube, I know how they work. There is no single algorithm that can solve any possible configuration in less than 26 moves simply because most of the configurations are completely different - i.e. an entirely different problem to be solved.

Plus, if there were such an algorithm (and one as incredibly short as 26 moves) everyone in the world would be able to solve Rubik's cube in no time flat. This is clearly not the case.

Each (unique) configuration has an optimal solution that requires the least amount of moves - but this solution is completely different from any other configuration's. Thus, this discovery is theoretically useful, but no applicably useful. In order to solve any configuration in 26 moves or less, one would probably have to memorize billions and billions of different solutions.

"That's why I put this darn thing down here (in the basement) in the first place" - Marge Simpson

I think 'The Dog' has a reasonable question here. The paper might was well be in a foreign language for me. How does this, or doesn't it, translate into a human usable method for solving the cube?

Sure this information is nice. but i guess if you give pictures to solve the issue that will be more helpful.

What a great move forwards. One stepp less and it`s a new record.

Could you tell me how to beat a slot machine please?

The guy who demonstrated that the cube can be solved in 27 steps, Mr. Silviu Radu is a Romanian. I am proud that he managed to solve this problem, even if now his algorithm was beaten by 1 step (27 steps vs. 26 steps).

I firmly believe that any complex problem could be solved using human brain's logical methods.I'm not against talking help from computers but i guess there should be an easy way to do this.
All big problems usualy have a very simple solution.
I believe many would not agree with me, but this what i fell and this is what i believe in.

@TheDog: I think you're wrong. THe article was very clear in *not* saying that one 26-step method would solve *any* configuration. I came away with the impression that, for any configuration, "there exists" a 26-step solution.

You mean there is a way to actually solve it? I just peeled the stickers off.

>>A supercomputer may be able to perform this feat. However, has anyone actually been able to use so few turns to solve a real Rubik's Cube regardless of its starting configuration?

I think there is a misunderstanding of concept there. What they have aimed to achieve here is firstly use solving each in 13 steps with different algorithms that are specific to each configuration.

When I was in high school, this kid who always got in trouble and had terrible ADD could solve that thing within seconds. Maybe because he was always in in-school? or detention? He would give it back to me and I would mix it up again the best I could...he solved it again. It was amazing! I thought this guy was an idiot (he still could be) but he solved this thing everytime within 30 seconds. He tried to teach me but I was lost after he told me to get all the yellow or white together...I don't remember. Anyway, David has a gift!! I've never met anyone else who could do it!

Gotta love the things people use super computers for. Instead of something important their solving Rubik's cubes

Razvan,
you are proud because Mr. Radu is a Romanian??? Be proud of something you did, don't try to bask in someone else's glory just because you happen to be from the same country.

Lauren - Its computational math and how to solve a problem more efficiently. It can be applied for many things. The use of a Rubiks cube is a tangible object people know and have used, rather than say like ...the folding of a protein...because most people haven't even taken College Biology and or College Chemistry. Think of it as a PR move :P

Maybe they should be using the super computers to find larger prime numbers for security purposes.

Lauren - Its computational math and how to solve a problem more efficiently. It can be applied for many things. The use of a Rubiks cube is a tangible object people know and have used, rather than say like ...the folding of a protein...because most people haven't even taken College Biology and or College Chemistry. Think of it as a PR move :P

Maybe they should be using the super computers to find larger prime numbers for security purposes.

there is no reason to believe that rubiks cube has any meaningful similarities to protein folding.

adam, over here in america we still congratulate ourselves (regularly!) on having won world war 2. so dont smart off about basking in other people's triumphs or we will have to come bring democracy to wherever it is you live. and you dont want that.

I understand what they mean by solving "all" combinations. They chose algorithms that can provably change a cube from one state to another... then they tried all possible combinations of state transitions rather than individual turns; breaking the task into provable chunks... Because each transition is provable by itself, they didn't need to test every combination of turns all the way through.

Unfortunately, this isn't much more groundbreaking than the Thistlethwaite algorithm; progressively increasing "solvedness" based on colors groupings. Their approach saved one extra step, but I think using increasingly limited turn-types is not going to lead to a "God's Algorithm".

Also, approaches like this aren't practical for speed-cubers. The thinking time required for these algorithms (and sometimes immense amounts of memorization) are too much -- it's quicker to take a few extra turns than it is to stop and think.

From what I can tell, these guys haven't advanced the theory at all. They simply optimized the computer calculation slightly and used a supercomputer. I have much more respect for Silviu Radu.

Personally, I'd like to see some sort of analysis as to the distribution of moves necessary to complete the puzzle. How many positions actually require the full 26 moves to complete? I'd bet that answer is quite small, just as the number of positions that require only one move to complete is quite small.

The claim is indeed that all positions require 26 moves or less. A complete algorithm isn't point blank claimed in the article, but given the commentary (if correct) it looks a lot like that might also be covered.

Why doesn't everyone solve every solution in 26/(time per move)? Because one can't sort through all this. Even the "normal" computer solvers go pretty low, much below the 50 odd moves needed by a skilled cuber. Human solving methods are chopped into several steps, leading one between members of different sets. First by intuition (if I can get a top cross, a corner with three sides, all sides, all corners - part of that set). Then a smaller subset - first two layers, top layer, whatnot. Then another, sides rotated, corners aligned. There are many routes, but they all work the same way: Giant set -(moves)-> Smaller subset -(so on for several)-> done. Humans can patter recognize well, computers can remember well. So humans use many more steps. In this case they claim two steps. One half, out of a very large whole, to get it to half turns. Then another to solve half turns. Even half turns is in several millions. People can't do that. Computers can.

I think that if you would show the algerithums so I could solve it This article would be ALOT!! better

HAH! 26? That's way too many, go here: http://kociemba.org/cube.htm and get the cube explorer. You will never have more than 20 moves after you optimize a solution. At least not one that I can find anyway. Herbert Kociemba is teh r0xx0r.

alot of you guys seem to be missing the point. 26 as opposed to 27 moves really doesn't matter. but they did come up with a way to extremely boost a computer's computational speed when solving complex algorythms. that is what is impressive and important. the rubik's cube solution is just an interesting novelty.

The reason humans take more than the claimed "maximum" of 26 moves is because we do not have the memorization capacity of computers. Though they can memorize massive numbers of algorithms, (and as previously stated there is no unique solution) humans tend to memorize by pattern. For example, I use the same algorithm to solve any cube regardless of how it's shuffled. Since this is one unique algorithm... obviously it will require a variable number of steps to solve different configurations (i.e. either the number of moves is constant and the number of algorithms is variable or vice versa)

wow! 26 moves, even i cant do that, i solve in somewhere between 80-100 moves, including slices, i once saw a guy build a machine out of leggos to do the cube, pretty sick, u can see me doing the cube, or learn how to do the cube at www.rubiks-cube-solutions.com

The thing about the cube, yes, they are saying that all positions require 26 moves or less(though they think they can get it to 20). As Geminitojanus said, this doesnt mean its the same pattern for every configuration of the cube. I can do the cube in about 30-60 seconds, in 3 different ways. It is not possible for there to be one algorithm to fix them all, or even many of them. Im good with the cube, but Ill leave it up to the computer to do it in 20-26 moves.

I also agree with Popedarren partially, a large purpose of the article is the achievement of boosting a computer's computational speed, thats pretty big, vs doing the cube in a XX about of turns.

Wait, wait, wait, when did it become the 80's again?

There is no algorithms that can solve the cube in 26,27,28 or even 30 moves. If you find one, let me know. It can be proven mathmaticaly and numericaly, but there is NO algorithem that can solve it in that few moves. Some of you are misunderstanding everything. Do not compare apples to bananas or to oranges. An algorithm is a set of rules or finite steps you follow to get an end result. There is no steps to follow that will yield a solve cube in 26, 27, or even 30 steps that I've seen. Hence no, algorithm that can work in 30 steps. But it is proven mathmatically. You know how many steps, but you dont know whats steps to take to get there.

"though they think they can get it to 20" - I believe someone has found a position that requires 21 moves.

To everyone who is reading this looking for the method they used to solve it: I belive it is like this:

1) Remember every single combination that can be reached within (let's say) six turns from a complete cube.

2) from the position you are trying to solve, try 20 moves at random. If you don't get to one of the thousands of positions you remembered above, start over and try to get there in 2o moves again.

It's not great, but a computer can do it quite fast. (It's also a bit more complex)

The thing about maths is that something as wierd as this can actually end up solving lots of other problems that turn up in completely disconnected fields (e.g. folding proteins), as by proving this you will have proved a result for a rubik's cube, and for any groups (mathematical definition of a group) that are similar, and for any network of connected points that are similar to the group's "Cayley graph", and thanks to the magic of topos theory, just about any other area of maths or science, although discoveries always take a long time to filter down to other areas of research.

"Even a supercomputer can't search through every possible..."

As early as 1998, when you could still download amazing freeware games, I found a program that solved the cube on my ordinary desk top PC, very quickly (though I can't recall in how many moves!)

17 moves has enough pathways but there will be many duplications. 20 is more likely. 26 would provide more than a billion pathways for each cube arrangement which seems far too many.

Of course all this is useless to solve a particular case, because we cannot possibly discover which of the 40 billion, billion arrangements we have to start with.

A useful simplification is to first find the moves to get one large corner, consisting of a corner piece and the three edge pieces, right and then, only move the three cube faces that don’t alter this group. With 9 possible first moves and subsequently 6, 26 moves is a bit more likely. The big advantage is that the number of arrangements of the rest of the cube is only about three thousand million!
Doing it this way has the advantage that we can hold the cube at the back and the possible 9 clockwise twists can be 1,2,and3 for the top face., 4,5 and 6 for the right side face and 7,8 and 9 for the left side face.
Now comes the clever bit. We work out the 20 sets of moves to bring the first corner from where it is to its right place. Then from this position we work out the 17 sets of moves to bring the second corner to its right place and also return the first corner to its right place. Then from this position we work out the 14 sets of moves to put all three corners right. Continuing with 11 sets for corner 4, 8 sets for corner 5 and 5 sets for corner 6, when corner 7 will be right as well.
The price for this is that there will be many more than 26 moves altogether, but well worth it.
Carrying on in the same way with the edge pieces. We need 17 sets of moves to put edge 1 right and all the corners right, 15 sets for edges 2 and 1 and all the corners and so on to edge 8.
Because these steps are added rather than multiplied, the total of 153 sets of moves is equivalent to the three thousand million. It can be printed on one A4 sheet which is not bad for a complete solution of the cube

Post a comment

(If you haven't left a comment here before, you may need to be approved by the site owner before your comment will appear. Until then, it won't appear on the entry. Thanks for waiting.)