June 25th, 2007
Searching for God's number
I was just a little old for the Rubik’s Cube phenomenon of the 1980’s, but my little brother had one and I remember spending the better part of the Christmas vacation he got it trying to solve the puzzle.
Now, there are “speedcubers” who compete to see who can solve random cubes the fastest. The world record is 9.86 seconds. Wow! Of course not all “random cubes” are created equal. Some are tougher than others. The curious might wonder “What’s the minimum number of moves necessary to solve cube from even the most difficult of it’s 43 quintrillion possibilities?” This number is called “God’s number” by speedcubers.
Well, wonder no more. Dan Kunkle and Gene Cooperman of Northeastern University have shown that the answer is “26.” At least that’s the lowest proven number to date. The final number could be lower.
Their proof ran for 63 hours on a cluster of 128 CPUs. That and 18 months of work to put it all together was all it took. Oh, and part of an NSF research grant too.
I know what reaction I’d get from my dad if I told him about this. He’d be pretty upset that part of his hard-earned tax contribution went toward figuring out the smallest number of moves to solve a toy puzzle.
But that misses a key point. One of the things one learns in a good computational theory class is that solutions to one type of problem can frequently be turned into solutions for other problems of the same class. In this case, knowing how to carry out a massive combinatorial search like the one for God’s number elucidates a technique for solving other large combinatorial problems (most of the interesting ones involve scheduling–air traffic control, for example).
Transforming the solution for one problem into the solution for another is an example of computational thinking, the idea that there are ways of thinking about problems that are computational and should be part of every educated person’s intellectual toolkit.
Phil Windley is an Associate Professor of Computer Science at Brigham Young University. See his full profile and disclosure of his industry affiliations.
