The "15 puzzle" is a sliding square puzzle commonly (but incorrectly) attributed to Sam Loyd. However, research by Slocum and Sonneveld (2006) has revealed that Sam Loyd did not invent the 15 puzzle and had nothing to do with promoting or popularizing it. The puzzle craze that was created by the 15 puzzle began in January 1880 in the United States and in April in Europe and ended by July 1880. Loyd first claimed in 1891 that he invented the puzzle, and he continued until his death a 20 year campaign to falsely take credit for the puzzle. The actual inventor was Noyes Chapman, the Postmaster of Canastota, New York, and he applied for a patent in March 1880.
The 15 puzzle consists of 15 squares numbered from 1 to 15 that are placed in a 
box leaving one position out of the 16 empty. The goal is to reposition the squares
from a given arbitrary starting arrangement by sliding them one at a time into the
configuration shown above. For some initial arrangements, this rearrangement is possible,
but for others, it is not.
To address the solubility of a given initial arrangement, proceed as follows. If the square containing the number 
appears "before" (reading the squares
in the box from left to right and top to bottom) 
numbers that are less than 
, then call it an inversion of order 
, and denote it 
. Then define
 |
where the sum need run only from 2 to 15 rather than 1 to 15 since there are no numbers less than 1 (so 
must equal 0). Stated more simply, 
is the number of permutation
inversions in the list of numbers. Also define 
to be the row number of the empty square,
counting the rows from 1 to 4 from the top.
The position is solvable iff 
is even. When the empty square is in the fourth row, this is equivalent to requiring
the permutation symbol 
of the numbered tiles to be 
. For example, in the arrangement shown above, 
(2 precedes 1) and all other 
, so 
and 
.
The puzzle therefore cannot be solved.
Similarly, in the above random arrangement of squares, the inversion counts are 12, 9, 9, 5, 4, 4, 3, 3, 0, 3, 3, 2, 1, 1, and 0, giving an inversion sum of 59. Since this number is odd, the above arrangement of the puzzle cannot be solved.
When the empty square starts and ends in the same position, odd permutations of the numbered tiles are impossible
to obtain (Johnson 1879), while all even permutations are
obtainable (Story 1879). Moving the empty square once
around a 
block produces a permutation cycle of length
3 on the other three tiles and returns the empty square
to its starting position. The attainable permutations
of the numbered tiles form the alternating group 
. Despite the assertion of Herstein
and Kaplansky (1978) that "no really easy proof seems to be known," Archer
(1999, pp. 795-797) presented a simple proof using permutation
cycles.
A more general result due to Wilson (1974) showed that for any biconnected graph on 
vertices, with the exception of cycle
graphs 
and the theta0 graph, exactly half of
the 
possible labelings are obtainable by
sliding labels when the graph is bipartite,
and all are obtainable otherwise (Archer 1999, pp. 798-799). Here one label
represents the empty square, and a move exchanges that
label with a label on an adjacent vertex. 
has six inequivalent labelings, while 
has 
inequivalent labelings.
Reversing the order of the "8 Puzzle" made on a 
board can be proved to require at least 26 moves, although
the best solution requires 30 moves (Gardner 1984, pp. 200 and 206-207). The
number of distinct solutions in 28, 30, 32, ... moves are 0, 10, 112, 512, ... (OEIS
A046164), giving 634 solutions better than
the 36-move solution given by Dudeney (1949).
The maximum number of moves required to solve the 
generalization of the 15 puzzle for 
, 2, ... are 0, 6, 31, 80, ... (OEIS A087725;
Brüngger et al. 1999).
-Extension of the 15-Puzzle
Is Intractable." J. Symbolic Comp 10, 111-137, 1990.Sloane,
N. J. A. Sequences