The 15 Puzzle (1880) — The Unsolvable Move with Which Sam Loyd Fooled the World

Introduction

In the winter of 1880, the whole of America was possessed by a small box that fit in the palm. Inside a square frame sat numbered tiles from 1 to 15, and by sliding them through the single empty space, one had to reorder the scrambled numbers into sequence. That was the entire toy, yet it stopped fingers in saloons, offices, and railway carriages alike, and newspapers complained that the fever was paralyzing honest work. This was the first worldwide craze for the sliding-tile game later known as the 15 Puzzle.

The goal state. Tiles run 1 to 15 in order, with the blank settled in the bottom-right. In 1880 the whole world was gripped by this simple act of rearrangement.

But what I wish to exhume here is less the craze itself than the identity of the man whom the world long remembered as the box's inventor. His name was Samuel Loyd (1841-1911). America's foremost puzzle author and a former chess problemist, he claimed that he himself had set off the mania, and even posted a reward of one thousand dollars to anyone who could solve it. Yet a decisive lie was folded into that claim.

In this essay I trace the true origin of the 1880 craze, and unearth the fact that the very board Loyd staked his prize on had been proven 'mathematically impossible to reach' in 1879, years before he ever spoke up. And I want to reread, from the side of history, the question this old wooden box handed down even to today's digital puzzles: how does one guarantee that a puzzle can be solved at all?

The Context of the Era

The sliding-tile mechanism itself is thought to have been devised around 1874 by Noyes Palmer Chapman, a postmaster in Canastota, New York. Over the next few years it spread by word of mouth, and once manufactured as a product, it ignited an explosive craze in the United States in January 1880. The wave crossed to Europe by April of that year, and then ebbed abruptly around July. The mania was a short but violent fever lasting only about half a year.

Sam Loyd began calling the puzzle 'my invention' long after the craze had passed. His first published article about the 15 Puzzle appeared in 1896, sixteen years after the peak of the mania. There is no trace of his involvement in the actual fad. And yet Loyd, over the long years until his death, kept asserting his authorship again and again.

This deception was fully unraveled only in recent times. The puzzle historians Jerry Slocum and Dic Sonneveld, in their 2006 book The 15 Puzzle, collated the period's primary sources and meticulously demonstrated that Loyd's claim had been a fabrication sustained for one hundred and fifteen years. The honor of invention belonged instead to an obscure postmaster.

Mechanics

The rules could not be simpler. Within a 4x4 frame sit fifteen tiles and one empty space; only a tile adjacent to the gap may be slid into it. The goal is to arrange the numbers in order from 1 to 15 and settle the blank into its appointed corner. There is no limit on the number of moves, and anyone can pick it up. That very plainness was the charm that seized the people of 1880.

The board Loyd offered as his prize. Tiles 1–13 sit in order, with only the 14 and 15 swapped (dashed). The goal is to sequence them from the top-left and send the blank to the bottom-right — yet this arrangement has reversed parity and can never be reached, however you slide.

And yet the game held an invisible wall. The American mathematicians William Woolsey Johnson and William E. Story contributed 'Notes on the ‘15’ Puzzle' to the American Journal of Mathematics in 1879, and by an argument from parity (the evenness or oddness of a permutation) they proved that half of all starting positions can never be ordered, no matter how many moves one makes. Whether a board is solvable, in other words, is fixed mathematically from the start, not by luck or persistence.

The board on which Loyd staked his thousand dollars belonged precisely to that 'unsolvable half.' What he posed was a nearly complete arrangement in which only the 14 and the 15 were swapped. It looks one step from done, yet because its parity is reversed it can never reach the solution. The prize money was safe. He sold a mathematical impossibility as a 'solvable hard problem,' setting the crowd to compete in eternal futility. This was not invention but the staging of impossibility.

The Lineage to the Present

The vantage that Johnson and Story opened up—reading a board's state space through mathematics—runs straight into later computer science. In 1990 Daniel Ratner and Manfred Warmuth showed that for the generalization of the 15 Puzzle to an n×n board, finding a shortest solution is NP-hard (first presented at AAAI in 1986). Enlarge the board, and the search for an optimal solution becomes computationally intractable. The question of parity from 1879 was continuous with the modern theory of hardness itself.

Generalize the board to n×n and finding a shortest solution becomes computationally intractable (NP-hard). The parity question of 1879 runs continuous with the modern theory of 'hardness.'

And this lineage now rests quietly but heavily on everyone who handles sliding tiles in digital form. Anyone implementing a puzzle that scrambles tiles at random must reckon with the Johnson–Story theorem, for if one naively scatters the tiles, half the time one hands the player a board that is absolutely unsolvable. That is why modern sliding-puzzle generators check parity internally and deal out only solvable boards. The 1879 proof lives on as a precondition of implementation.

What Loyd left behind was not the honor of invention but a thornier lesson. The difficulty of a puzzle can sometimes pass beyond 'hard' and reach 'impossible'; and to one who cannot discern that impossibility, an unsolvable board is indistinguishable from a merely difficult one. The ethic of modern puzzle design—that the setter bears responsibility for guaranteeing a solution exists—is, ironically, illuminated most vividly by his thousand-dollar lie.

References

Sources referenced in this article:

・Wikipedia: 15 puzzle

・Cut the Knot: Sam Loyd's Fifteen, the history of the puzzle

・David Richeson: A picture of frustration — Sam Loyd's 15 puzzle

・MacTutor History of Mathematics: Samuel Loyd (1841-1911)

・Wikipedia: Sam Loyd

・Jerry Slocum & Dic Sonneveld, The 15 Puzzle: How It Drove the World Crazy (Slocum Puzzle Foundation, 2006)

・W. W. Johnson & W. E. Story, “Notes on the ‘15’ Puzzle,” American Journal of Mathematics, vol. 2, no. 4 (1879), pp. 397–404

・D. Ratner & M. Warmuth, “The (n²−1)-puzzle and related relocation problems,” Journal of Symbolic Computation, vol. 10 (1990), pp. 111–138 (first presented at AAAI 1986)

・Wolfram MathWorld: 15 Puzzle

Closing

What the 15 Puzzle demonstrated historically, I believe, is two things. First, that an utterly simple set of sliding-tile rules placed an object of modern mathematics—the state space—into the palms of the general public. The people of 1880 wore down their fingers against a wall of pure logic, never knowing they were tracing the boundary between even and odd permutations. It was a rare moment in which a puzzle democratized mathematics.

Second, there is the question of the setter's honesty. Sam Loyd was no inventor, but the 'unsolvable board' he planted in his reward ironically thrust the very heart of puzzle design upon posterity. A challenge whose solution cannot be guaranteed is not a hard problem but a deception. The proof of 1879 and the craze of 1880, even now after a hundred and forty years, pose the same question to everyone who shuffles tiles: is that board truly solvable?