[next] [prev] [up] Date: Mon, 13 Jan 92 14:38:00 -0500
[next] [prev] [up] From: Allan C. Wechsler <ACW@yukon.scrc.symbolics.com >
~~~ [prev] [up] Subject: Re: Rubik's Cube, the minimax number of moves

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.


[next] [prev] [up] [top] [help]