Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!watmath!clyde!akgua!sdcsvax!sdcrdcf!hplabs!sri-unix!STORY@MIT-MC
From: STORY%MIT-MC@sri-unix.UUCP
Newsgroups: net.ai
Subject: puzzles and permutation groups
Message-ID: <12527@sri-arpa.UUCP>
Date: Wed, 18-Apr-84 08:27:00 EDT
Article-I.D.: sri-arpa.12527
Posted: Wed Apr 18 08:27:00 1984
Date-Received: Fri, 11-May-84 08:18:57 EDT
Lines: 37

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