Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: notesfiles - hp 1.2 08/01/83; site hp-pcd.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!mhuxl!houxm!hogpc!houti!ariel!vax135!cornell!uw-beaver!tektronix!hplabs!hp-pcd!btc
From: btc@hp-pcd.UUCP
Newsgroups: net.math
Subject: Wanted: Solution to kids puzzle
Message-ID: <6100006@hp-pcd.UUCP>
Date: Tue, 17-Jul-84 15:13:00 EDT
Article-I.D.: hp-pcd.6100006
Posted: Tue Jul 17 15:13:00 1984
Date-Received: Fri, 20-Jul-84 03:10:00 EDT
Organization: Hewlett-Packard - Corvallis, OR
Lines: 25
Nf-ID: #N:hp-pcd:6100006:000:747


Nf-From: hp-pcd!btc    Jul 17 11:13:00 1984





When I was a kid we used to have puzzles consisting of 15 tiles
placed in a 4X4 matrix.  The problem was to rearrange the tiles
to form a given pattern by moving tiles into the empty space.

What I want to know is how can one tell if a given starting position
has a solution.  That is, if the tiles are labled 1,2,...,15, and
randomly placed into positions p(i,j) (i,j=1,2,3,4) of the matrix P,
can you tell if the tiles can be moved to a given configuration.  Say
in ascending order from left to right starting at p(1,1) {row 1, col 1}.

I can't imagine that this hasn't been solved, so a reference will do
just fine.

Thanks in advance.



				Bob Clark
				Hewlett-Packard PCD
				Corvallis, OR

			{ucbvax!hplabs, harpo, ogcvax}!hp-pcd!btc