## Application: God's algorithm

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

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 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 Rubik's cube puzzle [CFS], which has diameter .

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

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

Let be a graph. A Hamiltonian circuit on is a sequence of edges forming a path in 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 be the group of the Rubik's cube puzzle. Does the Cayley graph of 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 ?

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 be the group with generators given to be the set of all transpositions:

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

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

Exercise 5.16.15   Find the Cayley graph of the sliced squared group

where 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.

david joyner 2008-04-20