From ACW@yukon.scrc.symbolics.com Mon Jan 13 22:03:15 1992 Return-Path: Received: from YUKON.SCRC.Symbolics.COM by life.ai.mit.edu (4.1/AI-4.10) id AA21059; Mon, 13 Jan 92 22:03:15 EST Received: from PALLANDO.SCRC.Symbolics.COM by YUKON.SCRC.Symbolics.COM via INTERNET with SMTP id 761285; 13 Jan 1992 14:40:58-0500 Date: Mon, 13 Jan 1992 14:38-0500 From: Allan C. Wechsler Subject: Re: Rubik's Cube, the minimax number of moves To: hoey@aic.nrl.navy.mil, tjj@lemma.helsinki.fi, Cube-Lovers@life.ai.mit.edu In-Reply-To: <9201102332.AA13941@sun13.aic.nrl.navy.mil> Message-Id: <19920113193832.8.ACW@PALLANDO.SCRC.Symbolics.COM> I would like to see us develop a programming language for expressing cube-solving algorithms in. Then we could cooperate in trying to find an algorithm with smaller and smaller numbers of moves in the worst case. I just completed an exercise I have wanted to try for a while, a rough worst-case analysis of my own technique. It's pretty scary. It turns out that my worst case is 236 qtw. My algorithm is "bottom-heavy" -- it starts with "intuitive" moves for fixing the first few corners. These were the hardest to analyze, but they take the fewest moves. It finishes up with great big macros for the last few fiddles and fixes. For example, flipping two edges in place takes 22 qtw. Obviously a lot could be gained from tweaking the earlier part of the algorithm to guarantee that I don't need to do this at the end.