shivers@cs.cmu.edu (Olin Shivers) (11/30/89)
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
paul@hpldola.HP.COM (Paul Bame) (12/02/89)
I once read somewhere that theoretically the Rubik's cube is never more than about 17 "moves" from solution - I don't know if a "move" was just a quarter turn or any number of turns of a single face. Has anyone a reference to an algorithm which approaches this number of moves - or a good tree-pruning heuristic even? Humans seem to solve the cube by a "subroutine" approach where we know how to move a particular (small) set of pieces a certain way without disturbing the rest of the "finished" cube. As solution is approached, these subroutines become longer because of the difficulty of not messing up the increasing "finished" portion of the cube. This seems non-optimal but I never came up with a heuristic I thought would work. Though since I didn't program it at the time, maybe some would've worked but didn't because of my fatigue due to computing them :-) -Paul Bame 719 590 5557 paul@hpldola.hp.com ...!hplabs!hpldola!paul
prem@geomag.fsu.edu (Prem Subrahmanyam) (12/06/89)
I would STRONGLY suggest using one of the solutions to Rubik's Cube books. There was at least one that presents a concise algorithm for solving the cube depending on its initial state, with a few branches here and there depending on results from previous moves. The one I'm referring to (I can't remember the title) was written independent of the color-coding scheme of the faces, thus it was independent of the "brand" of cube you were solving. ---Prem Subrahmanyam
Chris_F_Chiesa@cup.portal.com (12/10/89)
> > I would STRONGLY suggest using one of the solutions to Rubik's Cube > books. There was at least one that presents a concise algorithm for > solving the cube depending on its initial state, with a few branches > here and there depending on results from previous moves. The one > I'm referring to (I can't remember the title) was written independent > of the color-coding scheme of the faces, thus it was independent of > the "brand" of cube you were solving. > ---Prem Subrahmanyam Forgive me if this has already been posted; I'm progressing serially through back news articles... The book described above, may be (sure agrees with MY copy of) The Simple Solution to Rubik's Cube by James G. Nourse. Published in 1981 by Bantam books... very small paper- back, almost a pamphlet.