thumb|To solve the puzzle, the numbers must be rearranged into numerical order from left to right, top to bottom.

The 15 puzzle (also called Gem Puzzle, Boss Puzzle, Game of Fifteen, Mystic Square and more) is a sliding puzzle. It has 15 square tiles numbered 1 to 15 in a frame that is 4 tile positions high and 4 tile positions wide, with one unoccupied position. Tiles in the same row or column of the open position can be moved by sliding them horizontally or vertically, respectively. The goal of the puzzle is to place the tiles in numerical order (from left to right, top to bottom).

Named after the number of tiles in the frame, the 15 puzzle may also be called a "16 puzzle", alluding to its total tile capacity. Similar names are used for different sized variants of the 15 puzzle, such as the 8 puzzle, which has 8 tiles in a 3×3 frame.

The n puzzle is a classical problem for modeling algorithms involving heuristics. 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. For the 15 puzzle, lengths of optimal solutions range from 0 to 80 single-tile moves (there are 17 configurations requiring 80 moves) or 43 multi-tile moves; the 8 Puzzle always can be solved in no more than 31 single-tile moves or 24 multi-tile moves (integer sequence A087725). The multi-tile metric counts subsequent moves of the empty tile in the same direction as one. In 2016, the upper bound was improved to 205 single-tile moves.

Group theory

The transformations of the 15 puzzle form a groupoid (not a group, as not all moves can be composed); this groupoid acts on configurations.

Because the combinations of the 15 puzzle can be generated by 3-cycles, it can be proved that the 15 puzzle can be represented by the alternating group <math>A_{15}</math>. In fact, any <math>2 k - 1</math> sliding puzzle with square tiles of equal size can be represented by <math>A_{2 k - 1}</math>.

History

thumb|right|[[Sam Loyd's unsolvable 15 Puzzle, with tiles 14 and 15 exchanged. This puzzle is not solvable as it would require a change of the invariant to move it to the solved state.]]

thumb|U.S. political cartoon about finding a Republican presidential candidate in 1880

The puzzle was "invented" by Noyes Palmer Chapman,

Chapman applied for a patent on his "Block Solitaire Puzzle" on February 21, 1880. However, this patent was rejected, likely because it was not sufficiently different from the August 20, 1878 "Puzzle-Blocks" patent (US 207124) granted to Ernest U. Kinsey.

Sam Loyd

thumb|left|Sam Loyd's 1914 illustration of the unsolvable variation

From 1891 until his death in 1911, Sam Loyd claimed that he had invented the puzzle. However, Loyd had no connection to the invention or initial popularity of the puzzle. Loyd's first article about the puzzle was published in 1886, and it was not until 1891 that he first claimed to be the inventor.

Some later interest was fueled by Loyd's offer of a $1,000 prize () to anyone who could provide a solution for achieving a particular combination specified by Loyd, namely reversing the 14 and 15, which Loyd called the 14-15 puzzle. This is impossible, as had been shown over a decade earlier by , because it requires a transformation from an even to an odd permutation.

Varieties of the 15 puzzle

The Minus Cube, manufactured in the USSR, is a 3D puzzle with similar operations to the 15 Puzzle.

Versions of the 15 puzzle include a different number of tiles, such as the 8-puzzle or 24-puzzle.

Pop culture

Chess world champion Bobby Fischer was an expert at solving the 15 puzzle. He had been timed to be able to solve it within 17 seconds; Fischer demonstrated this on November 8, 1972, on The Tonight Show Starring Johnny Carson.

See also

  • Combination puzzles
  • Jeu de taquin, an operation on skew Young tableaux similar to the moves of the 15 puzzle
  • Klotski
  • Mechanical puzzles
  • Pebble motion problems
  • Rubik's Cube
  • Three cups problem

Notes

References

  • Edward Kasner & James Newman (1940) Mathematics and the Imagination, pp 177&ndash;80, Simon & Schuster.
  • The history of the 15 puzzle
  • 15 Puzzle Game
  • Fifteen Puzzle Solution
  • Maximal number of moves required for the m X n generalization of the 15 puzzle
  • 15-Puzzle Optimal Solver with download (from Herbert Kociemba)