Puzzling examples

Not all groups arising from puzzles must come from the Rubik's cube or some related puzzle. The next example illustrated a group arising from chess.

Example 5.9.1   Consider an infinite chessboard which we imagine being placed on the Cartesian plane. Label one square as $(0,0)$ and call it the origin. Label the others $(m,n)$, as one would label the vertices in a lattice in the plane. Place only one chess piece, a king, at $(0,0)$. Label the move one square to the right $x$, one square to the left $x^{-1}$, the move one square forward $y$, one square backwards $y^{-1}$, and label the other moves $xy$, $x^{-1}y$, $x^{-1}y^{-1}$, and $xy^{-1}$, in the obvious way. The set of all possible kings moves may be identifies with the set

$$King:=\{x^my^n\ \vert\ m,n\in \mathbb{Z}\}.$$

Note $King$ is an infinite abelian group under multiplication. This group can be identified with $\mathbb{Z}\times\mathbb{Z}$ (where the group operation is componentwise addition). The number of ways that the king can reach the square $(m,n)$ in $N$ moves is the coefficient of $x^my^n$ in the expansion of

$$(x+x^{-1}+y+y^{-1}+xy+x^{-1}y+x^{-1}y^{-1}+xy^{-1})^N.$$

For example, using this in a computer algebra package (such as MAGMA or GAP or Maple or Mathematica), it is easy to see that there are $19246920$ ways to reach $(1,1)$ from the origin in $10$ moves. Further details can be found in the chapter ``Wanderungen von Schachfiguren'' by K. Fabel in [BFR].

Example 5.9.2   The collection of all moves of the Rubik's cube may be viewed as a subgroup $G$ of $S_{48}$. The center of $G$ consists of exactly two elements, the identity and the superflip move which has the effect of flipping (i.e., rotating by $180^o$) every edge subcube, leaving all the corners alone and leaving all the subcubes in their original position. One move for the superflip is

$$\begin{array}{c} {\rm superflip} = R*L*F*B*U*D*R*L*F*B*U... ...2*D*R^2*L^2*D\ \ \ \ (34 \ {\rm quarter turns}), \end{array}$$

where $M_R$ is middle right slice move (rotation by 90 degrees of the middle slice, keeping the right face and left face fixed, as viewed from the right face). Other expressions for this move are Dik T. Winter's move

$$\begin{array}{c} {\rm superflip} = F*B*U^2*R*F^2*R^2*B^2*... ...R^2*U*B^2*U \ \ \ \ (28 \ {\rm quarter turns}), \end{array}$$

and Mike Reid's move (found with a computer search)

$$\begin{array}{c} {\rm superflip} = R^{-1}* U^2* B* L^{-1... ...* U* D^{-1} \ \ \ \ (24 \ {\rm quarter turns}). \end{array}$$

Jerry Bryan (in a Feb 19, 1995 posting to the cube-lover's email list, [CL]) showed that no fewer number of quarter turn moves taken from

$$\{R,R^{-1}, L,L^{-1}, U,U^{-1}, D,D^{-1}, B,B^{-1}, F,F^{-1}\},$$

that will also give this move. In the jargon, this move is `minimal in the quarter-turn metric'. The proof that $Z(G)=\{1,superflip\}$ uses the determination of the group structure of $G$ given later (see also [B]). By the way, there is a ``longer'' element of the Rubik's cube group. The superflip composed with the four-spot

$$\begin{array}{c} {\rm superflip4spot} = U^2* D^2* L * F^... ...1}* B^{-1}. \ \ \ \ (26 \ {\rm quarter turns}). \end{array}$$

This was also proven by Mike Reid to be minimal.