[next] [prev] [up] Date: Thu, 31 Jul 80 21:59:00 -0400 (EDT)
[next] [prev] [up] From: Alan Bawden <ALAN@MIT-MC >
[next] [prev] [up] Subject: The shortest solution?
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) McKeeman

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.

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).


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