The fifteen puzzle, or jeu de taquin, is a game that is won by arranging the tiles in numerical order, so that the final arrangement appears as
Several algorithms exist for solving the puzzle, which has been studied by mathematicians for well over 100 years.
It's important to note that not every starting configuration of tiles will have a solution (though this applet only generates puzzles that can be solved). In fact, of the \(15! = 1,307,674,368,000\) possible starting arrangements with the empty space in the lower right corner, only half are solvable. We can consider the starting arrangement of the 15 tiles to be a permutation on the set \([15]\). If this permutation is even, and therefore an element of the alternating group, the puzzle will have a solution. Otherwise, the puzzle can only be solved by interchanging two tiles by ``lifting'' a tile off the board and placing it in a new location. This requirement was first discovered in 1879, but was not well known. The puzzle maker Sam Loyd offered a $1,000 reward to anyone that could solve his "14-15 puzzle" with starting arrangement
sparking a nationwide craze as people tried and failed to solve the unsolvable puzzle.
A three dimensional version of the game, called the Minus Cube, has similar solvability requirements.