When it appeared in 1879 as The Gem Puzzle, the 15 Puzzle was accompanied by a cryptic instruction: Place the blocks in the box irregularly, then move until in regular order. At the outset, the applet below shows the 15 blocks in the "regular order". Pressing the "Shuffle" button in combination with the "Cheat" button is a modern day substitute for the block placing instruction. Pressing ether one of the buttons or both of them shuffles the numbers in the box. You move the blocks by clicking in the row or column containing the blank field.

The curious fact about the puzzle is that each configuration of the tiles represents a permutation of 16-element set N₁₆. It is known that every permutation is representable as a product of disjoint cycles. We also know that a cycle of length k can be split into a product of k-1 transpositions. It follows that, if T is the total number of board cells (T = 16 for the Fifteen puzzle), C is a number of disjoint cycles in a permutation, and P is its parity, then

which, in the case of the 15 puzzle, means that the parity of a permutation equals that of the length of its cycle decomposition. This remark serves the basis for one of the first rigorous solutions to the 15 Puzzle. The solution, by William Woolsey Johnson, came out in December 1879.

a product with 15 cycles, which represents an odd permutation. In itself the difference in parities does not imply that one permutation can't be obtained from the other. Each legal move in the puzzle changes the parity of the configuration. However, permutations (1) and (2) share the position of the blank cell, or the tile #16. Assume permutation (1) can be obtained from (2) by legal moves. Each of the moves involves tile #16. Thus as a sequence of transpositions involving tile #16, the latter will have returned to its original position. This is only possible if the number of moves in the sequence was even. (The easiest way to see this is to imagine that the puzzle board was cut off a regular checker board. Then each legal move shifts the empty cell from between cells of different colors. Each second move brings it back to the starting color.)

But an even number of transpositions applied to the permutation (2) will produce a permutation of odd parity, whereas the parity of (1) is even.

References

1. J. Slocum, D. Sonneveld, The 15 Puzzle, The Slocum Puzzle Foundation, 2006

Copyright © 1996-2009 Alexander Bogomolny