[net.math] Wanted: Solution to kids puzzle

btc@hp-pcd.UUCP (07/17/84)

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

gwyn@brl-tgr.ARPA (Doug Gwyn <gwyn>) (07/19/84)

A position in the "15" puzzle is realizable if and only if it
is an even permutation of the starting position.

brian@digi-g.UUCP (Brian Westley) (07/23/84)

There is a 50% chance that a random order of the 1-15 tiles will be
solvable.  This has to do with the parity of the tiles.  A very
devious variant is as follows:  instead of numbers, the tiles read -
RATE
YOUR
MIND
PAL
with RATE YOUR in red tiles and MIND PAL in white.  Show this to your
victim, and scramble the letters - but, put the 'R' in YOUR in the
upper left hand corner as you mix them up!  He will naturally leave
it there to spell RATE - but the parity is wrong!  The best he can do
is RATE YOUR MIND PLA... (from one of Martin Gardner's many books)