CS Colloquium 11/2/2011 "Rubik's Cube in Twenty Moves or Less"Posted Oct. 29, 2011
Rubik's Cube in Twenty Moves or Less
Dr. Morley Davidson
Mathematical Sciences Department
Kent State University
3:45 pm, 2 November 2011, 228 MSB
In July 2010 an international team of researchers led by Tomas Rokicki announced that "God's Number" for the Rubik's Cube is 20, that is, all scrambles can be solved in at most 20 moves. The speaker had the privilege to be part of this effort, which was ultimately brought to conclusion with the help of Google's high-performance computing infrastructure. In the first half of the talk we will recount the thirty-year history of cubing and examine the mathematical and computational problems underlying the basic problem at hand (in technical terms, that of determining the diameter of the Cayley graph of the Rubik's Cube group). Then we will describe some of the key breakthroughs that finally led to its solution, and round out the talk with a brief demo of some hands-on solution techniques.
PhD in Math from Univ of Michigan ('95), joined KSU faculty in '96 after doing postdocs at The Institute for Advanced Study and the Univ of Georgia. Started working on Cube research about five years ago, and in spring 2010 joined the team that along with Google's help made the final push to the sharp bound of 20 moves. On a related note and also last year, with Bruce Norskog and the Ohio Supercomputer Center, we calculated the depth and diameter of the classic 15-puzzle in the more natural "multi-tile metric". Hobbies include playing computer games with my four-year old son, and dreaming of having time to get back to playing pocket billiards and piano! And finally an odd fact: I'm a "Goldberg bug" -- since grad school, my collection of CD, LP, and even YouTube recordings of Bach's Goldberg Variations has grown to an embarrassingly large number!