Fifteen Puzzle
Main Concept
The fifteen puzzle is a simple game first invented around 1874. The game contains 15 blocks in a 4×4 grid, with each block labeled with an integer from 1 to 15. The goal of this puzzle is to arrange the block sequentially from 1 to 15 with the empty block (which would be numbered 16 if it were there) in the bottom right. In modern times the numbers have been replaced by images, which, when the game has been solved, form a complete picture. To start, the blocks are placed randomly in the grid. It should be noted, however, that certain initial conditions are unsolvable.
When is it solvable?
There are two properties of the initial configuration that determine whether the puzzle is solvable.
To start, imagine first replacing the empty space by a 16th block and converting the resulting block configuration to a row of numbers, by reading the blocks first from left to right and then top to bottom.
61584111523121691310147 →6, 1, 5, 8, 4, 11,15, 2, 3, 12, 16, 9, 13, 10, 14, 7
This row can be considered a permutation of the ordered sequence [1, 2, 3, ..., 16]. Now, any such permutation can be decomposed into a set of swaps of consecutive elements, and while there are many ways of doing this, the number of such swaps that make up this set is always even or odd for a given permutation. This property is known as the parity of the permutation.
The second property is the location of the empty block (labeled "16" earlier) with respect to its natural location on the bottom right corner of the grid. This is calculated using the taxicab distance between the two points, which is defined as the sum of the differences between horizontal and vertical coordinates on a Cartesian grid.
The fifteen puzzle's solvability can now be expressed as follows:
For an initial configuration, the fifteen puzzle is solvable when the parity of the permutation for all the blocks and the parity of the taxicab distance between the empty block and the bottom right corner of the grid are both even, or are both odd. The puzzle cannot be solved if one is even and the other is odd.
Slide the blocks one at a time and try to get them all back to their original position. You can also choose a block to slide by clicking on it. When finished, press "Reshuffle" to start again, or load a new image. Try making it harder by removing the numbers with the check box, or press "Clear Image" to just use the numbers.
More MathApps
MathApps/LogicAndPuzzles
Download Help Document
