Clicky

Mercyhurst UniversityDept of Math and ITDr Williams Home

Fifteen Puzzle



About the Fifteen Puzzle

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
1234
5678
9101112
131415
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
1234
5678
9101112
131514
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.

Using the Applet

Click on a tile next to the empty space to slide into the space. Continue sliding tiles until they are in the ending position. Every puzzle generated by this applet has a solution.

About this Applet

This applet was created using JavaScript and the Canvas library. If you are unable to see the applet, make sure you have JavaScript enabled in your browser. This applet may not be supported by older browsers.