15 Puzzle

A puzzle introduced by Sam Loyd in 1878. It consists of 15 squares numbered from 1 to 15 which are placed in a $4\times 4$ box leaving one position out of the 16 empty. The goal is to rearrange the squares from a given arbitrary starting arrangement by sliding them one at a time into the configuration shown above. For some initial arrangements, this rearrangement is possible, but for others, it is not.

To address the solubility of a given initial arrangement, proceed as follows. If the Square containing the number $i$ appears ``before'' (reading the squares in the box from left to right and top to bottom) $n$ numbers which are less than $i$, then call it an inversion of order $n$, and denote it $n_i$. Then define

$$N\equiv\sum_{i=1}^{15} n_i = \sum_{i=2}^{15} n_i,$$

where the sum need run only from 2 to 15 rather than 1 to 15 since there are no numbers less than 1 (so $n_1$ must equal 0). If $N$ is Even, the position is possible, otherwise it is not. This can be formally proved using Alternating Groups. For example, in the following arrangement

$n_2=1$ (2 precedes 1) and all other $n_i=0$, so $N=1$ and the puzzle cannot be solved.

References

Ball, W. W. R. and Coxeter, H. S. M. Mathematical Recreations and Essays, 13th ed. New York: Dover, pp. 312-316, 1987.

Bogomolny, A. ``Sam Loyd's Fifteen.'' http://www.cut-the-knot.com/pythagoras/fifteen.html.

Bogomolny, A. ``Sam Loyd's Fifteen [History].'' http://www.cut-the-knot.com/pythagoras/history15.html.

Johnson, W. W. ``Notes on the `15 Puzzle. I.''' Amer. J. Math. 2, 397-399, 1879.

Kasner, E. and Newman, J. R. Mathematics and the Imagination. Redmond, WA: Tempus Books, pp. 177-180, 1989.

Kraitchik, M. ``The 15 Puzzle.'' §12.2.1 in Mathematical Recreations. New York: W. W. Norton, pp. 302-308, 1942.

Story, W. E. ``Notes on the `15 Puzzle. II.''' Amer. J. Math. 2, 399-404, 1879.