Application: Rubik's cubes

First, some general terminology which applies to any Rubik's cube-like book. A one person game is a sequence of moves following certain rules satisfying

• there are finitely many moves at each stage,
• there is a finite sequence of moves which yields a solution,
• there are no chance or random moves,
• there is complete information about each move,
• each move depends only on the present position, not on the existence or non-existence of a certain previous move (such as chess, where castling is made illegal if the king has been moved previously).

The reader will find a fascinating and much fuller discussion of combinatorial game theory in the book by Berlekamp, Conway, and Guy [BCG] (volumes I and II). A permutation puzzle is a one person game with the following five properties listed below. Before listing the properties, we define the ``puzzle position'' to be the set of all possible legal moves. The five properties of a permutation puzzle are:

1. for some $n>1$ depending only on the puzzle's construction, each move of the puzzle corresponds to a unique permutation of the numbers in $T = \{1, 2, ..., n\}$,
2. if the permutation of $T$ in (1) corresponds to more than one puzzle move then the the two positions reached by those two respective moves must be indistinguishable,
3. each move, say $M$, must be ``invertible'' in the sense that there must exist another move, say $M^{-1}$, which restores the puzzle to the position it was at before $M$ was performed,
4. if $M_1$ is a move corresponding to a permutation $f_1$ of $T$ and if $M_2$ is a move corresponding to a permutation $f_2$ of $T$ then $M_1*M_2$ (the move $M_1$ followed by the move $M_2$) is either
   • not a legal move, or
   • corresponds to the permutation $f_1*f_2$.

Notation: As in step 4 above, we shall always write successive puzzle moves left-to-right. We shall consider briefly the $2\times 2$ and $3\times 3$ Rubik's cubes.