The 15 Puzzle was introduced in 1878 by American amateur mathematician Samuel Loyd (1841–1911). He called it the “Boss Puzzle” and later the “15-16 Puzzle.” It is one of the most famous puzzles in his book Sam Loyd’s Cyclopaedia of 5,000 Puzzles, Tricks and Conundrums, published in 1914 after his death by his son, Sam Loyd. This puzzle has 16 squares; 15 of them are numbered from 1 to 15 and placed in a 4 by 4 configuration, with one position, the 16th, left open. The idea was to reposition the squares from a given arbitrary arrangement by sliding them from place to place until they were in numerical order (1, 2, 3, and so on). For some initial starting points, the rearrangement was possible; for others, it was not.

But Loyd offered a twist to the puzzle—he switched the positions of the squares numbered 14 and 15—and offered $1,000 to anyone who could solve the puzzle. Working out the puzzle became a craze in America, with reports of companies prohibiting employees from playing during office hours—it was as popular as playing computer solitaire is today. Even in Europe, the craze grew. Deputies in Germany’s Reichstag played the puzzle, and in France it was claimed to be a greater curse than alcohol or tobacco. But Loyd knew no one could solve the puzzle, much less remember all the steps taken to try and get to a solution, because there was no solution!

An example of a Latin square.