The Fifteen Puzzle

  • Hard
  • Arrangement puzzles
  • Tests: Finding a quantity that no legal move can change

The puzzle

Fifteen numbered tiles sit in a four by four tray with one empty space. A tile adjacent to the space may slide into it.

Starting from the solved position, is it possible to reach the position where everything is solved except that 14 and 15 are swapped?

Stuck?

One at a time, smallest first. Open only as many as you need — the whole point of the puzzle is the part you work out yourself.

Hint 1

Look for something that every legal move leaves unchanged. If the two positions differ in it, no sequence of moves connects them.

Hint 2

Consider the parity of the tile permutation together with the parity of the blank square's position.

Show the answer Hide the answer

No. Exactly half of the arrangements are reachable, and the 14-15 swap is in the other half.

How to get there

Define two things: the parity of the permutation of the tiles (even or odd), and the parity of the blank's taxicab distance from its home corner. A single slide swaps one tile with the blank, which flips the permutation parity - and it also moves the blank one square, flipping the other parity too.

So the sum of the two parities never changes. It is an invariant of the puzzle, fixed by the starting position and untouchable by any sequence of moves.

In the solved position the permutation is even and the blank is home, so the sum is even. Swapping 14 and 15 is a single transposition, making the permutation odd, while the blank is still home - so the sum is odd. The two positions sit in different halves of the 16!/2 arrangements and no amount of sliding will join them. Loyd is said to have offered a prize for this and kept his money.

The technique worth keeping

To prove something impossible, find an invariant: a quantity every legal move preserves. Parity is the workhorse - it splits the state space in two, and no sequence of moves ever crosses between the halves.