ITA Software's Technical Seminar Series

Talk Topic: Twenty-Six Moves Suffice for Rubik's Cube
Dan Kunkel, Northeastern Univeristy
August 8, 2007

Abstract

The minimum number of moves sufficient to solve any configuration of Rubik's Cube has been a matter of long-standing conjecture -- since the puzzle appeared over 25 years ago. This number is sometimes known as "God's Number". Here, we show that God's Number is no more than 26.

To achieve this result, we use new techniques in two areas: group theoretic methods for efficiently representing and computing over the possible configurations of Rubik's Cube; and, parallel disk-based algorithms for enumerating large search spaces. This talk will primarily focus on the search and enumeration techniques we introduce.

The move to disk-based search and enumeration algorithms is being driven by the halt in the historical growth in the amount of RAM per CPU. Indeed, the current trend toward multi-core processing threatens to take us backwards. By allowing the efficient use of disk, these new search algorithms provide solutions to problems several orders of magnitude larger than previously possible.

Bio

Dan Kunkle is a PhD candidate in the High Performance Computing Lab at Northeastern University. His research interests include combinatorial optimization, high performance computing, and adaptive systems.