Introduction

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.

Slide the Tiles

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">A 3×3 sliding puzzle (the 8-puzzle). Click a tile next to the empty square to slide it. Goal: <b>1 2 3 / 4 5 6 / 7 8 ·</b>. Press <b>Swap two tiles</b> to flip the hidden parity — the board then looks normal but can <b>never</b> be solved.</p>
<div id="board" class="board"></div>
<div class="status" id="status">Slide tiles toward the goal.</div>
<div class="btns">
  <button id="shuffle" type="button">Shuffle (solvable)</button>
  <button id="swap" type="button">Swap two tiles</button>
  <button id="check" type="button" class="ghost">Check solvability</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; }

// The 8-puzzle. Tiles 1..8 plus a blank (0) on a 3x3 grid.
// SOLVABILITY (easy, linear time): for an odd-width board, a state is solvable
// iff the number of INVERSIONS (pairs i<j with tile[i]>tile[j], ignoring the
// blank) has the SAME parity as the goal. Sliding never changes that parity —
// it is an INVARIANT. Swapping two tiles flips it, making the board unsolvable.
// FINDING the shortest solution for the generalized n x n puzzle is NP-hard
// (Ratner & Warmuth, 1986/1990).
const W = 3, GOAL = [1,2,3,4,5,6,7,8,0];
let board = GOAL.slice();

function inversions(arr){
  const t = arr.filter(x => x !== 0); let inv = 0;
  for (let i = 0; i < t.length; i++)
    for (let j = i+1; j < t.length; j++) if (t[i] > t[j]) inv++;
  return inv;
}
// odd width => solvable iff inversion parity matches the goal's (goal has 0).
function solvable(arr){ return (inversions(arr) % 2) === (inversions(GOAL) % 2); }
function solved(arr){ return arr.every((v,i) => v === GOAL[i]); }

function setStatus(t, cls){ const s = document.getElementById('status'); s.textContent = t; s.className = 'status ' + (cls||''); }

function render(){
  const b = document.getElementById('board'); b.innerHTML = '';
  const blank = board.indexOf(0);
  board.forEach((v, i) => {
    const d = document.createElement('div');
    if (v === 0){ d.className = 'tile blank'; }
    else {
      const adj = neighbors(blank).includes(i);
      d.className = 'tile' + (adj ? ' movable' : '');
      d.textContent = v;
      if (adj) d.addEventListener('click', () => { slide(i); });
    }
    b.appendChild(d);
  });
}
function neighbors(idx){
  const r = Math.floor(idx / W), c = idx % W, out = [];
  if (r > 0) out.push(idx - W); if (r < W-1) out.push(idx + W);
  if (c > 0) out.push(idx - 1); if (c < W-1) out.push(idx + 1);
  return out;
}
function slide(i){
  const blank = board.indexOf(0);
  [board[blank], board[i]] = [board[i], board[blank]];
  render();
  if (solved(board)) setStatus('✓ Solved! Tiles are in order.', 'ok');
  else setStatus('Keep sliding toward the goal.', '');
}
function shuffle(){
  do { for (let k = 0; k < 200; k++){ const blank = board.indexOf(0);
    const ns = neighbors(blank); const pick = ns[Math.floor(Math.random()*ns.length)];
    [board[blank], board[pick]] = [board[pick], board[blank]]; }
  } while (solved(board));
  render(); setStatus('Shuffled with real slides — still solvable.', 'ok');
}
function swapTwo(){
  // swap the first two non-blank tiles -> flips inversion parity -> unsolvable.
  const idx = board.map((v,i)=>v!==0?i:-1).filter(i=>i>=0);
  const a = idx[0], b2 = idx[1];
  [board[a], board[b2]] = [board[b2], board[a]];
  render();
  setStatus('Two tiles swapped. Parity flipped — now unsolvable.', 'bad');
}
function check(){
  if (solvable(board)) setStatus('✓ Solvable: inversion parity matches the goal.', 'ok');
  else setStatus('✗ Unsolvable: no slides can ever fix it (parity differs).', 'bad');
}
document.getElementById('shuffle').addEventListener('click', shuffle);
document.getElementById('swap').addEventListener('click', swapTwo);
document.getElementById('check').addEventListener('click', check);
render();
Result
Console

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 Real Complexity

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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/fifteen-puzzle/Content licensed under CC BY-NC 4.0.