Path: utzoo!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!tut.cis.ohio-state.edu!pt.cs.cmu.edu!andrew.cmu.edu!+
From: shivers@cs.cmu.edu (Olin Shivers)
Newsgroups: comp.graphics
Subject: Factoring Rubik's Cube
Message-ID:
Date: 30 Nov 89 01:05:32 GMT
Organization: Carnegie Mellon, Pittsburgh, PA
Lines: 20
Solving Rubik's Cube can be cast as an instance of a general problem:
given a group generated by some finite set of elements G, and some
element e of the group, factor e into a product of the generators:
e = g1 * g2 * ... * gn.
In Rubik's cube, the group is given by 6 generators: the rotation of each
external face by a quarter-turn clockwise, for instance. If you
can factor some random position into a product of these guys (applied
to the start state), then you just reverse the factoring to solve the cube.
Merrick Furst, a CMU professor, has an algorithm that will do this in
time O(N^6) where N is the number of generators. Basically, you have
an NxN matrix; each row describes an orbit in the group. The factoring
process moves down through successive sub-orbits. I don't have a reference
for the algorithm, but you might ask Merrick: furst@cs.cmu.edu.
It's been 6 years since I saw the algorithm described, so I might be
fuzzy on details. It's not complicated to write, though; it's a
rather simple program once you see the idea.
-Olin