Conference rusure::math

694.0. "Fifteen puzzle" by BIRMVX::TURRELL (I'd rather be sleeping!) Tue Apr 28 1987 09:22

	Hi,
   Am looking for some assistance. In order to gain familiarity with the smg$
RTL I have written a simple program to demonstrate the "fifteen" puzzle. 
   My problem lies in the initial placement of the numbers. I seem to remember 
that if the numbers are placed randomly then they will reduce to one of the two
solutions :-

		  1				  2
	:-------------------:		:-------------------:
	:  1 :  2 :  3 :  4 :		:  1 :  2 :  3 :  4 :
	:-------------------:		:-------------------:
	:  5 :  6 :  7 :  8 :		:  5 :  6 :  7 :  8 :
	:-------------------:		:-------------------:
	:  9 : 10 : 11 : 12 :		:  9 : 10 : 11 : 12 :
	:-------------------:		:-------------------:
	: 13 : 14 : 15 :    :		: 13 : 15 : 14 :    :
	:-------------------:		:-------------------:

   a) Is this indeed the case?

   b) If so is there a simple method of determining which solution set a 
randomly generated array is in?

   Any input gratefully received.

		Pete_T

    The puzzle will indeed reduce to one of those two solutions.  I'm
    not sure about my answer to the second question, but someone will
    correct me if I'm wrong.  I believe if you solve the puzzle by swapping
    pairs of tiles (without regard to their position), and count the
    number of pairs that you swapped, the solution that a position will
    reduce to depends on whether you swapped an even or odd number of
    pairs.
    				Jeff
    

    From "Sliding Piece Puzzles," Edward Hordern, Oxford Univ.
    Press, 1986 (This is *the* book to get if you are interested
    in these puzzles):

    The simplest way of determining whether a random pattern of
    the pieces is solvable or not is simply to count the number
    of exchanges necessary to get the pieces into their correct
    positions.  If the count is even, it is solvable; if it is
    odd, it is impossible.