Lesson 1

We have seen that swapping \(14\) and \(15\) is impossible in the 15 Puzzle. The reason is that the resulting permutation is odd. For the same reason, any other configuration that corresponds to an odd permutation (and has the empty cell in the bottom-right corner) is unsolvable. For example, each of the following configurations is unsolvable.

In this section, we will prove that this is the only obstacle: if a configuration corresponds to an even permutation, then it is solvable. As a result, you will be able to implement a program that solves the 15 Puzzle instantly.