Researchers Close to Finding 'God's Number'

Loraine Lawson

There are a few mysteries from my childhood I still ponder. How many licks does it take to get to the center of Tootsie Pop? Why doesn't the Coyote ever catch the Road Runner? What was that stuff inside Stretch Armstrong?

 

And just how do you solve a Rubik's Cube?

 

It's not that I wasn't shown half a dozen times. It's just that one friend had just found one way to get to the right solution and a different friend found a different way, which -- logically -- made me suspect they each knew the same magical incantation and weren't sharing.

 

Also, I am not a patient person, and I quickly lost interest, opting to spend my free time watching my pet snail explore a glass bowl.

 

I didn't know the real challenge wasn't how you solved it, but how many moves, and that there must be a lowest number of turns that can solve any Rubix Cube. Fans call this number God's Number. (Sorry if you didn't know and thought the headline referred to something more... err... what's the word? Oh yeah: Significant.)


 

Obviously, this is a task for a computer. The problem is, even a supercomputer would take too long to explore the 43 billion possible positions, according to this BBC article.

 

Fortunately, two bright U.S. graduate students (American ingenuity!) put their heads together to determine out how a supercomputer could be put to the task. Northeastern University of Boston students Daniel Kunkle and Gene Cooperman -- who apparently did not have pet snails -- programmed a supercomputer to arrive at one of 15,000 half-solved solutions, each of which could fully be solved with a few extra moves.

 

I know. It's hard to believe someone let them use a supercomputer for this. And yet, it's also hard to believe no other computer geek had tackled this before.

 

The conclusion of their experiment: Any disordered cube can be fully solved in a maximum of 29 moves, however, most cubes take fewer than 26 moves to solve.

 

They're presenting on this experiment at the International Symposium on Symbolic and Algebraic Computation in Waterloo, Ontario. I don't know, but my guess is this approach could have other uses. I certainly hope so.

 

Now, if we can just get that owl to run a few computer simulations on a virtual lollipop.



Add Comment      Leave a comment on this blog post

Post a comment

 

 

 

 


(Maximum characters: 1200). You have 1200 characters left.

 

null
null

 

Subscribe to our Newsletters

Sign up now and get the best business technology insights direct to your inbox.