The Math of the 15-Puzzle: Solvability Algorithms, Inversions & Solving Strategies

Invented in the 1870s by Noyes Palmer Chapman and popularized by master puzzler Sam Loyd, the 15-Puzzle is one of the most famous sliding block mathematical puzzles in history. It consists of a 4x4 frame containing 15 numbered square tiles and one blank space.

In 1880, Sam Loyd offered a colossal $1,000 cash prize (equivalent to over $30,000 today) to anyone who could solve the puzzle starting with just the 14 and 15 tiles swapped. Millions of people bought the puzzle attempting to claim the prize, but nobody ever succeeded.

Mathematically, it was impossible. Here is the mathematical proof of solvability, the concept of inversion parity, and the algorithmic strategy to solve any valid puzzle.

---

The Mathematics of Solvability: Inversions and Parity

When generating a randomized sliding puzzle, exactly 50% of all possible permutations are mathematically unsolvable.

To determine whether any given configuration can be rearranged into sequential order, mathematicians calculate the number of inversions:

What is an Inversion?

An inversion occurs whenever a higher-numbered tile precedes a lower-numbered tile in the sequential order of the board (reading left-to-right, top-to-bottom), ignoring the empty space (0).

For instance, in the sequence [1, 2, 4, 3], the pair (4, 3) is an inversion because 4 is greater than 3 even though 4 appears first.

The Solvability Theorem for Even Grids (4x4):

For a grid with an even width (N = 4), a puzzle configuration is solvable if and only if:

1. The blank tile is on an odd row from the bottom (1st or 3rd row from bottom) AND the total number of inversions is even.
2. OR the blank tile is on an even row from the bottom (2nd or 4th row from bottom) AND the total number of inversions is odd.

In formulaic terms:

Solvable = (Inversions + Blank Row from Bottom) is ODD

In Sam Loyd's infamous swapped puzzle, the tiles 14 and 15 had an inversion count of 1 (odd) while the blank tile remained in the bottom corner (row 1, odd), making the configuration strictly unsolvable under valid sliding moves.

---

Step-by-Step Solving Strategy: Layer by Layer

To solve any solvable 15-puzzle systematically in minimal moves without undoing previous progress, use the row-by-row reduction algorithm:

Step 1: Solve the First Row (Tiles 1, 2, 3, 4)

• Place tile 1, then tile 2, then tile 3 into their correct spots.
• To position tile 4 without displacing 3, maneuver 4 directly below the top-right corner, position 3 to its left, and rotate them into position [1, 2, 3, 4].
• Row 1 is now permanently locked.

Step 2: Solve the Second Row (Tiles 5, 6, 7, 8)

• Repeat the exact same technique for row two: position 5, 6, 7, and swing 8 into place.
• The remaining puzzle is now reduced to a smaller 2x4 sub-grid.

Step 3: Solve the Leftmost Columns (Tiles 9 and 13)

• Instead of solving horizontally, solve vertically down the left edge.
• Move 9 to its slot, maneuver 13 directly adjacent, and slide both into the first column.

Step 4: Rotate the Final 2x3 Box (Tiles 10, 11, 12, 14, 15)

• With only 5 tiles and 1 blank remaining, cyclically rotate the tiles around the perimeter of the 2x3 area until all numbers drop naturally into sequential order.

---

Cognitive and Algorithmic Relevance

In computer science and artificial intelligence, the 8-puzzle and 15-puzzle serve as foundational benchmarks for teaching search heuristics:

• Breadth-First Search (BFS): Explores all branches equally to guarantee the shortest move sequence.
• A-Star Search with Manhattan Distance: Evaluates board states by calculating the sum of horizontal and vertical distances of each tile from its target position, finding optimal solutions in milliseconds.

Play our guaranteed-solvable 15-Puzzle Sliding Tiles online with both 3x3 and 4x4 boards and move tracking.