Project 15 Puzzle · Solving the Original Configuration

Lesson 11

Nikolai Chukhin · Alexander S. Kulikov

Finally, we are ready to prove that the following exchange is impossible in the 15 Puzzle.

To do this, let us replace the empty cell by a special dummy piece \(0\).

After this, the pieces cannot move. If in the original game we move, say, \(12\) down, in this new representation, we exchange \(12\) and \(0\). Every move in the original game is now a transposition in the new game (exchanging the moving piece with the \(0\)-piece).

If the original 15 Puzzle (where the goal is to exchange \(14\) and \(15\)) were solvable, the solution would require an odd number of moves, since the resulting permutation is an odd one. On the other hand, a solution gets the empty cell (or the 0-piece) back to its original position. But this means that the number of moves should be even! Indeed, the empty cell cannot return to its original position after an odd number of moves. Thus, the original configuration is unsolvable.