The story of the 15 puzzle

The 15 puzzle is a 4×4 frame holding fifteen numbered tiles and one empty square. You slide tiles into the gap to put the numbers in order. The strangest thing about it: exactly half of all possible arrangements can never be solved, however long you push tiles around.

Why half can't be solved

Read the tiles from the top left, skipping the gap, and count every pair where a bigger number comes before a smaller one. Call each such pair an “inversion”. The solved board has none.

Sliding a tile sideways doesn't change the reading order, so the inversion count stays the same. Sliding a tile up or down makes it jump over the three tiles between its old and new place in reading order. That flips its order with each of those three, so the count changes by 3, 1, −1 or −3: it always switches between even and odd. Meanwhile the gap moves exactly one row on every vertical slide. So the parity of “inversions plus the gap's row” can never change, whatever you do.

A board whose parity differs from the solved board's therefore can never reach it. It is also known that every board with the matching parity can be solved, so the solvable ones are exactly half. On the 4×4 board there are 16! arrangements, and half of them, 10,461,394,944,000, are solvable. Swapping just tiles 14 and 15 in the solved position adds a single inversion and flips the parity, so that board is impossible.

This was shown in 1879: W. W. Johnson proved the odd ones impossible, and W. E. Story showed that all the even ones can be reached, in a pair of notes in the American Journal of Mathematics. On the 3×3 version of this site, our program checks all 362,880 (9!) arrangements and confirms that the parity test agrees with whether the goal can really be reached. Try “Try an impossible board” on the puzzle page to see it for yourself.

Not Sam Loyd's invention

For a long time the 15 puzzle was credited to Sam Loyd, the famous American puzzle maker. Recent research says Loyd had nothing to do with inventing it or with making it popular. The inventor is believed to be Noyes Palmer Chapman, a postmaster in a small New York town, with an ancestor of the puzzle made of blocks around the mid-1870s. He applied for a patent, which seems not to have been granted.

Loyd began claiming it as his own more than ten years after the craze of 1880. The well-known tale that he offered $1,000 for swapping 14 and 15 back has never been confirmed. What is certain is that Loyd himself wrote that he had made such an offer.

The craze of 1880

Around the end of 1879 a woodworker in Boston began selling it as the “Gem Puzzle”. The fad started in the United States in January 1880, reached Europe in April, and had died down by July. It lasted less than half a year.

In Japan, a 1907 book, Sekai Yūgihō Taizen, is said to have introduced it under the name “Jūgo Okikae Asobi”.

How many moves at most?

The answer depends on how you count. Counting one tile per move, every solvable 3×3 (8-puzzle) position can be solved in 31 moves or fewer. This site's program searched all 181,440 reachable positions outward from the goal and confirmed that the farthest needs 31. For the 4×4 puzzle, the maximum is 80 single-tile moves, and 17 positions need all 80; that was settled by a large computer search in the late 1990s. If sliding a whole row of tiles at once counts as one move, the maximum drops to 43.

The game on this site counts one drag or tap, even when several tiles move together, as one move.

How to think about it

• Lock in the top row first. Once row one is done, never touch it again. Then do the left column, and so on, shrinking the board as you go.
• The last two of a row need a trick. Tucked in directly, the gap can't reach them. Deliberately shift them out of place first, and plan a sequence that drops both in together.
• Think of the gap as a carrier. To move a tile, walk the gap round to its side, along a path that doesn't disturb what you've already placed.
• Some boards are impossible. If you are left with exactly two tiles swapped at the end, the arrangement had the wrong parity from the start.

Stuck? The Hint button shows a next move. On 4×4, if no shortest route is found in time, it gives a move that is not necessarily shortest, and tells you so.