Return to my Puzzle pages
Go to my home page

The 15 Puzzle

© Copyright 2000, Jim Loy

The 15 Puzzle is the classic sliding block puzzle, by Sam Loyd, perhaps the greatest of all puzzle creators. He originally called it the "Boss Puzzle," and later called it the "15-16 Puzzle." In general, you mix up the numbered blocks and then try to rearrange them back in the original order (the left side of this diagram). You can only slide the blocks; you cannot remove a block from the puzzle. Loyd's original instructions were to start with the arrangement on the left, and rearrange the blocks to end up with the second arrangement in that diagram (switching the 14 and the 15). He tried to get a patent for this puzzle, but the U.S. Patent Office demanded the solution. Loyd admitted that there was no solution; the puzzle is impossible. So the Patent Office refused to grant him a patent.

So there are two puzzles here, the possible puzzle (mix up the pieces by sliding them around, and then solve the puzzle), and the impossible puzzle as originally composed by Sam Loyd.

The possible puzzle:

Solving the possible version (rearranging a mixed position back to the original position) is not difficult, once you are used to it. The general solution is to return the top row to its original order (one block at a time), then the second row, then the third row. Then the difficult part of the puzzle is usually the fourth row. You have to mix up the third row to rearrange the fourth row. I'll show you how to do that in a second. There are faster solutions, in which you rearrange several blocks simultaneously. But these methods require some creativity, and are not easily describable. So I will just describe the general solution.

Here (on the right) we have solved the first row, except for the four. We move the empty square to under the 1 (as shown in the second part of the same diagram). We then move the 1 down, the 2, 3, and 11 to the left. Then we move the 4 up. Then we move the 7 to the right (moving the empty square to under the 11). Then we move the 11 down and then 1, 2, and 3 back to their final position, completing the first row. This normally must be done for every row, of the first three rows of the puzzle.

Finally, we have to deal with the last row. We probably have the situation on the left here. Now we just rotate those two bottom rows a couple of times, arriving at the third position in this diagram. We can then move the 13 up, the 14 to the left, and the 15 down. Then we move the third row back into place (9, 10, 11, 12). And the puzzle is solved.

The impossible puzzle:

Starting from the diagram at the top of this article, there are many positions that can be produced. There are the same number of positions that cannot be produced. This situation is an example of mathematical parity (See Dominoes On a Checker Board). If the original position has even parity, then the impossible positions (including Sam Loyd's original target position) have odd parity. The moves on the board never change the parity.

To begin, we must study the simple 2x2 puzzle on the right. The second position can never be produced from the first position. The left position can be called 1-2-3, ignoring the blank square. From there we can get 3-1-2, and 2-3-1. The three positions that we can never get are 1-3-2, 2-1-3, and 3-2-1. Those six are all of the possible permutations. And so there are only two sets of distinct arrangements. Notice that switching any pair of sliding blocks is impossible, and it reverses the parity.

How can we possibly determine the parity of the 15 puzzle? We can switch some pairs of blocks and maintain the parity (as our solution to the "possible puzzle" showed, above). And we can move odd numbers next to odd numbers and even numbers next to even numbers. In the original position, we can switch 1 and 3, and then restore the rest of the position. But if we want to switch 1 and 2, we cannot restore the rest of the position. Switching 1 and 2 changes the parity, and we end up with other changes on the board, which also would change the parity, in order to keep the parity the same. For example, we can switch 1 and 2 if we also switch 11 and 12.

It is fairly well known that we should number the squares behind the sliding blocks in some manner like this. Remember that these numbers are not on the sliding blocks. If we number the squares in this way, then we can represent any position as a list of numbers. Our original position becomes 1, 2, 3, 4, 8, 7, 6, 5, 9, 10, 11, 12, 15, 14, 13. We ignore the blank square, and write down the numbers on the blocks in the order dictated by the numbers behind the blocks. Does that make sense? This list of numbers has odd parity. We can determine the parity by how many switches of adjacent numbers it takes to get the numbers into order (1, 2, 3, 4, . . ., 15). Here it takes nine switches (it takes three switches to move 5 next to 4), which is an odd number of switches.

Then we can go on to show that any move (sliding a block to an adjacent blank square) in the 15 puzzle does not change the parity of this sequence of numbers. Obviously a horizontal move does not change the parity. We can also show that any of the vertical moves do not change the parity. A vertical move changes the position of the block by 0, 2, 4 or 6 places. And none of these changes the parity.

Then we can show that Sam Loyd's second position has even parity, while the original position has odd parity. His puzzle is impossible.

Return to my Puzzle pages
Go to my home page