Project 15 Puzzle · Solving Any Configuration

Lesson 2

Nikolai Chukhin · Alexander S. Kulikov

Our high-level plan is as follows. We begin by showing that every even permutation can be decomposed into 3-cycles.

It then remains to show that every 3-cycle \((a, b, c)\), which cyclically permutes the elements \(a\), \(b\), and \(c\), can be realized on the puzzle board. To do this, we first move the elements \(a\), \(b\), and \(c\) to the top-left corner. Intuitively, this is possible because one can perform a cyclic shift around the entire board.

Once the three required elements are in the corner, we perform the 3-cycle using the following four puzzle moves.

Below, we examine each of these steps in full detail.