[next] [prev] [up] Date: Wed, 07 Jan 81 13:52:00 -0500 (EST)
[next] [prev] [up] From: Dan Hoey <Hoey@CMU-10A >
~~~ ~~~ [up] Subject: Pons Asinorum -- Part 1: Optimality

The Pons Asinorum (obtained by UUDDFFBBLLRR, and known as
6-X in Singmaster) is well-known to readers of this list. It is
perhaps surprising that this so well-known position has anything
more to teach us.

The first surprise is that the 12-move sequence given above
is provably optimal in the quarter-twist metric. Proofs were sent
to me by David C. Plummer, who attributed it to Alan Wechsler, and
by Chris C. Worrell. While it is well-known (See Alan Bawden's
messages of 31 July 1980 13:06-EDT and 31 JUL 1980 2159-EDT) that
some positions require at least 21 moves, the longest sequence
which has previously been proven optimal is LR'FB'DU'LR' for the
six-spot configuration. It is good to see a 12-move sequence
proven optimal -- and in a way not dependent on the vagaries of
programming errors and cosmic rays.

The proof of optimality relies on the "Oriented Distance
from Home" (ODH), used by Vanderschel (6 Aug 1980 1909-PDT) in his
proof of edge orientation parity conservation. The ODH of an edge
cubie (in some position and orientation) is defined to be the
minimum number of quarter-twists required to move that cubie to its
home position and orientation. A table of possible ODH values of
the UF cubie is given below, indexed by the position of that
cubie's F tab.

+ 3 +
2 U 2
+ 3 +
+ 1 +   + 0 +   + 1 +   + 2 +
2 L 2   1 F 1   2 R 2   3 B 3
+ 3 +   + 2 +   + 3 +   + 4 +
+ 3 +
2 D 2
+ 3 +

The Pons Asinorum moves every edge cubie to a position and
orientation which has an ODH of 4. To move all twelve cubies in
this way requires a total of 48 edge moves, and only four edge
moves can be accomplished by each quarter-twist. Thus the Pons
Asinorum requires twelve quarter-twists.

Unfortunately, this seems to be the only really impressive
result to be derived from counting ODH. All edges flipped
(Singmaster's 12-Flip) can be shown to require at least ten
quarter-twists, but this is a far cry from the 28-qtw process which
is the best known (Plummer, 10 Dec 1980 0157-EST). A brute force
technique for deriving such results is of course possible, but to
show a twelve-move lower bound seems to require sorting and merging
two lists of over one hundred thousand positions each, an act which
is viewed as unsociable (or, more usually, impossible) on the
systems to which I have access. Anyone who has a gigabit to spare
should get in touch -- there are several good problems for which
brute force seems attractive if there is enough of it.

Surprise number two -- Pons Asinorum in the Supergroup -- in
an hour or two.

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