The fifteen puzzle with two tiles swapped

Question

The fifteen puzzle is a 4 by 4 frame holding fifteen numbered sliding tiles and one empty space. A move slides a tile adjacent to the empty space into it.

The puzzle is set up in the solved position (1 to 15 in reading order, empty space at bottom right) except that tiles 14 and 15 have been swapped. In 1880 a prize of 1,000 dollars was offered for solving it.

Can it be solved? Prove your answer.

Accepted Answer

No. The swapped position can never be reached from the solved one, and the prize was never claimed. An invariant. Read the 16 cells in reading order (left to right, top to bottom), writing 16 for the empty space. Count the inversions: pairs of numbers where the larger comes before the smaller. Also note the row of the empty space, counting from the top. Now see what a move does. Sliding a tile horizontally does not change the reading order of the tiles at all, so the inversion count and the empty space's row are both unchanged. Sliding a tile vertically moves it past exactly three other tiles…

The fifteen puzzle with two tiles swapped

Your answer

Discussion

Learn the concepts

Related questions