Any Rubik's Cube Configuration Can Be Solved in 3³ – 1 (Wrist) Moves

June 11, 2007

Computer scientist Gene Cooperman and graduate student Dan Kunkle of Northeastern University used group theory and a lot of computer memory to answer one of life's riddles about Rubik's cube, perhaps the most famous combinatorial puzzle of all time: Optimally — if one were a genius — what number of wrist twists suffice to solve any of the many billions of configurations of the puzzle that Erno Rubik invented in the 1970s?

The answer is a meager 3³ – 1 times. Their solution easily shatters the old record of 3³ moves.

The two researchers arrived at the answer the easy way — via computers, naturally — by putting all of the possible configurations of a Rubik's cube into a family of sets of configurations, which in group theory is called a family of cosets. After analyzing the results of applying a single move all at once to all of the configurations of a coset, they used their 7 terabytes of distributed disk (as an extension to RAM) to compute moves at 100,000,000 times per second.

Their program, they said, does a precomputation and then — in about a second — voila! Out pops no more than 3³ – 1 moves to solve any Rubik's cube configuration.

But there is a serious side to all this. "Search and enumeration," Cooperman said, "is a large research area encompassing many researchers working in different disciplines — from artificial intelligence to operations. The Rubik's cube allows researchers from different disciplines to compare methods on a single, well-known problem."

Source: Northeastern University, May 31, 2007