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.
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 parityof 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 distancebetween 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.
