Date: 31 Jul 1980 16:44 PDT
Sender: McKeeman.PA at PARC-MAXC
Subject: Re: The shortest solution?
In-reply-to: ALAN's message of 31 July 1980 13:06-EDT
To: Alan Bawden
From: (Bill) McKeeman
cc: CUBE-HACKERS at MIT-MC, Lynn.ES
A lower bound on the number of twists can be derived as follows: There are
4.3*10^19 distinct reachable arrangments of the cube. Suppose the moves are
restricted to the (more than sufficient) set RLFBUD. Then there are at most six
independent choices at each step and the number of reachable places is bounded
by 6^n. That gives
6^25 < 4.3*10^19 < 6^26,
or 26 moves as the (probably unachievable) minimum. If all single-hand-motion
twists, R RR RRR L LL .... DDD are allowed, there are 18 choices, giving
18^15 < 4.3*10^19 < 18^16,
or 16 moves as a minimum. This isn't very interesting since Singmaster has
examples 18 twists away. If the orientation of the center squares is also
considered, then the combinatoric is 8.8*10^22, and the minima are, respectively,
30 and 19.