Solving the 15-Puzzle with Permutation Parity and IDA* — Proving Sam Loyd's 14-15 Swap Impossible Without Search

The classic 15-puzzle, built for the browser with two real algorithms inside. (1) Solvability is decided by permutation parity, with zero search — Sam Loyd's 1890s prize board (solved, but with 14 and 15 swapped) is provably impossible in O(n²) arithmetic. (2) The solver is IDA* with Manhattan distance + linear conflict, finding a shortest solution and animating it. Tests go as far as cross-checking IDA* lengths against exact BFS optima. Solver-equipped puzzle #3, after Sudoku (#33) and Lights Out (#284).

🌐 Live demo: https://sen.ltd/portfolio/fifteen-puzzle/
📦 GitHub: https://github.com/sen-ltd/fifteen-puzzle

Parity: proving impossibility without search

Every slide is a transposition of the blank with one tile. Count the board's
inversions (pairs of tiles out of order). A horizontal slide never changes
them; a vertical slide carries one tile past exactly n-1 others. The rule
therefore splits by board width:

• odd width (3×3): n-1 is even, so inversion parity alone is invariant — solvable ⇔ inversions even.
• even width (4×4): each vertical slide flips inversion parity and moves the blank one row — so inversions + (blank's row distance from home) is the invariant.

Sam Loyd's prize puzzle — the solved board with only 14 and 15 swapped — is off
by exactly one transposition of parity, so it's unsolvable, provable in a
page of arithmetic. The Loyd trap button in the demo sets it up; the solver
answers "provably unsolvable" without expanding a single node.

The trap I stepped in

My first version applied the even-width rule to 3×3 as well. The randomized
tests (50 random-walk boards must all be solvable) and a BFS cross-check
caught it instantly. The parity rule genuinely differs by width — a classic
textbook trap, and a nice case of tests catching a misunderstood spec rather
than a typo.

IDA*: shortest solutions in O(depth) memory

A* finds shortest solutions but holds an exponential frontier. IDA*
(iterative-deepening A*) runs depth-first search bounded by f = g + h,
retrying with the smallest overshoot as the next bound — same optimality, memory
proportional to solution depth:

for (;;) {
  const t = dfs(0, -1);          // DFS, pruned at f > bound
  if (t === -1) return { moves: path, nodes };
  bound = t;                     // smallest f that exceeded the old bound
}

The heuristic is Manhattan + linear conflict: two tiles in their home row
(or column) but in reversed order must pass each other — 2 extra moves per pair,
still admissible, far sharper than Manhattan alone. A medium scramble solves
optimally in well under a second; the status line reports moves, nodes, and time
(the screenshot shows a 44-move optimum in 700k nodes / 529 ms).

Testing: cross-check against BFS

18 vitest cases: parity classifications (including the Loyd board), random-walk
scrambles always solvable, replay-verified solves on 3×3 and 4×4, heuristic
admissibility — and the strongest one, IDA* solution lengths matching exact
BFS optima on random 8-puzzles:

const opt = bfs(b);            // exact brute-force optimum
const r = solve(3, b);
expect(r.moves!.length).toBe(opt);

If you claim optimality, verify it with a different algorithm — a running theme
in this solver-equipped puzzle series.

src/puzzle.ts      — pure engine: parity test, Manhattan + linear conflict, IDA*, scrambles
src/puzzle.test.ts — 18 cases (parity, admissibility, replay-verified, BFS cross-check)
src/main.ts        — DOM shell: grid, click-to-slide, animated solve, Loyd trap

Takeaway

The 15-puzzle is a rare exhibit where proof of impossibility (parity) and
optimal search (IDA*) share one small board. Try the Loyd trap in the demo
and watch a 130-year-old prize problem get judged "impossible" instantly.

🌐 Live demo: https://sen.ltd/portfolio/fifteen-puzzle/
📦 GitHub: https://github.com/sen-ltd/fifteen-puzzle