The 15 Puzzle, invented over one hundred years ago by N. Chapman and popularized by Sam Loyd, can be described as a game played on a certain graph with 16 vertices, using 15 counters (numbered from 1 to 15) placed on 15 of the vertices, in which a counter can move from its current vertex to an unoccupied neighboring vertex. By a sequence of moves one wants to get the counters into another specified configuration. From a given the initial configuration, that is possible for exactly half of the 16! possible final configurations.

In the generalization, the graph is an arbitrary connected, simple, finite graph. The question is: from a given initial configuration, what fraction of the final configurations can be solved? This fraction is 1 or .5, almost but not quite always.

This talk is based on a paper by Richard M. Wilson, “Graph puzzles, homotopy, and the alternating group”, from the American Mathematical Monthly in 1974.