[next] [prev] [up] Date: Fri, 28 Jan 83 03:33:00 -0500 (EST)
[next] [prev] [up] From: Dan Hoey <HOEY@CMU-CS-A >
[next] ~~~ [up] Subject: The shortest sequence of moves.

Leonard,

The process (R U^2 B^2 L')^2 will restore your cube in twelve
quarter-twists when executed with the Green face Up and the White face
Front, and twelve is the minimum sufficient number of quarter-twists.

Dave Plummer's discouraging word is usually right--we know of no
algorithm to let us find optimal processes for most positions. This is
because the only known algorithms involve exhaustive breadth-first
search, and there are far too many positions of the cube to make this
practical in either time or space. But when the optimal process is
sufficiently short, some headway can be made. Having some megabytes
and CPU-hours at my disposal, I was able to list
(A) all positions reachable in five qtw from your cube, and
(B) all positions reachable in five qtw from SOLVED.
Finding that sets (A) and (B) are disjoint, I conclude that there is no
ten qtw process for the pattern, so the twelve qtw process is optimal.

I discovered the optimal process by hand. Of course, I could have just
run the program one more qtw and it would give me the process, along
with any other twelve-qtw processes that may exist. The problem with
that approach is that I don't have that many megabytes and CPU-hours.

My program, by the way, is written in C and runs under Unix. It trades
time and storage efficiency for programmer laziness, making extensive
use of the Unix sort utility. Dave Plummer has written a much
optimized program, in assembler language for the PDP-20, that uses very
clever hacks (some of them my own). As I recall, he and I estimated
that with about 150 megabytes and a day or two elapsed time on an
unloaded machine it could take the search three more quarter-twists.
Does anyone need to settle a bar bet on an eighteen qtw process?

Dan


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