xxxviii. Fifteen Puzzle

Problem. Fifteen numbered tiles and one blank in a $4\times 4$ frame; a move slides a tile into the blank. Which positions can be solved, and how to solve them optimally? Sam Loyd’s famous “14–15” prize (the solved board with 14 and 15 swapped) is impossible.

Fact	Value
solvable iff ($C$ odd) inversions even; ($C$ even) inversions + blank row has the parity of $R-1$	slidingSolvable in Parity, Coloring and Mod Observations
reachable positions of an $R\times C$ board ($R,C\ge 2$)	$(RC)!/2$
8-puzzle ($3\times 3$)	$181440$ positions, hardest need 31 moves (2 positions)
15-puzzle ($4\times 4$)	$\approx 1.05\cdot 10^{13}$ positions, hardest need 80 moves (Brüngger et al. 1999; Korf’s complete BFS 2008)
optimal solving	IDA* with an admissible heuristic: Manhattan distance + linear conflicts (fine for $4\times 4$), pattern databases (for $5\times 5$)
finding some solution	layer-by-layer method (place the top row, then the left column, recurse): $O(n)$ moves per tile, $O(n^3)$ in total on $n\times n$
finding a shortest solution of the $n\times n$ puzzle	NP-hard (Ratner and Warmuth, 1990)

// R x C sliding puzzle, row-major, 0 = blank, goal 1..RC-1 then the blank. Optimal move count by IDA*.
// Heuristic: Manhattan distance + 2 per tile that must leave its goal row (or column) to resolve a linear conflict.
struct Sliding {
    int R, C; vector<int> b;
    int h() const {
        int s = 0;
        for (int i = 0; i < R * C; i++) if (b[i]) { int g = b[i] - 1; s += abs(i / C - g / C) + abs(i % C - g % C); }
        auto mustLeave = [](const vector<int>& v) {          // |v| - LIS(v): tiles that cannot keep their order
            vector<int> d; for (int x : v) { auto it = lower_bound(all(d), x); if (it == d.end()) d.push_back(x); else *it = x; }
            return sz(v) - sz(d);
        };
        for (int r = 0; r < R; r++) {
            vector<int> v; for (int c = 0; c < C; c++) { int t = b[r * C + c]; if (t && (t - 1) / C == r) v.push_back((t - 1) % C); }
            s += 2 * mustLeave(v);
        }
        for (int c = 0; c < C; c++) {
            vector<int> v; for (int r = 0; r < R; r++) { int t = b[r * C + c]; if (t && (t - 1) % C == c) v.push_back((t - 1) / C); }
            s += 2 * mustLeave(v);
        }
        return s;
    }
    bool dfs(int z, int prev, int g, int bound, int& next) {
        int hv = h(), f = g + hv;
        if (f > bound) { next = min(next, f); return false; }
        if (hv == 0) return true;                             // h = 0 only at the goal
        for (int y : {z - C, z + C, z - 1, z + 1}) {
            if (y < 0 || y >= R * C || (abs(y - z) == 1 && y / C != z / C) || y == prev) continue;
            swap(b[z], b[y]); bool ok = dfs(y, z, g + 1, bound, next); swap(b[z], b[y]);
            if (ok) return true;
        }
        return false;
    }
    int solve() {                                             // call only on solvable boards
        int z = int(find(all(b), 0) - b.begin()), bound = h();
        while (true) { int next = INT_MAX; if (dfs(z, -1, 0, bound, next)) return bound; bound = next; }
    }
};

Proof: solvability, the 14–15 puzzle, and the state count

Necessity is the invariant proved in Parity, Coloring and Mod Observations: with the blank back at its home cell, only even permutations of the tiles can occur. Loyd’s position is a single transposition with the blank at home, an odd permutation: impossible.

Sufficiency. Let $G$ be the group of tile permutations produced by blank tours that start and end at the home cell. A tour that goes out along a path $\pi$ to a corner of a $2\times 2$ block, once around the block, and back along $\pi$ produces a 3-cycle (going around the block rotates its three tiles; walking $\pi$ and back conjugates). Every closed tour is, up to immediate back-and-forth steps (which do nothing), a product of such lassos, since the faces of the planar grid graph generate its cycle space; so $G$ is generated by 3-cycles and lies in $A_{RC-1}$. That it is all of $A_{RC-1}$ for $R,C\ge 2$ (except $2\times 2$, where the board is a single 4-cycle) is the grid case of Wilson’s theorem (1974): for a 2-connected graph that is not a cycle and not the exceptional graph ${\theta }_0$, the sliding-token puzzle realizes exactly the even permutations if the graph is bipartite. For $2\times 2$, rotating the blank around the cycle realizes the 3 rotations, which are exactly $A_3$. So every position satisfying the parity condition is reachable, and the reachable positions are half of all $(RC)!$ arrangements. BFS confirms it on $2\times 2$, $2\times 3$, $2\times 4$, $2\times 5$ and $3\times 3$, and finds 31 as the largest optimal distance of the 8-puzzle.

Proof: the heuristic is admissible, so IDA* is optimal

Each move moves one tile one cell, so a tile needs at least its Manhattan distance in moves; summing over tiles gives a lower bound. Now take a row $r$ and the tiles currently in it whose goal row is $r$: they need no vertical move for their Manhattan term. Tiles in the same row cannot pass each other without one of them leaving the row, so the tiles that never leave keep their relative order and must already be in goal order: they form an increasing subsequence of the goal columns. Hence at least $k-\mathrm{LIS}$ of them leave the row and come back, each spending at least 2 vertical moves not counted by Manhattan. Columns are symmetric with horizontal moves. The extra moves charged to rows are vertical moves of tiles with zero vertical distance, those charged to columns are horizontal moves of tiles with zero horizontal distance, so no move is counted twice: $h$ never overestimates.

IDA*. Iteration with bound $B$ explores every path whose nodes all have $f=g+h\le B$. If an optimal solution has length $d$, every node on it has $f\le d$ (admissibility), so the iteration with $B\ge d$ finds it; bounds only grow to the smallest $f$ that exceeded the previous bound, so no bound in $(B_{\text{prev}},B)$ is skipped and the first success occurs at $B=d$, returning $d$. Checked: $h\le$ BFS distance for all $181440$ positions of the 8-puzzle and all $1814400$ of the $2\times 5$ board, solve() equals the BFS distance on random positions, and on $4\times 4$ random scrambles the answer has the scramble’s parity and never exceeds its length.

Related notes

• A*, IDA* and Branch and Bound
• Parity, Coloring and Mod Observations
• Rubik’s Cube and Permutation Puzzles