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 Brought to you by Super Global Mega Corp .com