15 Puzzle

The game consists of fifteen small squares numbered one to fifteen. These can be moved horizontally or vertically in a square frame of 4x4 fields, whereby the vacant field serves as the alternative space. The aim of the game is to arrange the fifteen scrambled numbers in the correct order with the vacant space in the bottom right-hand corner.  

History

Also known as the Boss Puzzle, the game was invented in the USA in the 1870s and soon caught on. Its success is comparable with that of the Rubik's Cube in the 1980s.   

In around 1880, Sam Loyd presented the problem called the 14–15 Puzzle: to start with, all the numbers appear in the correct order except for fourteen and fifteen, which are the wrong way around. He offered a USD 1,000 prize to anyone who could solve the problem. Many people entered the competition, but nobody won as the problem is unsolvable.   

Mathematics

There is a simple criterion to determine whether the problem is solvable or not: you imagine the four rows arranged in a line and count the pairs of numbers which are in the incorrect order. If the number is even, the problem can be solved; otherwise, it is unsolvable. In mathematical jargon, the criterion can be described as follows: with a fully executed move (with the empty field on the bottom right), the parity of the permutation of the numbers one to fifteen remains intact. As the basic position is an even permutation, starting positions are only solvable if they are even permutations. Nonetheless, the questions as to how many moves are required and how the puzzle can be solved in the smallest number of moves remain open.