The 14-15 puzzle

During your lifetime, you've probably seen the 15-puzzle. The game consists of a 4x4 grid containing 15 tiles and an empty slot. With the tiles shuffled, the objective is to slide them back into order without taking them off the board.

The problem

In the puzzle presented by Sam Loyd, all the pieces were initially in their correct positions, only with the 14th and 15th pieces reversed. A reward of $1000 was offered to the first person who could successfully solve it.

Despite several claims from different individuals, the prize remained unclaimed. It was eventually determined that the puzzle was impossible to solve.

Some considerations

Before explaining why the challenge is impossible, there are some concepts that need to be mentioned.

Permutation

Every permutation can be defined by a matrix of order as follows

Taking the movements from a 15-puzzle as an example we would have

There is another convenient notation knows as the cycle notation. Consider with

We would have

To write in the cycle notation, we typically begin with element 1. Let us observe that , meaning that 1 is mapped to element 2. Subsequently, 2 is mapped to 3, which is then mapped back to 1. Consequently, we have a cycle

Not all elements of have been mapped yet. The element 4 is mapped to itself, forming another closed cycle

Indeed, we have and , resulting in the cycle.

Hence, . Since we know that , the cycle (4) becomes redundant, and we can remove it, resulting in

Transposition

A transposition is a cycle of length 2, that is, it has the form (ab).

Every permutation can be expressed as the product of transpositions.

For example

Although a given permutation can be decomposed into transpositions in various ways, it will always have an even or odd number of transpositions.

Parity

The parity of a permutation can be defined based on the number of transpositions. If the number of transpositions is even, the parity is even; if the number of transpositions is odd, the parity is odd.

Since can be decomposed in 3 transpositions, the parity of the permutation is odd.

Sign

The sign of a permutation can be expressed as

where is the number of transpositions.

• If the parity of is even, then its sign is
• If the parity of is odd, then its sign is

Hence, .

Back to the challenge

We first need to look at how the 15-puzzle works. As previously mentioned, the game consists of sliding the pieces in order to return them to the correct position. In a way, we would always be permutating a piece and the empty space.

Let's consider that all pieces are in their correct positions, and obviously, the empty space occupies the 16th position. Since every move involves swapping the empty space with a piece, we will pay close attention to this space.

Suppose we start shuffling the game and want to return the empty space to the 16th position again. It is intuitively clear that it must have moved an even number of times. In other words, we will always have an even number of transpositions.

In the challenge proposed by Loyd, the board initially has all the tiles in their respective positions, except for tiles 14 and 15, which are swapped. We can say that there is a permutation such that . Its parity is odd.

As mentioned earlier, it is not possible to have both an even and odd configuration simultaneously. Therefore, solving Loyd's challenge is impossible.