Fifteen Puzzle - Solvability

Solvability

Johnson & Story (1879) used a parity argument to show that half of the starting positions for the n-puzzle are impossible to resolve, no matter how many moves are made. This is done by considering a function of the tile configuration that is invariant under any valid move, and then using this to partition the space of all possible labeled states into two equivalence classes of reachable and unreachable states.

The invariant is the parity of the permutation of all 16 squares plus the parity of the taxicab distance (number of rows plus number of columns) of the empty square from the lower right corner. This is an invariant because each move changes both the parity of the permutation and the parity of the taxicab distance. In particular if the empty square is in the lower right corner then the puzzle is solvable if and only if the permutation of the remaining pieces is even.

Johnson & Story (1879) also showed that the converse holds on boards of size m×n provided m and n are both at least 2: all even permutations are solvable. This is straightforward but a little messy to prove by induction on m and n starting with m=n=2. Archer (1999) gave another proof, based on defining equivalence classes via a hamiltonian path.

Wilson (1974) studied the analogue of the 15 puzzle on arbitrary finite connected and non-separable graphs. (A graph is called separable if removing a vertex increases the number of components.) He showed that, except for polygons, and one exceptional graph on 7 vertices, it is possible to obtain all permutations unless the graph is bipartite, in which case exactly the even permutations can be obtained. The exceptional graph is a regular hexagon with one diagonal and a vertex at the center added; only 1/6 of its permutations can be obtained.

For larger versions of the n-puzzle, finding a solution is easy, but the problem of finding the shortest solution is NP-hard. For the 15-puzzle, lengths of optimal solutions range from 0 to 80 single-tile moves or 43 multi-tile moves; the 8-puzzle always can be solved in no more than 31 single-tile moves or 24 multi-tile moves (integer sequence A087725).

The symmetries of the fifteen puzzle form a groupoid (not a group, as not all moves can be composed); this groupoid acts on configurations.