Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!wuarchive!usc!ucsd!ucsdhub!hp-sdd!hplabs!hpfcso!hpldola!paul From: paul@hpldola.HP.COM (Paul Bame) Newsgroups: comp.graphics Subject: Re: Factoring Rubik's Cube Message-ID: <11390025@hpldola.HP.COM> Date: 1 Dec 89 16:22:40 GMT References: Organization: HP Elec. Design Div. -ColoSpgs Lines: 19 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 Brought to you by Super Global Mega Corp .com