Rubik’s cube solved in 25 moves

Last year, a couple of fellas at Northeastern University with a bit of spare time on their hands proved that any configuration of a Rubik’s cube could be solved in a maximum of 26 moves.

Now Tomas Rokicki, a Stanford-trained mathematician, has gone one better. He’s shown that there are no configurations that can be solved in 26 moves, thereby lowering the limit to 25.

Rokicki’s proof is a neat piece of computer science. He’s used the symmetry of the cube to study transformations of the cube in sets, rather than as individual moves. 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.

But Rokicki isn’t finished there. He is already number-crunching his way to a new bound of 24 moves, a task he thinks will take several CPU months. And presumably after that, 23 beckons. (link)

Advertisements

0 Responses to “Rubik’s cube solved in 25 moves”



  1. Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s




Enter your email address to subscribe to this blog and receive notifications of new posts by email.

Join 29 other followers

Technorati – Blog Search

Add to Technorati Favorites

submit express


%d bloggers like this: