[next] [prev] [up] Date: Sun, 01 Feb 81 05:39:00 -0500 (EST)
[next] [prev] [up] From: Dan Hoey <Hoey@CMU-10A >
~~~ ~~~ [up] Subject: Algorithm for finding cube group orders

David C. Plummer (31 Dec 1980 1210-EST) gave a preliminary
analysis of the 5x5x5 cube. I complete it here. Let a move consist
of twisting any of the six faces, at a depth of 1 or 2. It will be
necessary to consider the two depths as distinct; M1P will refer to
the number of depth 1 moves (mod 2), while M2P will refer to the
number of depth 2 moves (mod two). It is important to realize that
the two parities vary independently. The tabs on each face are
assigned types
as in Plummer's analysis.

Let COP ("C" Orientation Parity) and CPP ("C" Permutation)
parity be defined as before. As before, COP=0 (mod 3). We must be
explicit about the CPP this time: Since either kind of move is an
odd permutation of the "C" faces, CPP=M1P+M2P.

As in the 4x4x4 case, "R"'s may be ignored and "L"'s have
no orientation. The permutation parity (LPP) is important, however.
Depth 1 moves are an even permutation of the "L"'s (two 4-cycles),
so they do not affect the LPP, but Depth 2 moves are an odd
permutation of the "L"'s (three 4-cycles). Therefore LPP=M2P. Note
that while LPP and CPP may vary independently, they together
determine both M1P(=LPP+CPP) and M2P(=LPP).

The "E" faces act as in the 3x3x3 case, with orientation
and permutation parity. Orientation changes on four "E"'s with
every move, so EOP=0 (mod 2). Permutation parity changes with every
move, so EPP=M1P+M2P. This has already been determined by CPP, so
only half of the "E" permutations are possible.

Every move is an odd permutation of the "D" faces, so
DPP=M1P+M2P. Since M1P+M2P=CPP is determined, only half of the "D"
face permutations are possible.

Moves work differently on "A" faces depending on depth:
Depth 1 moves are odd permutations of the "A"'s, and depth 2 moves
are even. Thus APP=M1P, which is determined by CPP+LPP, so only
half of the "A" permutations are possible.

Finally, the "X" faces have orientation which changes on
every move, so XOP=M1P+M2P, and only half of the "X" orientations
are possible.

Thus there are 96 orbits, corresponding to COP (mod 3) and
EOP, EPP+CPP, DPP+CPP, APP+CPP+LPP, and XOP+CPP (mod 2). The basic
combinatoric is as Plummer described:
8! C Permutations
3^8 C Orientations
24! L Permutations
1 R Permutation
12! E Permutations
2^12 E Orientations
24! D Permutations
24! A Permutations
4^6 X Orientations
which when multiplied together and divided by 96 yields about
5.289*10^93. [This differs from Plummer's result by a factor of
4096 because (4^6/2) he didn't count X Orientations, and (2) he did
not realize that LPP and CPP are independent.] My implementation of
Furst's algorithm claims that all of these are reachable.

To count the number of reachable color patterns, divide this note
that there are by (4!)^6/2 invisible D permutations, (4!)^6/2
invisible A permutations, and 4^6/2 invisible X orientations that
satisfy the invariants. While there are pairs of L/R edges that
look the same, they cannot be interchanged, for that would entail
putting an L tab into an R position. So there are 2.829*10^74
different color patterns achievable.


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