Project 15 Puzzle · The Puzzle

Lesson 2

Nikolai Chukhin · Alexander S. Kulikov

Take a $4\times 4$ square frame and place $15$ square tiles labeled $1,2,\dotsc,15$ inside it.

Each tile has size $1\times 1$, so the tiles occupy $15$ out of the $16$ cells, leaving one cell empty. A move consists of sliding a tile adjacent to the empty cell into it, thereby vacating its previous position. The objective is to rearrange the tiles into a desired configuration.

For example, one may attempt to transform the configuration on the left into the one on the right by a sequence of such moves.

Equivalently, one may consider the reverse task: starting from the configuration in which $14$ and $15$ are swapped (right), restore the initial configuration (left). This formulation is entirely equivalent—one simply reverses the sequence of moves, as in a video played backwards—and is often more convenient in practice, since there is no need to memorize the target configuration. Try it!

Historically, the 15 Puzzle enjoyed enormous popularity in the United States in the late 19th century, sparking a widespread craze. At the height of this phenomenon, substantial prizes were offered for its solution, including a notable reward of $\$$1 000 for anyone who could solve certain challenging configurations like the one above.