Kent State Professor Helps Solve Rubik’s Cube ProblemPosted Aug. 18, 2010
A long-standing problem behind one of the world’s most popular and addicting puzzles has been solved. A team of researchers, including Dr. Morley Davidson, an associate professor of mathematical sciences at Kent State University, has unveiled new research that finds that every position of the Rubik's Cube™ can be solved in 20 moves or less.
“In seventh grade, I got a Rubik’s Cube as a birthday gift from my mom, and I was soon determined to understand the mathematics behind the puzzle,” Davidson said. “Four years ago, while incorporating the puzzle into my teaching, I became interested in computational Cube research and began working with graduate student Joseph Miller on theoretical questions related to popular solution methods. This past spring, I was invited to participate in the end run to crack the God’s Algorithm problem.”
Along with Davidson, the research team consisted of John Dethridge, an engineer at Google in Mountain View, Calif.; Herbert Kociemba, a math teacher from Darmstadt, Germany; and project leader Tomas Rokicki, a programmer from Palo Alto, Calif. With computer time donated by Google, the team essentially solved every position of the Rubik's Cube – all 43,252,003,274,489,856,000 positions – and showed that no position requires more than 20 moves.
“Every solver of the Cube uses an algorithm, which is a sequence of steps for solving the Cube,” the team explained on its website. “One algorithm might use a sequence of moves to solve the top face, then another sequence of moves to position the middle edges, and so on. There are many different algorithms, varying in complexity and number of moves required, but those that can be memorized by a mortal typically require more than 40 moves.
“One may suppose that an omniscient being would use a much more efficient algorithm, always using the shortest sequence of moves. This is known as God's Algorithm. The number of moves this algorithm would take in the worst case has been called God's Number since the early years of the Rubik's Cube some 30 years ago. At long last, God's Number has been shown to be 20.”
According to the research team, it took 15 years after the introduction of the Cube for somebody to find the first position that provably requires 20 moves to solve. Appropriately, 15 years later, it has been established that 20 moves suffice for all positions.
The cube was created in 1974 by Erno Rubik, a Hungarian university lecturer, and was launched in 1980, soon becoming a global phenomenon and an icon of the ‘80s. In the puzzle’s 30-year history, more than 350 million have been sold worldwide. To learn more about Rubik’s Cube, visit www.rubiks.com.
To learn more about the research conducted by Davidson and his collaborators, visit www.cube20.org.
For more information about Kent State’s Department of Mathematical Sciences, visit www.kent.edu/math.
# # #
Dr. Morley Davidson, an associate professor of mathematical sciences at Kent State University, helped unveil new research that finds that every position of the Rubik's Cube can be solved in 20 moves or less.
Morley Davidson, firstname.lastname@example.org, 330-672-9040
Emily Vincent, email@example.com, 330-672-8595