> < ^ Date: Thu, 12 Oct 1995 18:20:00 -0500 (CDT)
^ From: John Pliam <pliam@imafs.ima.umn.edu >
> < ^ Subject: Re: Rubik's Cube

In January of 1994, I wrote a small package for describing elements of a
permutation group in terms of its generators. There were some inefficiencies,
and the results were far from optimal, but it gives reasonable results, and
reasonably quickly. For example, for Rubik's Cube, it takes less than a minute
to "familiarize itself" with the cube. After this, I chose a random element
of the group, and ask for the solution. The calculations took .017 seconds.
The solution involved about 1200 moves. The worst case has about 1575 moves.
Much better than the 500,000 mentioned, but far short of optimal. I used
another routine to find a shorter version of the solution. This gives a
further reduced word, but it is still not optimal. In my last run, 85 seconds
of "Shrinking" gave a word of length 135. Of course, the timing results are
machine dependent. I am using a Sun workstation.

I placed the package in /pub/incoming at
ftp@samson.math.rwth-aachen.de with the non-obvious name of AbStab. (This
is for "Abstract Stabilizer Chains.")

I haven't heard comments about it, and was curious as to if anyone has
used it, or if it has been moved to another location.


Hi, How's it going? I saw this on the Gap forum and was wondering what
is the worst case minimum # of moves (diameter of the Cayley graph)?
Does anyone know? I have read claims of like 50?

I have become interested in this again, because of applications to routing
in parallel archectures (I actually found papers using the Schreier thm.
in eng. journals :-)

John Pliam

> < [top]