#2           56. THE FIFTEEN PUZZLE                  

The fifteen puzzle consists of 15 square tiles which are free to slide vertically and horizontally on a 4 x 4 square tray. The tiles are numbered from 1 to 15.

It can be shown that if any pair of tiles is interchanged (for example by lifting tiles 14 and 15 out of the tray and replacing them in opposite positions) then it is impossible to return the tiles to their natural order 1, 2, 3, ... , 14, 15 by sliding. In fact, any odd number of such interchanges gives rise to an impossible sliding puzzle; any even number corresponds to a solvable puzzle.

Now, is it possible to slide the tiles in the second puzzle to give the message correctly?
 Hints and strategies 

Hint 1                       Hint 2                   Solution                      Extensions
HINT 1

The best way to start this problem is to lay hands on an actual puzzle. They are available commercially, and not expensive.
HINT 2

Look at the two puzzles. They are obviously differnt: one is numbers, the other letters. But apart from this, there is a structural difference between the two arrays. Can you see what it is?

(The left hand array is made up of different numbers; ... .)
SOLUTION

Yes, it is possible to obtain the correct message. Simply interchange the positions of A and L, and also the two tiles carrying the letter R. That is, two interchanges, and the puzzle is solvable.

Notice that this is a theoretical solution. It doesn't show you how to actually do it! In fact, it is rather a fiendish puzzle. Few people tackling it are likely to remove the R tile from its initial position in the top left corner.
EXTENSION

1. Investigate the parity properties of permutations. For example, see
http://internal.maths.adelaide.edu.au/people/pscott/groups/gpf/ 

2. Make up your own sliding puzzle with a suitable message.

3. Do you think a sliding 8 puzzle might be successful? Why or why not?