From: rusin@vesuvius.math.niu.edu (Dave Rusin)
Subject: Re: Rubik's tour.
Date: 29 Jan 2000 08:00:53 GMT
Newsgroups: rec.puzzles,alt.math,sci.math,alt.math.recreational
Summary: Cayley diagram for the Rubik's group

[A number of posters commented on this thread; I can't quite out who said what]

> Suppose we have Rubik's cube, and suggest a tour such that all
> possible outcomes of the various configurations are presented. We
> begin with the identity.
> Is this possible?

> Hmmn.  It seems like a tour should be possible due to the regularity
> of the configuration graph (a vertex for each configuration and
> two vertices are connected if you can move from one configuration
> to the other by turning some face 1/4 of a turn).

This "configuration graph" is the Cayley diagram for this group [together
with this set of generators]; you're asking if there is a Hamiltonian
path through this graph. You're right, a high degree of regularity makes
this more likely but that's not sufficient. On the other hand I believe it
is conjectured that all Cayley diagrams have Hamiltonian circuits, so
probably one can (if verrry patient) cycle through all the configurations
of the Rubik's group without repetition. As far as I know this conjecture
is only known to be true for groups with a fairly simple presentation
(for which a direct assault of the graph is possible). There was a
survey article by Joe Gallian and Steve Curran a few years ago which
must have discussed this.
dave