The 15 Puzzle:
A Century of Beautiful Mathematics
A simple grid of sliding tiles hid one of the most elegant theorems in combinatorics — and sparked a global obsession that shut down businesses, distracted ship captains, and drove mathematicians to their desks for decades.
In the winter of 1880, something strange swept through Boston. Shop owners arrived to find their clerks standing motionless behind counters, pushing small numbered squares around wooden trays. Pilots navigated poorly. Legislators neglected bills. A Baltimore newspaper editor, having stepped out for a noon lunch, was discovered by his staff long past midnight, still pushing little pieces of pie around on a plate.
"To the minds of the Bostonians there was something more than a mere puzzle in the game: it was a mathematical study, and its solution a science."
— The New York Sun, February 27, 1880The object of all this obsession was a 4×4 tray holding fifteen numbered tiles with one empty space. The goal: slide the tiles around until they read 1 through 15 in order, with the blank in the bottom-right corner. Simple to state. Wildly addictive to pursue. And secretly, a profound window into the structure of permutation groups.
What makes the 15 puzzle remarkable — mathematically — is not how hard it is to solve, but the fact that exactly half of all possible arrangements are impossible to solve, no matter how clever you are. Understanding why that is true requires the same machinery that underpins much of modern algebra.
The Craze of 1880
The puzzle was invented around 1874 by Noyes Chapman, a postmaster in Canastota, New York, who presented a prototype to the American Journal of Mathematics. But it was the toymaker Matthias Rice of Boston who manufactured the first commercial version — the "Gem Puzzle" — in December 1879, and the puzzle manufacturer Sam Loyd who turned it into a legend.
Click adjacent tiles to slide them · Arrow keys work too · Ctrl+Z to undo
Why Can't You Solve Half the Puzzle?
When you first encounter an unsolvable configuration, it feels like you simply haven't tried hard enough. But the impossibility is not practical — it is structural. The 15 puzzle lives in a world governed by the algebra of permutations, and the key insight is about parity.
Permutations and the Symmetric Group
Think of each configuration of the puzzle as a permutation $\alpha$ of the set $\{1, 2, \ldots, 15, 16\}$, where 16 represents the blank tile. The goal state is the identity permutation $e$.
Every legal slide of a tile is a transposition — it swaps the blank with one neighbouring tile. So each move is a transposition $(i\ 16)$ for some tile $i$. A sequence of $k$ moves produces a permutation that is a product of $k$ transpositions.
The critical observation: a permutation is called even if it can be written as a product of an even number of transpositions, and odd otherwise. This parity is well-defined — no permutation is both even and odd. The set of all even permutations forms a subgroup called the alternating group $A_{15}$, which has exactly $\frac{15!}{2}$ elements.
The Key Observation: The Blank Must Return Home
Here is the beautiful core argument. Suppose we start with the blank in box 16 (bottom-right) and make a sequence of moves to solve the puzzle, ending with the blank back in box 16. Since the blank travels a closed path, it must have moved an even number of steps — each move right must be undone by a move left, and similarly vertically. Therefore the total number of transpositions $k$ is even, and the resulting permutation is even. This proves:
A permutation $\alpha$ of the 15-puzzle which fixes position 16 (i.e. the blank starts and ends in the bottom-right corner) is solvable if and only if $\alpha \in A_{15}$ — that is, $\alpha$ is an even permutation.
This tells us the number of solvable positions when the blank must return to box 16:
What About the Blank Anywhere? — Parity of a Box
The full puzzle allows the blank to end up anywhere. The general solvability criterion requires a beautiful idea: colour the 16 cells like a checkerboard.
Define the parity of a box as: shaded boxes are even and white boxes are odd. This is the minimum number of moves needed to bring the blank from that box to box 16, modulo 2. Now we can state the full theorem:
A permutation $\alpha$ of the 15-puzzle is solvable if and only if the parity of $\alpha$ equals the parity of the box containing the empty space.
Combining both theorems: out of all $16!$ possible arrangements of the tiles, exactly half are solvable:
As a historical footnote: even in the 1950s, commercial puzzle manufacturers were still getting this count wrong. Instructions for Lowe's "14-15 Puzzle" stated there were $2{,}615{,}348{,}736{,}000$ configurations — exactly four times too small!
Counting Inversions: The Practical Test
The theorems above are elegant, but how do you quickly check whether a given configuration is solvable? The answer is an efficient algorithm based on inversions.
An inversion in a sequence is a pair of tiles $(i, j)$ where $i$ appears before $j$ in the flattened sequence but $i > j$. Intuitively, an inversion counts how "out of order" the arrangement is.
Example: Counting Inversions
Consider the sequence below. Highlighted tiles form inversions with the tile 3 — pairs where a larger number precedes 3:
( inversions + row_of_blank_from_bottom ) mod 2 = 0
The complete solvability algorithm is:
- Flatten the board into a 1D sequence (left-to-right, top-to-bottom), treating the blank as 0.
- Count the total number of inversions among the non-zero tiles.
- Find the row of the blank tile, counting from the bottom (so row 4 → 1, row 3 → 2, etc.).
- If (inversions + blank_row) is even, the puzzle is solvable. Otherwise it is not.
This is exactly what my Python code implements below.
Sam Loyd's Infamous $1,000 Prize
Loyd's impossible challenge was to start from the solved position and reach a state with tiles 14 and 15 swapped (and all others in place). A single transposition of two tiles is an odd permutation — it changes the parity. Since the goal state (identity) is an even permutation, and swapping tiles 14 and 15 produces an odd one, no sequence of legal slides can ever achieve it. Loyd knew this. The prize was a mathematical certainty he would never have to pay. Every person who tried simply confirmed the theorem, one frustrated attempt at a time.
The Python Solver: IDA* with Manhattan Distance
Knowing a puzzle is solvable is one thing. Finding the optimal solution is quite another. Optimal solving of the 15 puzzle is provably NP-hard in the general $n$-puzzle setting, but in practice the most effective algorithm is IDA* (Iterative Deepening A*), using the Manhattan distance heuristic.
The Manhattan Distance Heuristic
For each tile $t$ currently at position $(r, c)$, its goal position is $(r_t, c_t)$. The Manhattan distance contribution of tile $t$ is $|r - r_t| + |c - c_t|$. Summing over all tiles gives a lower bound on the number of moves remaining, making it an admissible heuristic. IDA* with this heuristic finds a provably optimal solution.
Here is the implementation. The key insight is that IDA* avoids the enormous memory cost of BFS/A* by doing repeated depth-limited DFS, increasing the cost threshold each iteration. A hard starting position (like the one in the Colab notebook below) required finding a 54-move optimal solution — and the solver found it, albeit in about 160 seconds.
N = 4
def get_inv_count(puzzle):
"""Count inversions in the flattened board (ignoring the blank)."""
flat = [x for row in puzzle for x in row]
inv = 0
for i in range(N * N - 1):
for j in range(i + 1, N * N):
if flat[i] and flat[j] and flat[i] > flat[j]:
inv += 1
return inv
def blank_row_from_bottom(puzzle):
"""Find the row of the blank (0), counting from the bottom (1-indexed)."""
for i in range(N - 1, -1, -1):
for j in range(N - 1, -1, -1):
if puzzle[i][j] == 0:
return N - i # row 4 → 1, row 3 → 2, ...
def is_solvable(puzzle):
"""
A 4×4 puzzle is solvable iff:
(inversions + blank_row_from_bottom) is even.
This follows from Theorem 9.1.2: parity of permutation
must equal parity of the box containing the empty space.
"""
inv = get_inv_count(puzzle)
row = blank_row_from_bottom(puzzle)
return (inv + row) % 2 == 0
# ── Example ────────────────────────────────────────
start = (0, 5, 9, 12, 15, 8, 14, 11, 1, 4, 13, 3, 6, 2, 10, 7)
puzzle = [list(start[i:i+4]) for i in range(0, 16, 4)]
print("Solvable" if is_solvable(puzzle) else "Not Solvable")
# → SolvableGOAL = (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0)
def manhattan(state):
"""Sum of Manhattan distances of all tiles from their goal positions."""
dist = 0
for i, tile in enumerate(state):
if tile != 0:
r, c = divmod(i, 4)
tr, tc = divmod(tile - 1, 4)
dist += abs(r - tr) + abs(c - tc)
return dist
def get_moves(state):
"""Yield (new_state, direction) for each legal slide."""
idx = state.index(0)
r, c = divmod(idx, 4)
for dr, dc, name in [(-1,0,'Up'),(1,0,'Down'),(0,-1,'Left'),(0,1,'Right')]:
nr, nc = r + dr, c + dc
if 0 <= nr < 4 and 0 <= nc < 4:
ns = list(state)
ni = nr * 4 + nc
ns[idx], ns[ni] = ns[ni], ns[idx]
yield tuple(ns), name
def solve(start):
"""IDA* search: returns the list of move directions for the optimal solution."""
threshold = manhattan(start)
path = [start]
moves = []
def search(g, bound):
node = path[-1]
f = g + manhattan(node)
if f > bound: return f
if node == GOAL: return "FOUND"
min_val = float('inf')
for nbr, name in get_moves(node):
if nbr not in path: # avoid revisiting
path.append(nbr); moves.append(name)
res = search(g + 1, bound)
if res == "FOUND": return "FOUND"
if res < min_val: min_val = res
moves.pop(); path.pop()
return min_val
while True:
res = search(0, threshold)
if res == "FOUND": return moves
if res == float('inf'): return None # unsolvable
threshold = res
# ── Run ────────────────────────────────────────────
import time
start_state = (0,5,9,12,15,8,14,11,1,4,13,3,6,2,10,7)
t0 = time.time()
sol = solve(start_state)
print(f"Solved in {len(sol)} moves in {time.time()-t0:.1f}s")
print(" → ".join(sol))
# → Solved in 54 moves in 161.5s
The 54-move solution for the starting configuration
(0,5,9,12,15,8,14,11,1,4,13,3,6,2,10,7) took about
160 seconds to find — a reminder that even with an excellent
heuristic, the search tree for hard positions is enormous. Faster approaches include
bidirectional search, pattern databases, and the state-of-the-art
divide-and-conquer solvers used in competitive speedsolving.
What the Computer Found
The optimal move sequence for this particular starting position was:
Every one of those 54 moves was necessary. Remove any one, and you cannot solve the puzzle. This is the beauty of admissible heuristics — IDA* with Manhattan distance guarantees optimality.
A Humble Tray of Tiles
The 15 puzzle is, in miniature, an introduction to one of the central themes of modern mathematics: the idea that symmetry has algebraic structure. The set of solvable positions is not just "about half" the total — it is precisely the alternating group $A_{15}$, a perfectly defined mathematical object with 653 billion elements.
Sam Loyd never had to pay his $1,000. But in offering the prize, he inadvertently gave generations of mathematicians a beautifully concrete example of parity, permutation groups, and the power of algebraic reasoning. Every time you slide a tile, you are performing a transposition. Every time you solve the puzzle, you have written the identity element as a product of even permutations.
And every time you find yourself staring at an arrangement that won't resolve, no matter what you try — you have found one of the 10.4 trillion odd permutations. You are not failing. The mathematics is simply telling you no.
"The mysterious feature of the puzzle is that no one seems to be able to recall the sequence of moves whereby they feel sure they succeeded in solving the puzzle."
— Jerry Slocum, The 15 PuzzleGo ahead and try the puzzle above again. This time, you know the theory behind it. Count your inversions. Check the parity. And when you finally slide that last tile into place, know that you just navigated a 10-trillion-state combinatorial space guided only by human intuition — which is, in its own way, just as beautiful as the algebra that governs it.
Comments
Post a Comment