STORY%MIT-MC@sri-unix.UUCP (04/18/84)
From: Kenneth Byrd Story <STORY @ MIT-MC>
[Forwarded from the MIT bboard by Laws@SRI-AI.]
DATE: Thursday, April 19, 1984
TIME: Lecture, 4:00pm
PLACE: NE43-512a
``Generalized `15-puzzles' and the Diameter of Permutation Groups''
Dan Kornhauser
MIT
Sam Lloyd's famous ``15-puzzle'' involves 15 numbered unit squares free to move
in a 4x4 area with one unit square blank. The problem is to decide whether a
given rearrangement of the squares is possible, and to find the shortest
sequence of moves to obtain the rearrangement when it is possible.
A natural generalization of this puzzle involves a graph with @i(n) vertices,
and @i(k<n) tokens numbered @i(1,...,k) on distinct vertices. A legal move
consists of sliding a token from its vertex to an adjacent unoccupied vertex.
Wilson (1974) obtained a criterion for solvability for biconnected graphs and
@i(k=n-1). No polynomial upper bound on number of moves was given.
We present a quadratic time algorithm for deciding solvability of the general
graph problem. It is also shown that @i[O(n@+{3})] move solutions always exist
and can be efficiently planned. Further, @i[O(n@+{3})] is shown to be a
matching lower bound for some graph puzzles.
We consider related puzzles of the Rubik's cube type, in the context of the
general permutation group diameter question.
This is joint work with Gary Miller, MIT, and Paul Spirakis, NYU
HOST: Professor Silvio Micali