A short history of the 15 puzzle

The 15 puzzle looks timeless, but it has a birth date of sorts: the winter of 1879–1880, when a small wooden box of numbered blocks went from a curiosity in upstate New York to a craze that swept America and Europe in a few months.

Who invented it

For a long time the credit went to Sam Loyd, the famous American puzzle maker, who claimed from the 1890s on that he had invented it. He hadn’t. Historians Jerry Slocum and Dic Sonneveld traced the puzzle back to Noyes Chapman, a postmaster in Canastota, New York, who was showing friends a version of it in the mid-1870s. Copies spread to Syracuse, then to Boston, where woodworkers began making and selling them in late 1879. Chapman applied for a patent in 1880, but it was turned down.

The craze of 1880

In early 1880 the “Gem Puzzle” or “Boss Puzzle”, as it was sold, was everywhere. Newspapers printed cartoons of people bent over the little box; employers complained about lost working hours; some shops banned it. Within weeks it crossed the Atlantic to Britain, France and Germany. Then, almost as fast as it had come, the fashion faded by the summer.

The 14–15 puzzle and the prize

Part of the fever came from a cruel twist. Puzzles were often sold with the tiles in order except for 14 and 15, which were swapped, and players were challenged to fix them. Prizes were offered for a solution. Sam Loyd later told the story of a $1,000 prize of his own; there is no evidence he ever offered it, but the story stuck.

Nobody ever claimed a prize, because nobody could. In 1879 two American mathematicians, William Johnson and William Story, had published a proof in the American Journal of Mathematics: every slide keeps a certain count (even or odd) the same, so exactly half of all arrangements can be reached from the solved board and the other half can’t. The 14–15 board is in the wrong half. It was one of the first times a popular game was settled by a mathematical proof.

Counting the boards

There are 16! (about 20.9 trillion) ways to put fifteen tiles and a gap in the box, so about 10.5 trillion boards can be solved. That is far too many to check one by one with pencil and paper, and for a century the question “how many moves does the hardest board need?” stayed open.

Computers changed that. In 1985 Richard Korf used the 15 puzzle to introduce IDA*, a search method still used today (it is what the solver on this site runs). In the 1990s, researchers in Zurich showed that every 15 puzzle can be solved in at most 80 moves, and that some boards do need all 80. The smaller 8 puzzle never needs more than 31. For the 24 puzzle on a 5×5 board the exact number is still unknown.

数字华容道 and other names

In China the 15 puzzle is called 数字华容道, “number Huarong Road”. The name comes from an older Chinese sliding-block puzzle, 华容道, in which the general Cao Cao must slide his way out of an ambush at Huarong. In Japan it is the 15パズル; in France, the taquin; in Spain and Latin America, the juego del 15. The puzzle has never really gone away: cheap plastic versions became a classic pocket toy, and speed solvers today finish a 4×4 board in a few seconds.

Want to try it? Play the 15 puzzle, or learn how to solve it.