At last, the Hamiltonian circuit problem for Rubik's Cube has a solution! To be a little more mathematically precise, a Hamiltonian circuit of the quarter-turn metric Cayley graph for the Rubik's Cube group has been found.
Basically it is a sequence of quarter-turn moves that would (in theory) put a Rubik's cube through all of its 43,252,003,274,489,856,000 positions without repeating any of them, and then one more move restores the cube to the starting position. Note that if we have any legally scrambled Rubik's Cube position as the starting point, then applying the sequence would result in the cube being solved at some point within the sequence.
(Note that the following discussion describing how the solution was found is somewhat technical and assumes some basic knowledge of the branch of mathematics known as group theory and common conventions used in mathematical discussions of Rubik's Cube.)
The Hamiltonian circuit was constructed in a hierarchical manner using nested subgroups. These subgroups are:
< UR >
< U, R >
< U, R, D >
< U, R, D, L >
< U, R, D, L, F >
The last of these subgroups, of course, is actually the whole cube group. The entire Hamiltonian circuit consists of turns of only five face layers. No turns of back layer are used!
The cyclic group < UR > contains 105 elements. Of course, the Hamilton circuit for this group is simply the two-move sequence UR repeated 105 times. So the number of positions reached in such a cycle is 2 × 105 = 210. The < U, R > subgroup can be partitioned into 73483200/210 = 349920 parts, with each part being such a 210-move cycle. It is easy to connect certain pairs of these cycles together to form larger cycles. A simple breadth-first search can then be used to connect all these 349920 cycles into one big cycle. Thus, finding a Hamiltonian circuit for the < U, R > subgroup was relatively easy to accomplish in this manner.
The < U, R, D > subgroup partitions into 2,177,280 cosets using the < U, R > subgroup. (Note: in this discussion, the term coset will more specifically refer to a left coset as opposed to a right coset.) A Hamiltonian cycle for each coset can be made using the Hamiltonian circuit for the < U, R > subgroup, by changing the starting point to some element of the particular coset. The Hamiltonian circuit for the < U, R, D > subgroup can be constructed by connecting up one coset at a time until all the cosets are connected up into one large cycle.
The given Hamiltonian circuit for this subgroup actually starts with a cycle of 63 cosets. A Hamiltonian path for the < U, R > subgroup can be created by simply removing an R move from that subgroup's Hamiltonian circuit. That path is equivalent to the move R'. Since R'D has order 63, a cycle of 63 cosets is easily created using the above Hamiltonian path followed by the move D, and repeating this 63 times.
The < U, R, D, L > subgroup partitions into 132 cosets using the < U, R, D > subgroup. Cycles for the cosets are connected together in a manner similar to the way the 2,177,280 cosets of the preceding level were connected up.
The < U, R, D, L, F > subgroup partitions into 2,048 cosets using the < U, R, D, L > subgroup. The cosets resulting from this subgroup can be determined by what set of edge cubies are misoriented. (We use the edge orientation convention where quarter-turns of the F or B face layers result in changing the orientation of the four edge pieces moved, while no other face layer turns affect the orientation of any pieces.) Since the move F does not commute with the moves used in the earlier levels, the technique used for the previous two levels no longer works. So instead, of connecting up cosets one at a time, we will connect up three cosets at a time.
The problem of connecting up the 2048 cosets will be done in two phases. In the first phase, 32 cosets that allow up to six specific edge pieces to be misoriented are connected up. In the second phase, we consider 32 sets of 63 cosets each. Each set is associated with one of the cosets of the first phase. The cosets of each set are connected up to its corresponding coset of the first phase. Since 63 is divisible by 3, this works out well. For the first phase, we first connect up six cosets based on the identity maneuver (U' R' U F)6. Of course, we need to use a Hamiltonian path for the < U, R, D, L > subgroup that has the same effect on the cube as U' R' U. In this manner, we traverse six of the desired cosets. (It is noted that this sequence affects the orientation of only six of the twelve edge cubies. So these are the six cubies we allow to be misoriented in the first phase.) This leaves 26 cosets to be traversed. As 26 is not divisible by three, we use the above identity another time during the first phase to connect up five cosets at once. The remaining 21 cosets are connected up 3 at a time.
To connect up 3 cosets at a time, we make use of the fact that F (R' U' R) F' (R' U R U' R) F (R' U R) F' has the same effect on the cube as the single move R. Thus we can replace a single R move in some existing cycle with the above sequence to connect up three additional cosets. Of course, we need to use maneuvers that traverse entire cosets that are equivalent to each of the parenthesized parts of the above sequence. We also note the R' U' R and R' U R are inverses of each other, so the same path can be used for both, but one going in the opposite direction as the other.
It is further noted, that arbitrary sets of three cosets can not be connected up at a time. First, the possible sets of 3 cosets were determined, and then a subset of these sets (that collectively would contain each coset exactly once) were found using a simple recursive search algorithm similar to what might be used to solve a problem such as the well-known eight queens puzzle.
This .zip archive (about 7 megabytes, expands to over 200 megabytes) contains a specification on how this Hamiltonian circuit is constructed. See the readme.txt file within the archive for detailed information.