> < ^ Date: Fri, 18 Aug 1995 10:01:00 +0200
> < ^ From: Joachim Neubueser <joachim.neubueser@math.rwth-aachen.de >
> < ^ Subject: Re: Rubik's Cube

Istvan Hernadvolgyi asked:

I recently downloaded and installed gap. I do not know too much about
the package, but I would like to use it to develop algorithms to solve the
Rubik's Cube and similar puzzles. I would appreciate if someone could
provide a little help, especially if someone already programmed the Cube
or something similar in gap.

The question of course asks to find shortest expressions for a group
element in given generators or equivalently shortest pathes from one
point to another in the Cayley graph of a group. This is known to be
computationally difficult - it falls into one of those nastier
categories of complexity analysis ( I am not an expert on complexity
theory, so do not ask me for more exact terminology). However I know
that there are rather efficient approximative algorithms, one research
group dealing with these are Gene Cooperman and Larry Finkelstein at
Northeastern University, Boston, MA. who say that they have methods by
which they can obtain solutions close to or even better than the best
ones known.

Gene and Larry, can you perhaps comment directly in the Forum?

Reagards Joachim Neubueser

> < [top]