Designing a Solvability Gate for 15 Puzzle Implementations

Every 15-puzzle implementation eventually hits the same quiet question: given a starting arrangement, can the player ever reach the goal? The answer is not obvious. Random shuffles fail roughly half the time, and a permissive build that lets the player play an unsolvable board wastes the user's evening. A strict gate that blocks too many starts kills engagement. Engineers building or integrating a sliding-tile game need a clear, testable rule, plus a way to debug it when their version disagrees with a reference solver.

This piece walks through the parity math behind the classic sliding puzzle, the edge cases that bite production code, and a short checklist you can drop into a code review. It is written for engineers, not for casual players — if you want the gameplay walkthrough, rules, and winning tips, the 15 puzzle rules and winning tips guide covers that side of the topic.

The Two-State Rule Most Codebases Get Wrong

The puzzle's state space splits cleanly into two connected components. From any reachable configuration, the parity of the permutation combined with the row of the blank tile determines which component the configuration lives in. The standard formulation:

1. Count the number of inversions — pairs (i, j) with i < j and value[i] > value[j], treating the blank as value 16 and ignoring it when it occupies a tile position.
2. Find the row of the blank tile, counted from the bottom (row 1 is the bottom row of the 4×4 grid).
3. The board is solvable iff either of the following holds:
   • The blank is on an even row from the bottom and the inversion count is odd.
   • The blank is on an odd row from the bottom and the inversion count is even.

That is the rule. Implementations get it wrong by counting inversions with the blank included, by counting the blank's row from the top, or by flipping both branches at once. Any one of those slips makes the gate accept unsolvable boards or reject solvable ones. Treat the two checks as a single boolean with a unit test on each side.

A useful reference for the underlying combinatorics is the Wikipedia entry on the 15 puzzle, which traces the parity argument back to the 1870s and explains why the two-component structure exists.

Why the Rule Is Not Enough in Production

A pure parity check protects you against random shuffles, but production systems accumulate state through player actions, save/restore, and import/export. Three concrete failure modes show up repeatedly:

• Resume from a corrupt save. A user closes the tab mid-shuffle, the local storage writes a half-serialized state, and on reload the board is technically legal but unreachable from the current "shuffle seed." Reject these on load.
• Drag-and-drop moves that bypass the grid model. A naive drag handler lets the user pick up a tile and release it two cells away. From the player's view it looks like two swaps; from the solver it is an illegal transition. Gate every input through the same move primitive.
• Hint features that propose an illegal move. If your hint engine runs an A* search on a state graph but you forgot to apply the parity filter when seeding the search, you can return a move that pushes the board out of the goal's component. Pre-filter the start state before any search.

The fix in every case is the same: have one function isSolvable(state) -> boolean, call it on every transition that changes state, and never expose the underlying state object to other modules without that wrapper.

A Minimal Implementation in TypeScript

Here is a compact, testable version. It treats the blank as 0 internally and never lets the blank leak into inversion counting.

type Board = readonly (readonly number[])[]; // 4x4, values 1..15 plus one 0

export function isSolvable(board: Board): boolean {
  const flat = board.flat();
  let inversions = 0;
  for (let i = 0; i < flat.length; i++) {
    if (flat[i] === 0) continue;
    for (let j = i + 1; j < flat.length; j++) {
      if (flat[j] === 0) continue;
      if (flat[i] > flat[j]) inversions++;
    }
  }

  // Row of the blank, 1-indexed from the bottom.
  const blankIndex = flat.indexOf(0);
  const blankRowFromTop = Math.floor(blankIndex / 4);
  const blankRowFromBottom = 4 - blankRowFromTop; // 1..4

  if (blankRowFromBottom % 2 === 0) return inversions % 2 === 1;
  return inversions % 2 === 0;
}

Two tests worth pinning down before shipping:

• The solved board ([1..15, 0]) is solvable — inversions is 0, blank is on row 1 from the bottom (odd), even inversions satisfy the branch. Returns true.
• A swap of just 14 and 15 in the solved state is unsolvable — inversions jumps to 1, blank is still row 1, even branch rejects. Returns false.

If those two cases pass, you have eliminated about 90% of parity bugs.

Generating Shuffles That Are Always Legal

Once the gate exists, the natural next step is a shuffle primitive that never returns false. The simplest approach is rejection sampling:

export function shuffleBoard(rng: () => number): Board {
  while (true) {
    const flat = [0, ...range(1, 15)].map((v) => ({ v, k: rng() }));
    flat.sort((a, b) => a.k - b.k);
    const board = flat.map((c) => c.v).chunk(4);
    if (isSolvable(board)) return board;
  }
}

Rejection sampling is fine for small state spaces and human-scale runs, but the expected number of retries is close to 2, so the cost is negligible. If you are seeding thousands of puzzles per minute — leaderboards, daily challenges, classroom modes — consider a constructive algorithm: start from the solved state and perform a long random walk of legal moves. Any walk from the solved state is, by construction, in the same connected component. This guarantees one valid output per walk and avoids the loop entirely. The walk length matters: fewer than ~50 moves produces recognizably ordered boards; 200+ looks random to players.

For a deeper look at random walk length and perceived randomness in puzzle generation, the JavaScript reference on typed arrays is a useful reminder that any RNG path you pick should produce reproducible output when seeded, so daily challenges are reproducible across users.

Debugging When Your Solver Disagrees With a Reference

A common debugging story: a tester solves the puzzle, your completion counter does not increment, and the state you serialized looks solved. Three checks, in order:

1. Re-serialize and re-run isSolvable on the result. If it returns false, your move handler produced an illegal transition. Walk back through the last move and confirm the move primitive is the only path to mutate state.
2. Compare the serialized state to the canonical solved state byte-by-byte. Tile-by-tile equality is the only valid completion signal. Do not compare hashes, do not compare "all tiles in correct position except blank" — the only correct solved state has the blank in the bottom-right corner.
3. Replay the user's move log against a known-good solver. If your solver refuses the final move, your solver is wrong; if it accepts but your counter does not fire, your completion signal is reading stale state.

A reviewer-friendly way to enforce this: keep isSolvable, applyMove, and isSolved in the same module, expose them through a single barrel, and forbid direct state mutation outside that module. A grep for board[...]= outside the file should be a code review failure.

Checklist for the Code Review

Before approving a 15-puzzle change, verify:

• [ ] Every public mutation goes through a move primitive that updates the blank position and the tile permutation atomically.
• [ ] isSolvable is called on every external state entry point: shuffle, save restore, URL-import, and seeded challenge load.
• [ ] The solved-state check is strict tile equality with the blank at index 15, not a heuristic.
• [ ] At least one unit test pins the parity rule with the blank on an even row from the bottom and one with an odd row.
• [ ] The shuffle path is either rejection sampling with a bounded retry count, or a constructive random walk of length 100+.
• [ ] No PDF, download, or vendor-specific link appears in error messages; failures resolve to stable docs.

That checklist, plus the parity function above, will catch every solvability regression I have seen in shipped builds.

Frequently Asked Questions

Does the parity rule change for 3×3 or 5×5 sliding puzzles?

Yes — the rule generalizes to any NxN board with a single blank. For odd-width grids (3×3, 5×5) the rule collapses to a single inversion parity: solvable iff the inversion count is even. For even-width grids the blank-row term appears, exactly as in the 4×4 case. The derivation is on the Wikipedia page linked above and is worth a careful read if you ship multiple sizes.

How do I handle boards imported from a URL or QR code?

Treat the import as untrusted. Run isSolvable on the deserialized state and refuse to load if it fails, with a clear message. Optionally offer a "shuffle to a solvable state" button so the user is not stranded. Never silently rewrite the user's input — they may be testing your gate.

Can the parity rule be bypassed to add "cheat" features like swapping any two tiles?

Technically yes — any state is reachable if you let the user perform arbitrary permutations — but doing so breaks every downstream feature that assumes the two-component invariant, including hint engines, save compatibility, and leaderboard validation. If you must ship a "free play" mode, isolate it behind a flag and never let its state cross into the main mode's persistence layer.

What is the smallest number of moves guaranteed to solve any legal state?

The worst-case optimal move count for the 15 puzzle is 80, established by exhaustive search. If your hint engine proposes more than 80 moves to a solved state, your search is misconfigured; if it proposes fewer for a legal state, your state is misconfigured. Use 80 as a sanity bound during development.

---

This article was drafted with AI assistance and reviewed for technical accuracy before publishing.