About the 15 Puzzle | History, Parity, and Sam Loyd's 14-15

The 1880 craze

The puzzle comes from New York State in the 1870s; Noyes Chapman, a postmaster in Canastota, is usually named as its inventor. Early in 1880 it became a craze, first across the United States and then in Europe.

Sam Loyd's 14-15

The American puzzle maker Sam Loyd later claimed that he had invented the puzzle, and told of a $1,000 prize for anyone who could solve it with only 14 and 15 swapped. Nobody won the prize, and nobody could: that position cannot be solved. His claim to the invention was not true either.

Why half the positions are impossible

Treat the gap as a sixteenth tile. Every slide swaps the gap with one tile. To get back to its corner the gap must move as often left as right and as often up as down, so a position with the gap in its corner is always an even number of swaps away from the solved order. Swapping 14 and 15 is one swap, which is odd, so no slides can reach it. In 1879 William Johnson and William Story proved that exactly half of all arrangements can be reached.

A test for any position

Count the pairs of tiles that stand in the wrong order when you read the tray row by row. On a 3×3 or 5×5 board a position can be solved when that count is even. On a 4×4 board, add the row of the gap counted from the bottom: the position can be solved when the sum is odd.

Solving by computer

A computer can search for a way back with A*, which always looks at the most promising position first. It estimates the moves still needed from how far each tile is from home, plus two moves for each pair of tiles that block each other in their own row or column. Finding the shortest solution gets very hard on large boards. The hardest 15 puzzle positions need 80 moves, and the 8 puzzle never needs more than 31.

Try it in PictorX

Open the 15 Puzzle and click a tile to slide it. Shuffle mixes the tiles into a new position that can be solved, Solve plays a solution move by move, and Show correct tiles colors the numbers of the tiles already in place. Pick Loyd's 14-15 to see the impossible position, and use Size to switch between 3×3, 4×4, and 5×5.