From cube-lovers-errors@mc.lcs.mit.edu Mon Aug 18 13:05:48 1997
Return-Path:
Received: from sun30.aic.nrl.navy.mil by mc.lcs.mit.edu (8.8.1/mc) with SMTP
id NAA02085; Mon, 18 Aug 1997 13:05:43 -0400 (EDT)
Precedence: bulk
Errors-To: cube-lovers-errors@mc.lcs.mit.edu
Mail-from: From jbryan@pstcc.cc.tn.us Sun Aug 17 00:42:09 1997
Date: Sun, 17 Aug 1997 00:38:39 -0400 (EDT)
From: Jerry Bryan
Subject: Calculating Local Maxima in Face Turn Metric
To: Cube-Lovers
Reply-To: Jerry Bryan
Message-Id:
While everybody else has been doing isoglyphs and minimal maneuvers for
highly "symmetric" positions, I have been trying to figure out how to
calculate local maxima for the face turn metric with my Shamir program.
It's a bit trickier than with the quarter turn metric, but I think I have
it. If anybody sees any holes in the following, please let me know.
Recall that I have been creating Start-rooted search trees by forming
products of the form z=xy for |x|=n and |y|=m, for 1<=m<=n. Prior to my
Shamir program, I would fix n (it gets larger iteratively), and just let
m=1 to advance one level of the tree at a time. But the Shamir method
lends itself to jumping forward several levels at one fell swoop.
If E(w) is the set of all moves with which a minimal maneuver for w can
end, then E(z) is the union of E(y) over all the y which can be used to
create z. We now introduce an alternative interpretation for E(w). E(w)
is the set of all moves whose inverses carry w one move closer to Start.
The alternative interpretation works for both quarter turns and face
turns.
My program is all set up to calculate E(w) for either the quarter turn
metric or the face turn metric. The only difference is that the
representation of E(w) for the quarter turn metric is a bit string of 12
bits and for the face turn metric is a bit string of 18 bits.
But using E(w) to calculate local maxima for the face turn metric will
yield only what we have agreed to call strong local maxima, namely those
local maxima where every face turn moves one move closer to Start. We
desire also to calculate weak local maxima, where one or more face turns
may leave the distance from Start unchanged. To this end, we define E2(w)
to be the set of all moves whose inverses leave w the same distance from
Start.
For quarter turns, the required initializations are E(q)={q} for all q in
Q, the set of twelve quarter turns. E2(q) is of course null in all cases.
For face turns, the required initializations are:
E(q) = {q} for all q in Q
E(q2) = {q2} for all q2 in H, the set of six half turns
E2{q} = {q',q2} for all q in Q
E2{q2} = {q,q'} for all q2 in H
To be pedantically complete, we could define E3(w) to be the set of all
moves whose inverse leaves w one move further from Start. Note that E(w),
E2(w), and E3(w) are disjoint, and their union is Q for quarter turns and
Q+H for face turns.
For quarter turns, we have defined the maximality of w to be |E(w)|,
wherein we have a local maximum if |E(w)|=12. The corresponding
definition of maximality for face turns is an ordered pair
(|E(w)|,|E2(w)|), where w is a local maximum if |E(w)|+|E2(w)|=18 and
where w is a strong local maximum if |E(w)|=18. (A local maximum which is
not a strong local maximum is a weak local maximum.)
The only thing I am worried about is the following. Given the proposed
initializations and calculations for E(w) and E2(w) for face turns, will
E(w) and E2(w) be disjoint automagically, or is their disjointedness
something which will have to be tested?
= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
Robert G. Bryan (Jerry Bryan) jbryan@pstcc.cc.tn.us
Pellissippi State (423) 539-7198
10915 Hardin Valley Road (423) 694-6435 (fax)
P.O. Box 22990
Knoxville, TN 37933-0990