Why Can Half of All 15-Puzzle Starting Positions Never Be Solved?

Half of all 15-puzzle starting positions cannot be solved, because every slide keeps the parity of one count unchanged. Of the 16! = 20,922,789,888,000 ways to place the 15 tiles and the blank, exactly 10,461,394,944,000 sit in the unsolvable half. William Johnson and William Story proved it in 1879. You can tell which half your puzzle is in by counting inversions.

Below: who invented the puzzle, the counting rule with a worked example, Sam Loyd's $1,000 offer, the 80-move record for the hardest position, and whether sliding puzzles say anything about IQ. Every count on this page is our own arithmetic, checked by script on 12 November 2026.

What is the 15 puzzle and who invented it?

The 15 puzzle is a sliding puzzle. Fifteen numbered square tiles sit in a frame four tiles wide and four high, with one empty space, and you slide tiles into the space until they read 1 to 15 in order. It is also called the Gem Puzzle, the Boss Puzzle or the Mystic Square. The same idea on a 3 by 3 frame is the 8 puzzle, and both are sliding tile puzzles.

Noyes Palmer Chapman, a postmaster in Canastota, New York, is said to have shown friends a precursor as early as 1874. The puzzle became a craze in the United States in 1880. Sam Loyd claimed from 1891 that he had invented it, but Wikipedia, citing Barry Clarke's 1994 book, says he had no connection with its invention, and his first article on it came in 1886. The OEIS entry A087725 also names Chapman. Both rest on Jerry Slocum and Dic Sonneveld's book The 15 Puzzle (2006), which we did not open.

Why can half of all 15-puzzle starting positions never be solved?

Because every legal slide changes two numbers at once, and the changes cancel out. Read the tiles row by row and skip the blank. An inversion is a pair of tiles where the larger number comes first. Add the number of inversions to the blank's row, counted from the bottom row as 1. A slide never changes whether that total is odd or even.

Here is why. A sideways slide leaves the reading order alone, so the inversions stay put and so does the blank's row. An up-or-down slide moves one tile past three others in the reading order, so the inversion count changes by an odd amount (1 or 3), while the blank's row changes by exactly 1. The two changes add to an even number, so the parity holds. This is our statement of the argument. Johnson and Story's own paper phrases it with a determinant.

The solved board has no inversions and the blank in row 1, so its total is odd. Only starting positions with an odd total can ever reach it. Half of the 16! arrangements have an odd total and half have an even one, so exactly half are out of reach. Johnson and Story (American Journal of Mathematics, December 1879) opened by noting that players generally supposed the puzzle was always possible, "but this is an error".

Aaron Archer (American Mathematical Monthly, 1999) set out to give a simpler modern proof, because the older accounts were hard to follow. We also checked small boards by brute force. A search from the solved position reaches 12 of the 24 arrangements of a 2 by 2 board, 360 of 720 on a 3 by 2 board and 181,440 of 362,880 on the 3 by 3 board. That is exactly half each time, and every position reached obeys the rule.

How can you tell if a sliding puzzle is solvable?

Here is how to tell if a sliding puzzle is solvable: count the inversions, then apply one rule for the width of the board. On an odd-width board, such as the 8 puzzle, the position is solvable when the inversion count is even. On an even-width board, such as the 15 puzzle, it is solvable when the inversions plus the blank's row from the bottom come to an odd number. Searches like 15 puzzle solvable or 15 puzzle unsolvable all end at this one test.

Take this position. Row 1 is 2, 3, 4, 10. Row 2 is 1, 6, 8, 7. Row 3 is 5, 11, blank, 15. Row 4 is 9, 14, 13, 12. For each tile, count the smaller tiles that come after it in reading order.

• Tiles 2, 3 and 4 each have tile 1 after them: 3 inversions
• Tile 10 has 1, 6, 8, 7, 5 and 9 after it: 6 inversions
• Tile 6 has 5 after it (1), tile 8 has 7 and 5 (2), tile 7 has 5 (1): 4 inversions
• Tile 11 has 9 after it (1) and tile 15 has 9, 14, 13 and 12 (4): 5 inversions
• Tile 14 has 13 and 12 after it (2) and tile 13 has 12 (1): 3 inversions
• Total: 3 + 6 + 4 + 5 + 3 = 21 inversions

The blank is in the second row from the bottom, so the total is 21 + 2 = 23, which is odd. This position is solvable. Now swap tiles 1 and 2. The inversions drop to 20, the total becomes 22, which is even, and the position can never be solved.

We tested the rule two ways. A script shuffled the 16 squares 100,000 times with a fixed seed, and 49,798 of the arrangements, 49.8%, passed, close to the 50% the theory predicts. Another run made 200,000 random legal slides from the solved board, and the rule held after every one.

What was Sam Loyd's $1,000 14-15 puzzle?

It was the solved board with tiles 14 and 15 swapped, and it cannot be solved. The position has 1 inversion (15 comes before 14) and the blank sits in the bottom row, so the total is 1 + 1 = 2, which is even. It lies in the unsolvable half. Wikipedia says Loyd offered a $1,000 prize for solving it, an offer that could never be claimed, because Johnson and Story had shown the swap impossible more than a decade before. The sources we read give no date for the offer, so we print none.

Any unsolvable 15 puzzle has the same fate as Loyd's. You can shuffle it for ever, and the odd-or-even total never changes. If you pull the tiles out and put them back at random, your chance of an unsolvable board is about 1 in 2.

How many moves does the hardest 15-puzzle position need?

The hardest solvable positions need 80 single-tile moves, and no solvable position needs more. Wikipedia quotes Brüngger, Marzetta, Fukuda and Nievergelt (Annals of Operations Research, 1999) as writing that they proved the hardest positions need 80 moves. Richard Korf (Journal of the ACM, 2008) ran the first complete breadth-first search of the 4 by 4 puzzle and verified its radius, as his abstract says.

We read Korf's abstract and the OEIS entry A087725, which gives the maximum number of moves for n by n boards as 6, 31 and 80 for n = 2, 3 and 4. Wikipedia quotes pages 29 and 30 of Korf's paper as saying that 17 positions need exactly 80 moves. We could not open the paper's body, so the figure of 17 is Wikipedia's quotation, not our reading.

• 2 by 2 board: 12 solvable positions, hardest needs 6 moves (our search)
• 2 by 3 board: 360 solvable positions, hardest needs 21 moves (our search)
• 3 by 3 board, the 8 puzzle: 181,440 solvable positions, hardest needs 31 moves (our search)
• 4 by 4 board, the 15 puzzle: 10,461,394,944,000 solvable positions, hardest needs 80 moves (literature)

A full search of the 4 by 4 board is far beyond a quick script, so we did not rerun it. Our searches match the OEIS values for the three smaller boards.

Does solving sliding puzzles raise IQ?

No study we read shows that practising sliding puzzles raises IQ. Solving one takes planning, because you must look several moves ahead. Learning the inversion rule is a piece of knowledge, and knowledge about one puzzle is not a higher score on a test. Whether brain games raise IQ is covered in our guide to brain training apps.

IQ tests use different puzzle types. Matrix and number-sequence items ask you to find a rule, as in our guide to number sequence puzzles and the hardest IQ test questions. A score on such a test is placed against other people, and our IQ percentile calculator turns it into a percentile. For more puzzles with answers, see our math brain teasers and brain teasers for adults.

Another puzzle with a proven answer is the Tower of Hanoi, which we compare in what it measures in people and in AI. You can play it in our Tower of Hanoi game, or try the logic puzzles.

To see how your reasoning compares with other adults, take the IQ Metrics test.

Common questions