Date: Thu, 23 Sep 82 12:06:00 -0400 (EDT)
From: Dan Hoey <Hoey@CMU-10A >
~~~ ~~~ Subject: MegaMinx and orientation theory

analyzed this puzzle with the FHL algorithm. It was the longest
run of that algorithm that I have heard of, something like 20 CPU
hours. Necessity was the mother of checkpointing.

The standard MegaMinx has 20 corners and 30 edges. Both the edge
and corner permutation parities must be even. Corner and edge
orientation parities are zero (mod 3) and (mod 2), respectively.
These are the only invariants, so there are twenty-four orbits and
(20! 3^20 30! 2^30)/24 ~ 1.007E68
positions. In the SuperMegaMinx, a 1/5 twist of a single face
center is possible, so there are
(20! 3^20 30! 2^30 5^12)/24 ~ 2.458E76
positions. I think the MegaMinx is going to be easier than Rubik's
Revenge, not because there is more carryover from the cube, but
because there is more of the puzzle that is not affected by a
single generator. Computing a lower bound that takes account of
generators that commute is going to be difficult, however: there
are triples of commuting generators, and we can find commuting
triples {A, B, C} and {A, B, D} such that C and D do not commute.

A curious question: What do we mean by the corner orientation of
the MegaMinx when the corner permutation is not the identity? On
the cube, we took the corner colortabs on two opposite faces of a
solved cube and marked both the tab and its position. Then in a
scrambled cube we counted the position of each marked corner
colortab relative to the marked position on its cubie. This
procedure doesn't work on the dodecahedron: where should we mark
the tabs on those corner cubies that are not on the two opposite
faces?

It was a year before I realized that the choice of placing the
marks on opposite faces of the cube was arbitrary. The marked tabs
and positions can be chosen any way that gives us one marked tab
and one marked position per cubie, and has zero orientation parity
in a solved cube. It is customary to enforce the second criterion
by requiring that marked positions be the positions of marked tabs
in a solved cube. The same argument holds for edges, and both
generalize to the MegaMinx.

Why is there orientation parity? When we twist an n-gon face, the
edge cubies move in an n-cycle and their colortabs move in two
n-cycles. We call this an ``untwisted cycle''. But we could
conceive (see below) of a puzzle where the edge colortabs would
move in a single 2n-cycle. This would be a ``twisted cycle'', and
would violate orientation parity. Similar arguments hold for
corner cubies, whose kn tabs must move in k n-cycles rather than
k/d nd-cycles, for d a divisor of k (note that k=4 for the
icosahedron (but the icoshahedron has two corner tab orbits, so
quite a different argument applies)). To summarize, any puzzle
that moves pieces in untwisted cycles must preserve orientation
parity.

I wonder if some argument of this type can be made for the
tesseract. The argument depends on the orientation group being
Abelian (it has in fact been cyclic in our examples), and at least
some of the hypercubies have nonabelian orientation groups.
Perhaps we have to use Abelian quotients of the orientation groups.
Has anyone seen the paper on the tesseract that was mentioned by
Hofstatder?

Retreating to three dimensions, let's consider a variant on Rubik's
cube. Suppose you had a gear (heh) embedded in the URF and BLD
corners, such that whenever an edge cubie passed by one of these
corners (e.g. from UR to UF by twisting U) it would flip (go from
UR to FU). This would violate EOP on every quarter-twist! Of
course, you know what positions would be possible in such a puzzle.
So now let's consider gears in the FU, BL, and RD edges that twist