|
|
|
|
|
|
|
|
|
Sam Loyd's FifteenWhen 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 N16. 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
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. The cycle representation of the tiles in regular order consists solely of unicycle, i.e. 1-element cycles:
where the last tile (#16) stands for the blank cell. The number of cycles in its representation is 16, an even number. In other words the parity of the "regular order" is even. There are of course odd permutations. One of these is obtained by swapping tiles 14 and 15:
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. Additional puzzle information.References
Copyright © 1996-2008 Alexander Bogomolny |
| 28765968 |  |
|