8-Puzzle / 15-Puzzle

Problem. Tiles numbered $\mathrm{1..}{n}^2-1$ in an $n\times n$ grid with one blank. A move slides an adjacent tile into the blank. Reach the goal configuration in the fewest moves.

Solvability — the parity invariant

Not every configuration is reachable. Define:

• $\mathrm{inv}$ = the number of inversions in the tile sequence (reading row by row, ignoring the blank);
• $r$ = the blank’s row, counted from the bottom, 1-indexed.

Board	Solvable iff
$n$ odd (e.g. 3×3)	$\mathrm{inv}$ is even
$n$ even (e.g. 4×4)	$\mathrm{inv}+r$ is odd

Why: each move changes the blank’s row parity by 0 or 1, and changes $\mathrm{inv}$ by an even number for horizontal moves, or by an odd number for vertical ones. The combination $\mathrm{inv}+r$ is therefore invariant mod 2. Exactly half of all configurations are reachable.

bool solvable(const vector<int>& board, int n) {
    int inv = 0, blankRow = 0;
    vector<int> a;
    for (int i = 0; i < n * n; i++) {
        if (board[i] == 0) { blankRow = n - i / n; continue; }
        a.push_back(board[i]);
    }
    for (int i = 0; i < (int)a.size(); i++)
        for (int j = i + 1; j < (int)a.size(); j++)
            if (a[i] > a[j]) inv++;
    return (n % 2) ? (inv % 2 == 0) : ((inv + blankRow) % 2 == 1);
}

This is the invariant argument in its purest form — it settles half of all inputs in $O(n^2)$ with no search at all.

Solving it

Board	State space	Method
8-puzzle (3×3)	$9!/2=181440$	BFS over all states, or A*
15-puzzle (4×4)	$16!/2\approx 10^{13}$	IDA* with a good heuristic
24-puzzle (5×5)	$\approx 10^{25}$	IDA* with pattern databases

A* and IDA*

Use $f=g+h$ with an admissible heuristic $h$ (never overestimating):

Heuristic	Quality
Misplaced tiles	weak
Manhattan distance	the standard baseline
Manhattan + linear conflict	noticeably better
Walking distance	stronger
Pattern databases	by far the strongest; solves the 15-puzzle in milliseconds

IDA* (iterative-deepening A*) is preferred over A* here because A*‘s open list does not fit in memory for the 15-puzzle. IDA* uses $O(d)$ space:

int search(State& s, int g, int bound) {
    int f = g + h(s);
    if (f > bound) return f;                       // exceeded: report the new bound
    if (s.isGoal()) return FOUND;
    int minExceed = INF;
    for (Move m : s.moves()) {
        if (m.undoes(lastMove)) continue;          // essential pruning
        s.apply(m);
        int t = search(s, g + 1, bound);
        if (t == FOUND) return FOUND;
        minExceed = min(minExceed, t);
        s.undo(m);
    }
    return minExceed;
}
// outer loop: bound = h(start); repeat with bound = returned value

Never undoing the previous move is the single most important pruning — it halves the branching factor.

Bidirectional BFS

Since the goal is known, searching from both ends turns $b^d$ into $2b^{d/2}$. For the 8-puzzle this makes plain BFS trivial; for the 15-puzzle it helps but is not enough on its own.

God’s number

Puzzle	Maximum optimal moves
8-puzzle	31
15-puzzle	80
24-puzzle	152 (conjectured)
Rubik’s cube (quarter turns)	26
Rubik’s cube (half turns)	20

The Rubik’s cube number 20 was proved in 2010 by an exhaustive computation using coset decomposition — 35 CPU-years donated by Google.

The general lesson: state-space search

The 15-puzzle is the reference problem for the whole search toolkit:

Technique	Role
BFS	optimal, but memory-bound
A*	guided by a heuristic; still memory-bound
IDA*	A*‘s guidance with DFS memory
Bidirectional search	halves the exponent
Pattern databases	precomputed admissible heuristics
Invariant checking	rules out half the inputs instantly
Symmetry reduction	shrinks the effective state space

The same combination solves Rubik’s cube, sliding-block puzzles, Sokoban (PSPACE-complete), and general planning problems.

Why it is worth knowing

Two lessons: check for an invariant before searching (it may answer the question outright), and a good admissible heuristic beats a faster search — Manhattan distance turns an intractable 15-puzzle into a solvable one, which no amount of BFS optimisation would achieve.

See also: A* Algorithm · Invariants · BFS