The 15-Puzzle

You have met it on cereal boxes and in airport gift shops: fifteen numbered tiles in a 4×4 frame with one empty square, and you slide tiles around until they read 1 through 15 in order. The 8-puzzle is its 3×3 little brother.

In 1880 the puzzle ignited a worldwide craze. The showman Sam Loyd famously offered $1000 to anyone who could solve a board where only the 14 and 15 were swapped. The money was never claimed — and it never could be.

The reason is one of the most elegant facts in all of puzzling: exactly half of the possible arrangements can never be reached, no matter how long you slide. That invisible wall, and the much taller wall behind it, is what this article is about.

Here is a 3×3 sliding puzzle (the 8-puzzle). Click any tile next to the empty square to slide it. Try to reach 1 2 3 / 4 5 6 / 7 8 · — the empty square in the corner.

<p class="hint">{{hint}}</p>
<div id="board" class="board"></div>
<div class="status" id="status">{{status_initial}}</div>
<div class="btns">
  <button id="shuffle" type="button">{{btn_shuffle}}</button>
  <button id="swap" type="button">{{btn_swap}}</button>
  <button id="check" type="button" class="ghost">{{btn_check}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.board { display: grid; grid-template-columns: repeat(3, 64px); gap: 6px; margin: .4rem 0; }
.tile { width: 64px; height: 64px; display: flex; align-items: center; justify-content: center;
        font: 700 26px ui-monospace, monospace; border-radius: 10px; user-select: none;
        background: #1d3557; color: #fff; border: 1px solid #15273f; transition: transform .08s; }
.tile.movable { cursor: pointer; }
.tile.movable:hover { transform: scale(1.04); background: #2a4a73; }
.tile.blank { background: #e8eef3; border: 1px dashed #cdd9e3; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Now press Swap two tiles. The board looks like a normal scramble, but a hidden quantity — the parity — has flipped, and no sequence of slides will ever solve it. The demo computes that parity instantly and tells you. Checking whether a board is solvable is easy. Finding the shortest path of slides for a big puzzle is the hard part.

The 15-puzzle hides two very different questions, with two very different answers.

• Is this board solvable? Surprisingly easy. Write the tiles in reading order and count the inversions (pairs of tiles out of order). For the 4×4, combine that count with the row of the blank; for odd-width boards just use the inversion parity. This is a single linear-time scan — and it never changes as you slide, which is why it is called an invariant. Every legal slide moves the blank and changes the inversion count by an even amount, so the parity is frozen. That is precisely why Loyd's swapped 14–15 board was impossible: the swap flips the parity.
• Solvability splits the world in two. Of the 16! arrangements of the 15-puzzle, exactly half are reachable from the goal. The other half live in a separate universe you can never slide into.
• What is the shortest solution? Now it gets brutal. For the generalized n×n puzzle, deciding the minimum number of moves is NP-hard — proved by Daniel Ratner and Manfred Warmuth (1986 conference paper; full version 1990). So while you can always tell whether a giant sliding puzzle is solvable, computing its optimal solution is as hard as the toughest problems in P vs NP.

That gap — trivial to verify reachability, intractable to optimize the path — is the whole story.

The two ideas behind the 15-puzzle — a hidden invariant and a huge search space — are everywhere:

• Group theory & the Rubik's Cube: the same parity argument explains why you can't pop out two cube stickers and swap them; the reachable states form a subgroup, never the whole set.
• Robot motion planning: rearranging objects in a warehouse or pixels on a screen is "reconfigure pieces under movement rules," exactly the 15-puzzle pattern at scale.
• AI search & heuristics: the 8- and 15-puzzles are the textbook proving ground for A* and admissible heuristics (Manhattan distance, pattern databases) — the same machinery behind route finders.
• Detecting impossibility cheaply: a fast invariant that rules out half the inputs before any search begins is a recurring engineering win.

The lesson generalizes: a cheap check can save you from a hopeless search, but it can't make the search itself easy. Compare the optimization wall with the Traveling Salesman and SAT.

The 15-puzzle is a perfect miniature of computational complexity. A one-line parity check tells you, instantly and for certain, whether a board can ever be solved — and that same arithmetic proves Sam Loyd's prize was unwinnable. Yet ask for the shortest solution of a large board and you slam into NP-hardness, the same wall behind P vs NP.

So the next time someone hands you a scrambled puzzle, you can do something almost magical: glance at it, count a few inversions, and announce whether it is solvable at all — long before you would ever finish sliding the tiles.