From:

Subject:

Date: 31 Jul 1980 16:44 PDT Sender: McKeeman.PA at PARC-MAXC In-reply-to: ALAN's message of 31 July 1980 13:06-EDT From: (Bill) McKeemanA 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.

This is not an improvement on my result. I (and the rest of the cube

hackers I know) consider a unit move to be a 90 degree twist in EITHER

direction. You are only considering CLOCKWISE 90 degree twists.

Let me point out that if we were to count twists your way, we would

no longer have a metric. Both the quarter twist method and Singmaster's

method result in a measure of distance that is a true metric.

Date: 31 Jul 1980 5:13 pm PDT (Thursday) From: Woods at PARC-MAXC Subject: Re: The shortest solution? In-reply-to: McKeeman's message of 31 Jul 1980 16:44 PDT To: CUBE-HACKERS at MIT-MC

You can do better than that for a lower bound! Say you consider all

single-hand-motion twists to be okay. Then yes, there are 18 such,

but there's no point in twisting the same face twice consecutively, so

after the first twist the tree branching factor is only 15. In fact, there's

no point in twisting a face twice if the only intervening twist was done

on the opposite face; if we look at the operations of the form "twist face

X thusly and the opposite face thusly", there are 45 initial such operations,

and 30 at each succeeding branch, but since some branches now represent

two twists and some only one twist, it's much harder to compute the

minimum depth of the tree.-- Don.

Singmaster's notes are aware of these factors, that is how he improves

on the 16 count computed by McKeeman to arrive at 18. Similarly I

used the same factors to improve on the 12^n argument for quarter

twists (which gives 19 as a lower bound) to arrive at the number 21.

I also compute 24 as the quarter twist lower bound for the extended

cube (considering orentations of the center faces).