From:

~~~ ~~~ Subject:

Oops... you have just received part 3. This is part 1....

This note is in somewhat delayed response to the note by

David C. Plummer (31 DEC 1980 1115-EST) regarding the 5x5x5 Rubik

cube, and some related ideas. In that note he tried to calculate

the size of that cube's Rubik group, but left several of the values

open to conjecture. I will complete the answer, and answer a few

others that haven't been addressed here.

Computing the size of a Rubik group is a special case of

computing the size of a permutation group, given generators for

that group. The technique we have already seen in these pages is in

two parts. The first part seems relatively easy: certain invariants

must be observed in the generators, such as "Corner Orientation

Parity" and "Total Permutation Parity." [In this general setting,

such invariants as "Colortabs on the same cubie move together" must

also be considered.] It may take some thought to dig out the

invariants, but once you have seen them demonstrated for Rubik's

Cube, you have an idea of what to look for. The second part is the

devil: it must be demonstrated that every permutation satisfying

those invariants is actually generated. This involves developing a

solution method for the puzzle. Given the days or weeks (or

eternity) it takes most people to develop such a method--with cube

in hand!--it is hardly surprising that few answers have been

developed.

Well, the second part is no longer a hard problem. The

answer lies in a paper by Merrick Furst, John Hopcroft, and Eugene

Luks, entitled "Polynomial-Time Algorithms for Permutation Groups,"

which was presented at the 21st Annual Symposium on Foundations of

Computer Science, October 1980. Among the results is an algorithm

which takes as input a set of permutations on n letters, and

reports the size of the group G which is generated by those

permutations.

The algorithm operates by decomposing G into a tower of

groups I=G[0], G[1], ..., G[n]=G, where G[i] contains those

permutations p in G for which p(k) = k whenever i < k <= n. The

index of G[i-1] in G[i] is developed explicitly by the algorithm;

in fact, a representative g[i,j] of every coset of G[i-1] in G[i]

is exhibited. These coset representatives generate G; in fact,

every element of G is representable as a product of the form

(g[1,j1])(g[2,j2])...(g[n,jn]). For this reason the coset

representatives are called "strong generators" for G. There is a

good deal of structure that can be learned from the strong

generators, in addition to the size of G.

I have coded this algorithm in Pascal, and offer the

program for the use of anyone who needs to find group orders. The

relevant files are on CMU-10A, from which other sites may FTP

without an account. The relevant files are

all:group.pas[c410dh51] The source

all:rubik.gen[c410dh51] A sample input -- the supergroup

all:rubik.lst[c410dh51] Sample output.

Of course, CMU Pascal is probably slightly different from yours,

and OS-dependent stuff like filenames is likely to be wrong. I'll

be glad to help out in cases of transportability problems. The

other problem you may run into is resource availability. The

running time of the algorithm is proportional to (nm)^2, where m is

the total number of strong generators; the supergroup (n=72, m=279)

takes 639 cpu seconds on a KL-10, and bigger problems grow rapidly.

The program also requires 47000+47m words.

It might seem that the problem has been answered, but I

find that simply knowing the size of a group is not very

satisfying. There doesn't seem to be a better way of demonstrating

lower bounds, but the upper bounds that come from invariants are

much more elegant than a simple numerical answer. Unfortunately, I

know of no mechanical way of finding the invariants. Furthermore,

using group theory does not help much when we ignore the

Supergroup. Consider the 4x4x4 cube. If we are only concerned with

the color pattern on the cube, then a twist may or may not affect

the four face centers--it depends on whether they are the same

color or not.

In summary, the algorithm has inverted the hard and easy

parts of cube analysis. The size of the group is now easy to

determine, making invariant-finding the hard part. Further, the

algorithm works on the Supergroup, making counting distinct color

patterns the part which requires further analysis. Two messages

follow, supplying these answers for the 4x4x4 and 5x5x5 cubes.