Application: God's algorithm

Problem: Let $G$ be the group of a permutation puzzle. Find the diameter of the Cayley graph of $G$ .

Sometimes this is called God's algorithm, though here that term is reserved for a harder version of the problem, stated below. This diameter problem is unsolved for must puzzles (including the $3\times 3$ Rubik's cube) and appears to be very difficult computationally (see [J1] for a discussion of similar problems). One case where it is known includes the $2\times 2$ Rubik's cube puzzle [CFS], which has diameter $14$ .

Problem: Let $G$ be the group of a permutation puzzle and let $v$ be a vertex in the Cayley graph of $G$ . Find an algorithm for determining a path from $v$ to the vertex $v_0$ associated to the identity having length equal to the distance from $v$ to $v_0$ .

This problem is much harder. The algorithm, if it exists, is called God's algorithm.

Let $\Gamma$ be a graph. A Hamiltonian circuit on $\Gamma$ is a sequence of edges forming a path in $\Gamma$ which passes through each vertex exactly once. (If you think of the vertices as cities and the edges as roads then a Hamiltonian circuit is a tour visiting each city exactly once.)

The following unsolved problem was first mentioned in this context (as far as I know) by A. Schwenk.

Problem: Let $G$ be the group of the $3\times 3$ Rubik's cube puzzle. Does the Cayley graph of $G$ have a Hamiltonian circuit? In other words, can we (in principle) ``visit'' each possible position of the Rubik's cube exactly once, by making one move at a time using only the basic generators $R, L, U, D, F, B$ ?

This is a special case of a more general unsolved problem: For an arbitary permutation group with more than two elements, is the Cayley graph Hamiltonian?

An example of one where the Hamiltonian circuit problem is known is the symmetric group.

Example 5.16.14   Let $G$ be the group $S_n$ with generators given to be the set of all transpositions:

$$G=S_n, X=\{(i,j) \vert 1\leq i< j\leq n\}.$$

(There are many more transpositions than necessary to generate $S_n$ since the subset of transpositions of the form $(i,i+1)$ , $1\leq i\leq n-1$ , suffice to generate $S_n$ [R].) The algorithm of Steinhaus (see §4.5) shows that there is a Hamiltonian circuit in the Cayley graph of $S_n$ with respect to $X$ .

The reader interested in more examples is referred to [CG].

Exercise 5.16.15   Find the Cayley graph of the sliced squared group

$$G = \langle M_R^2, M_F^2, M_D^2\rangle ,$$

where $M_R$ is the middle slice move which turns the middle slice parallel to the right face clockwise 90 degrees (with respect to the right face). Find the diameter of this graph.