From: mgv@cs.scarolina.edu (Marco Valtorta)
Subject: Re: 8 Puzzle (Is it connected)
Organization: USC  Department of Computer Science
Date:  7 Sep 92 18:05:37 GMT

ginsberg@t.Stanford.EDU (Matthew L. Ginsberg) writes:

>In article <babraham.3.715849833@unpcs1.cs.unp.ac.za> babraham@unpcs1.cs.unp.ac.za (Bobby Abraham) writes:
>>I recently gave the 8 puzzle to an Intro AI class.  I remember reading that 
>>the 15 puzzle was not solvable from any position.  In other words the graph 
>>of this problem was not connected.
>>
>>Can anyone tell me if the same applies to the 8 puzzle?  I would be 
>>interested in the proof as well.

>None of these puzzles is connected.  If you consider the blank a tile,
>each legal move swaps two tiles and therefore obviously retains the "parity"
>of the overall position.

>					Matt Ginsberg

A while ago, Torben Mogensen gave the argument in more detail.  (What follows
is e-mail he sent me relating to his posting, rather than his actual posting
to comp.ai.)

For the trivia enthusiast, the argument was first made by William E. Story in
Woolsey Johnson, Wm. and William E. Story.
"Notes on the "15" Puzzle."
_American Journal of Mathematics, 2 (1879), 397-404.

Marco Valtorta, Assistant Professor	usenet: ...!ncrcae!usceast!mgv
Department of Computer Science	internet: mgv@usceast.cs.scarolina.edu
University of South Carolina	tel.: (1)(803)777-4641
Columbia, SC 29208		tlx: 805038 USC
U.S.A.				fax: (1)(803)777-3767
usenet from Europe: ...!mcvax!uunet!ncrlnk!ncrcae!usceast!mgv

*******************************************************************************

From torbenm@freja.diku.dk Thu Oct 10 06:18:26 1991
Received: by usceast.cs.scarolina.edu (cs.grandpoobah.022591)
Received: by freja.diku.dk id AA06723
  (5.65+/IDA-1.3.5 for mgv@usceast.cs.scarolina.edu); Thu, 10 Oct 91 11:18:02 +0100
Date: Thu, 10 Oct 91 11:18:02 +0100
From: Torben AEgidius Mogensen <torbenm@freja.diku.dk>
Message-Id: <9110101018.AA06723@freja.diku.dk>
To: mgv@usceast.cs.scarolina.edu
Subject: Re: Re: Tiled Puzzle Problem for 2x2 or 5x5 square
Status: RO


>Could you please sketch the argument or give a reference to the proof
>of the result?

The argument I gave you was actually slightly incomplete: it requires
that the empty space is in the same position in the initial and final
states. Or, more precisely, that the empty space is an even number of
squares away from the initial position (the initial and final squares
would have the same colour on a chess board).

The proof goes like this:

1) A single move is an exchange between the empty space and one other
   piece.

2) The empty space will, in a single move, change from a black square
   to a white or vice versa.

3) Thus any sequence of moves that leaves the empty space on the same
   colour will have to be even.

4) An even number of moves corresponds to an even number of exchanges
   of pieces (including the empty space).

5) This can be seen from a result about permutations, stating that if
   the permutation can be achieved by an even number of exchanges, no
   odd number of exhanges will achieve the same permutation (and vice
   versa). The permotation is said to have even or odd parity.

Thus, a solution exist if the empty space starts and ends on the same
colour and an even number of exchanges is required or the empty space
starts and ends on opposite colours and an odd number of exchanges is
required.

	Torben Mogensen (torbenm@diku.dk)
Xref: sparky comp.ai:3393 comp.ai.shells:428 comp.robotics:1751 comp.ai.neural-nets:3432