The 15 puzzle

In his session about “What is mathematical proof?” on Monday 3 November Tim Gowers will mention the 15-puzzle.

This is a puzzle which was invented in the 1870s, became an international craze in the 1880s, and is widely available as a computer app today.

You have 15 tiles in a 16-square box, for example:

15-puzzle-loyd

The puzzle is to shift them around, using the empty square, so that you get them into the right order:

15-puzzle-solved

The maths of the 15-puzzle brings in some powerful and widely-used ideas, such as odd and even permutations.

Click here to download an article discussing the maths of the 15-puzzle.

Click here for a pdf which includes presentations of the 15-puzzle and the proofs of why all odd permutations of the tiles are insoluble puzzles, and all even permutations are soluble puzzles.