The 15 Puzzle: The Hoax That Made It Famous

Quick answer: the 15 puzzle is fifteen numbered tiles in a four-by-four frame with one empty space, solved by sliding them into order. It was invented by Noyes Palmer Chapman, not Sam Loyd, and exactly half of all possible starting positions cannot be solved at all.

Best for: anyone who likes a puzzle with a scandal attached.

Almost everybody has handled one. Almost everybody has been told it was invented by Sam Loyd. That part is a lie, and it is a lie Loyd told deliberately, for twenty years, and largely got away with.

Who Invented the 15 Puzzle?

Noyes Palmer Chapman, the postmaster of Canastota, New York, who applied for a patent in March 1880.

Sam Loyd, a famous and genuinely talented puzzle designer, first claimed the invention in 1891, more than a decade later, and kept claiming it until his death twenty years after that. He was a far better self-publicist than Chapman and the claim stuck. It is still repeated today, including in places that ought to check.

Loyd did not need to do this. He designed a great deal of excellent material on his own account, which is what makes the episode odd rather than merely dishonest.

Why Can Half of the Starting Positions Never Be Solved?

This is the part that makes the puzzle mathematically interesting, and it is also the part Loyd exploited.

Every arrangement of the tiles has a property called parity, which you can think of as whether it takes an odd or an even number of tile swaps to reach the solved state. Sliding a tile into the gap always changes the arrangement in a way that preserves one kind of parity and never the other.

The consequence is absolute. The possible arrangements split into two groups, and you can only ever move within your own group. Half of all starting positions can reach the solved state. The other half cannot, ever, no matter how long you work.

No amount of skill crosses that line, which is unusual: most puzzles punish you for being wrong, and this one can be unsolvable from the moment it is handed to you.

What Was the Famous Prize?

Loyd offered a substantial cash prize to anyone who could solve the puzzle from a position with the 14 and 15 tiles swapped and everything else in order.

That position is in the unsolvable half. The prize was never going to be claimed, and Loyd knew it, which is the other reason the attribution matters. The hoax and the prize were the same piece of showmanship.

It worked. The puzzle became a mania in the early 1880s, and the story of the unclaimable prize is a large part of why.

How Many Positions Are There?

Sixteen cells with fifteen tiles and a gap gives 20,922,789,888,000 arrangements, which is sixteen factorial.

Parity halves it. Exactly 10,461,394,944,000 of those can reach the solved state, and the same number never can. Roughly ten and a half trillion solvable positions, and an equal number of traps.

That is the scale that makes the hoax work. Hand somebody a random arrangement and there is a fifty per cent chance you have handed them something impossible, and no way for them to tell by looking.

How Do You Solve a 15 Puzzle?

Top-down and left-to-right, finishing each region before starting the next.

Solve the top row first, then lock it. Place tiles 1, 2 and 3, then handle 4 together with the position below it, because the last tile of a row cannot be slotted in directly without disturbing what you have done.

Repeat for the second row. You now have two rows finished and a two-by-four area remaining.

Solve the last two rows together, column by column. They have to be treated as one region, which is why many people get three rows done easily and then stall.

If the final two tiles are swapped and nothing else is wrong, stop. You have not made a mistake. You have been given one of the unsolvable positions, and the only fix is to lift a tile out and put it back, which is cheating and also the correct response.

Is the 15 Puzzle Mathematically Hard?

Harder than it looks, in a formal sense.

Finding the shortest solution to a sliding puzzle of this kind is computationally difficult, and sliding-block puzzles in general were proved PSPACE-complete by Robert Hearn and Erik Demaine. Getting to a solution is easy once you know the method. Getting there in the fewest possible moves is a genuinely hard problem.

That gap between easy-to-solve and hard-to-solve-optimally is covered more broadly in the guide to mechanical puzzles, where sliding puzzles sit in the combination family.

What Should You Try Instead?

We do not make sliding puzzles, and they are the one major family we have nothing in.

If what you enjoyed was the sequencing, the closest thing we make is Snake Cube, where 27 blocks on a cord can only be wrong in their order, and there is a full walkthrough. If it was the ordered-moves aspect, the Tower of Hanoi is the other great classic of the form and we do make that one.

The wider range is in mechanical puzzles.

If you want the same family with pieces of different sizes rather than identical tiles, that is Huarong Dao, and it works nothing like this one.

The same gap between the famous version and the real origin shows up in the Hungarian Rings, sold in 1982 and patented in 1893.

A 1981 puzzle that grafted this sliding mechanic onto a rotating one is the Missing Link, where two of the four rows cannot turn at all.

Frequently Asked Questions

Who invented the 15 puzzle?

Noyes Palmer Chapman, postmaster of Canastota, New York, who applied for a patent in March 1880. Sam Loyd claimed the invention from 1891 until his death twenty years later and is still widely credited, incorrectly.

Why is my 15 puzzle impossible to solve?

It may genuinely be impossible. Arrangements divide into two groups by parity, and sliding tiles can never move you between them, so exactly half of all starting positions cannot reach the solved state. If you are left with two tiles swapped and everything else correct, you were given an unsolvable start.

What is the trick to solving a 15 puzzle?

Work top-down, completing each row and then leaving it alone. The last tile of a row has to be placed together with the one below it rather than directly. The final two rows must be solved as a single region, column by column, which is where most people stall.

Was Sam Loyd's prize ever won?

No, and it could not have been. The position he set, with the 14 and 15 swapped, is in the unsolvable half. The prize was safe by mathematics rather than by difficulty.