15 Puzzle

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).

REFERENCES

Archer, A. F. "A Modern Treatment of the 15 Puzzle." Amer. Math. Monthly 106, 793-799, 1999.

Ball, W. W. R. and Coxeter, H. S. M. Mathematical Recreations and Essays, 13th ed. New York: Dover, pp. 312-316, 1987.

Beasley, J. D. The Mathematics of Games. Oxford, England: Oxford University Press, pp. 80-81, 1990.

Berlekamp, E. R.; Conway, J. H; and Guy, R. K. Winning Ways for Your Mathematical Plays, Vol. 2: Games in Particular. London: Academic Press, 1982.

Bogomolny, A. "Sam Loyd's Fifteen." http://www.cut-the-knot.org/pythagoras/fifteen.shtml.Bogomolny, A. "Sam Loyd's Fifteen [History]." http://www.cut-the-knot.org/pythagoras/history15.shtml.Brüngger, A.; Marzetta, A.; Fukuda, K.; and Nievergelt, J. "The Parallel Search Bench ZRAM and Its Applications." Ann. Oper. Res. 90, 45-63, 1999.

Davies, A. L. "Rotating the 15 Puzzle." Math. Gaz. 54, 237-240, 1970.

Dudeney, H. E. Problem 253 in The Canterbury Puzzles and Other Curious Problems, 7th ed. London: Thomas Nelson and Sons, 1949.

Gardner, M. The Sixth Book of Mathematical Games from Scientific American. Chicago, IL: University of Chicago Press, pp. 64-65, 200-201, and 206-207, 1984.

Herstein, I. N. and Kaplansky, I. Matters Mathematical, 2nd ed. New York: Chelsea, pp. 114-115, 1978.

Hurd, S. and Trautman, D. "The Knight's Tour on the 15-Puzzle." Math. Mag. 66, 159-166, 1993.

Johnson, W. W. "Notes on the '15 Puzzle. I.' " Amer. J. Math. 2, 397-399, 1879.

Kasner, E. and Newman, J. R. Mathematics and the Imagination. Redmond, WA: Tempus Books, pp. 177-180, 1989.

Korf, R. E. "Depth-First Iterative-Deeping: An Optimal Admissible Tree Search." Artificial Intelligence 27, 97-110, 1985.

Korf, R. E. and Taylor, L. A. "Finding Optimal Solutions to the Twenty-Four Puzzle." In Proceedings of the 11th National Conference on Artificial Intelligence, pp. 756-761, 1993.

Kraitchik, M. "The 15 Puzzle." §12.2.1 in Mathematical Recreations. New York: W. W. Norton, pp. 302-308, 1942.

Liebeck, H. "Some Generalizations of the 14-15 Puzzle." Math. Mag. 44, 185-189, 1971.

Loyd, S. Mathematical Puzzles of Sam Loyd, Vol. 1. New York: Dover, pp. 19-20, 1959.

Loyd, S. Jr.Sam Loyd's Cyclopedia of 5000 Puzzles, Tricks, and Conundrums.Lamb Pub., 1993.

Mallison, H. V. "An Array of Squares." Math. Gaz. 24, 119-121, 1940.

Ratner, D. and Warmuth, M. "Finding a Shortest Solution for the -Extension of the 15-Puzzle Is Intractable." J. Symbolic Comp 10, 111-137, 1990.

Sloane, N. J. A. Sequences A046164 and A087725 in "The On-Line Encyclopedia of Integer Sequences."Slocum, J. and Sonneveld, D. The 15 Puzzle: How It Drove the World Crazy. The Puzzle that Started the Craze of 1880. How America's Greatest Puzzle Designer, Sam Loyd, Fooled Everyone for 115 Years. Beverly Hills, CA: Slocum Puzzle Foundation, 2006.Spitznagel, E. L. Jr. Selected Topics in Mathematics. New York: Holt, Rinehart and Winston, pp. 143-148, 1971.

9Spitznagel, E. L. Jr. "A New Look at the Fifteen Puzzle." Math. Mag. 40, 171-174, 1967.

Steinhaus, H. Mathematical Snapshots, 3rd ed. New York: Dover, pp. 14-16, 1999.

Story, W. E. "Notes on the '15 Puzzle. II.' " Amer. J. Math. 2, 399-404, 1879.

Whipple, F. J. W. "The Sign of a Term in the Expansion of a Determinant." Math. Gaz. 13, 126, 1926.Wilson, R. M. "Graph Puzzles, Homotopy, and the Alternating Group." J. Combin. Th. Ser. B 16, 86-96, 1974.