Albion College
Mathematics and Computer Science
On God's Number(s) for Rubik's Slide
Brittany Shelton

Ph.D. Candidate

Mathematics Department

Lehigh University

Rubik's Slide is a puzzle which consists of a $3 \times 3$ grid of squares that is reminiscent of a face of the well-known cube. Each square may be lit one of two colors or remain unlit. The goal is to use a series of moves, which we view as permutations, to change a given initial arrangement to a given final arrangement. Each play of the game has different initial and final arrangements. To examine the puzzle, we use a simpler $2 \times 2$ version of the puzzle to introduce a graph-theoretic approach, which views the set of all possible puzzle positions as the vertices of a (Cayley) graph. For the easy setting of the puzzle, the size of the graph depends on the initial coloring of the grid. We determine the size of the graph for all possible arrangements of play and determine the associated god's number (the most moves needed to solve the puzzle from any arrangement in the graph). We provide a Hamiltonian path through the graph of all puzzle arrangements that describes a sequence of moves that will solve the easy puzzle for any initial and final arrangements. Further, we use a computer program to determine an upper bound for god's number associated to the graph representing the medium and hard versions of the puzzle.

This is joint work with Michael A. Jones, Mathematical Reviews, Ann Arbor MI and Miriam Weaverdyck, Bethel College, North Newton KS.
3:30 PM
All are welcome!
Palenske 227
September 13, 2012