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.
Then if 
is even, the position is possible, otherwise it is
not. In other words, if the permutation symbol 
of the list is 
, the position is possible, whereas if the signature is 
, it is not. This can be formally proved
using alternating groups. For example, in the
arrangement shown above, 
(2 precedes 1) and all other 
,
so 
and the puzzle 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.
While odd permutations of the puzzle are impossible to solve (Johnson 1879), all even permutations are
solvable (Story 1879). Despite the assertion of Herstein and Kaplansky (1978) that
"no really easy proof seems to be known," Archer (1999) presented a simple
proof. A more general result due to Wilson (1974) showed that for any connected
graph on 
nodes, with the exception of cycle graphs 
and the theta0 graph,
either exactly half or all of the 
possible labelings are obtainable by sliding labels, depending
on whether the graph is bipartite (Archer 1999).
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