Do you remember Rubik’s cube, that frustrating “toy” of the 1980s? The idea was to move the sides around, then restore them to their originalcolors in as few moves as possible. For most people, of course, that restoration proved impossible, and the cube moldered in a closet until being thrown out.
But it’s inspired a pair of graduate students from Northeastern University in Boston. They programmed a supercomputer to discover just how few moves could be used to return the cube to its pristine state. They presented their solution at the International Symposium on Symbolic and Algebraic Computation in Waterloo, Ontario.
The previous best has been 27 moves, but after 63 hours of number crunching, the supercomputer arrived at a solution that, quite literally, went one better – that it can be solved in no more than 26 moves.
Students Daniel Kunkle and Gene Cooperman approached the idea with some creative thinking, which was necessary as the 43 billion billion possible positions of the cube was too massive even for the computer. So they used a two-stage solution.
First they programmed the supercomputer to reach one of 15,000 half-solved solutions, which could then be closed in a few moves. Their results indicated that the puzzle could be solved in a maximum of 29 moves,but in most cases 26 moves or less.
From there they decided to focus on the small number of configurations that would require more than 26 moves to reach a solution. Since there were so few of these, it was possible to use the supercomputer to figure out the answer. Perhaps surprisingly, the computer could solve them all in fewer than 26 moves.
So what’s the point of all this? It brings mankind closer to the so-called “God’s number,” the minimum number of moves necessary to solve any Rubik’s cube. The name comes from the fact that God would only need the minimum number of moves, which theorists feel is in the low 20s.
How Many Moves to Solve Rubik’s Cube?
