15 puzzle

The goal of the puzzle is to place the tiles in numerical order (from left to right, top to bottom).

Commonly used heuristics for this problem include counting the number of misplaced tiles and finding the sum of the taxicab distances between each block and its position in the goal configuration.

[1] 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 binary function of the tile configuration that is invariant under any valid move and then using this to partition the space of all possible labelled states into two mutually inaccessible equivalence classes of the same size.

In particular, if the empty square is in the lower right corner, then the puzzle is solvable only if the permutation of the remaining pieces is even.

Johnson & Story (1879) also showed that on boards of size m × n, where m and n are both larger or equal to 2, all even permutations are solvable.

Archer (1999) gave another proof, based on defining equivalence classes via a Hamiltonian path.

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 attained, which gives an instance of the exotic embedding of S5 into S6.

Copies of the improved 15 puzzle made their way to Syracuse, New York, by way of Chapman's son, Frank, and from there, via sundry connections, to Watch Hill, Rhode Island, and finally to Hartford, Connecticut, where students in the American School for the Deaf started manufacturing the puzzle.

In late January 1880, Charles Pevey, a dentist in Worcester, Massachusetts, garnered some attention by offering a cash reward for a solution to the 15 Puzzle.

[1] This is impossible, as had been shown over a decade earlier by Johnson & Story (1879), because it requires a transformation from an even to an odd permutation.

[19] He had been timed to be able to solve it within 25 seconds; Fischer demonstrated this on November 8, 1972, on The Tonight Show Starring Johnny Carson.