Why half of all 15 puzzle configurations are mathematically impossible
In short: You might think any scrambled arrangement of the 15 puzzle can eventually be solved with enough patience. However, mathematics proves that exactly 50% of all possible starting positions are physically unreachable. This isn't a limitation of skill, but a fundamental property of parity and permutation.
In 1879, mathematicians Johnson & Story used a parity argument to demonstrate that the 15 puzzle divides into two mutually inaccessible equivalence classes. They discovered that certain configurations are impossible to resolve because they require an 'odd' transformation from an 'even' state. Specifically, the solvability depends on the relationship between the permutation of the tiles and the taxicab distance—the sum of horizontal and vertical steps—of the empty square from its home position in the bottom-right corner.
Every legal move changes both the parity of the tile sequence and the parity of that distance. Because these two values change simultaneously, their combined parity remains invariant. If you start with a configuration where this parity doesn't match the goal state, no amount of sliding will ever fix it. This principle was famously used to debunk Sam Loyd’s '14-15 puzzle' in the late 19th century; Loyd offered a prize for reversing just two tiles, a feat Johnson & Story had already proven impossible over a decade earlier.
While finding any solution is relatively simple, determining the shortest path (the 'God's number') is an NP-hard problem. For the standard 4x4 grid, the maximum number of single-tile moves required to solve the most difficult configuration is 80. In contrast, the larger 24-puzzle presents a staggering complexity; its total possible positions are approximately 7.76 trillion, making brute-force calculations for optimal solutions nearly impossible.
The puzzle's history is also marked by intellectual disputes. While Noyes Palmer Chapman is credited with an early precursor in 1874, Sam Loyd falsely claimed invention rights for decades. Despite these controversies, the puzzle remains a cornerstone of algorithmic study, used to test heuristics like taxicab distance and misplaced tile counts in search algorithms like A*.
Opens the Intellect+ feed with this card first. Swipe up for the next one.
Sources
- Summary by Intellect · source: 15 puzzle
- Also: Wikidata — 15 puzzle · CC0
- Also: Wikidata — 15 puzzle · CC0
To cite this card, link to https://intellectplus.co.uk/app/sport-15-puzzle.
How we source, check and correct cards: Editorial standards.
General information, not professional advice. Spotted an error? Flag the card or see corrections and complaints.
Intellect Plus is a visual educational discovery platform for exploring fascinating facts and ideas. Brain Food, Not Brain Rot. What is Intellect Plus?
Related
More in Puzzles · More in Sport & Games · Latest · A–Z · All topics
