The Impossible Fifteen Puzzle, math that surprises you lesson

The 15 puzzle has fifteen numbered tiles and one empty square on a 4 by 4 board, and a move slides a tile into the empty square next to it. Suppose the tiles are in order except that 14 and 15 have changed places. It looks like a small repair, yet no sequence of slides, however long, puts them back. This page finds a quantity that no slide can change and uses it to tell the two positions apart without making a single move.

Key terms

15 puzzle

Definition The 15 puzzle is the sliding puzzle on a 4 by 4 board with fifteen tiles numbered $1$ to $15$ and one empty square, called the blank. A legal move slides a tile that shares a side with the blank into the blank. In the goal position the tiles read $1$ to $15$ from left to right along the rows, top row first, and the blank is in the bottom right corner. The impossible fifteen puzzle starts from the goal position with tiles $14$ and $15$ exchanged and asks whether legal moves can reach the goal. They cannot. Read the tiles row by row in the same order, skipping the blank, let $I$ be the number of inversions in this list, and let $r$ be the row of the blank counted from the bottom, so that the bottom row is row $1$ . A horizontal move changes neither the list nor $r$ . A vertical move changes $r$ by $1$ and moves one tile past exactly three others in the list, which changes $I$ by $1$ or $3$ , up or down, so $I + r$ changes by an even number. Whether $I + r$ is even or odd therefore never changes, and the two positions give

\begin{aligned} \text{goal}&\quad 0 + 1 = 1, \\[0.4em] \text{start}&\quad 1 + 1 = 2. \end{aligned}

One is odd and the other even, so the goal cannot be reached from the start.

In plain words Every position carries a hidden label, even or odd, and sliding tiles never changes it. The goal is labeled odd and the swapped position is labeled even, so no amount of sliding connects them.

Example From the goal, slide tile $15$ to the right into the blank. The list is still $1$ to $15$ and the blank is still in row $1$ , so $I + r = 0 + 1 = 1$ . From the goal, slide tile $12$ down instead. In reading order the square of a tile and the square directly below it are four places apart, with three squares between them, and here those squares hold $13$ , $14$ and $15$ . So $12$ moves from before these three tiles to after them, and the list ends 11, 13, 14, 15, 12. It has the three inversions formed by $12$ with $13$ , $14$ and $15$ , the blank has moved to row $2$ , and $I + r = 3 + 2 = 5$ , which is odd again.

Sliding puzzle

Definition A sliding puzzle on a board with $m$ rows and $n$ columns, where $m \ge 2$ and $n \ge 2$ , has $mn - 1$ tiles numbered $1$ to $mn - 1$ and one blank square. A legal move slides a tile that shares a side with the blank into the blank, so the tile and the blank trade places. A position records where every tile and the blank are, so there are $(mn)!$ positions, where $k!$ is the product $1 \cdot 2 \cdots k$ . The goal position has the tiles in increasing order, read along the rows from the top, with the blank in the bottom right corner. Every move can be undone by sliding the same tile back, so if a position $B$ can be reached from a position $A$ , then $A$ can be reached from $B$ .

In plain words Tiles move one at a time into the single empty space, and any move can be reversed by sliding the tile back.

Example On a 2 by 2 board with tiles $1$ , $2$ and $3$ there are $4! = 24$ positions. The blank can only travel around the ring of four squares, and each move shifts one tile one step along the ring, so the order of the tiles read clockwise around the ring never changes. In the goal, with $1$ and $2$ in the top row and $3$ at the bottom left, the tiles read $1$ , $2$ , $3$ clockwise, and so they do in every position reached from it. There are exactly $4 \cdot 3 = 12$ such positions, since the blank can be in any of the four squares and tile $1$ in any of the other three, and all of them can be reached. Exchanging tiles $2$ and $3$ in the goal gives one of the other $12$ positions, which can never be solved.

Inversion

Definition In a list $a_1, a_2, \ldots, a_k$ of different numbers, an inversion is a pair of positions $i < j$ with $a_i > a_j$ , that is, a larger number that comes before a smaller one. A list in increasing order has no inversions. A list in decreasing order has every pair inverted, so it has the largest possible number,

\frac{k(k - 1)}{2}.

In plain words Count the pairs of numbers that are in the wrong order relative to each other, wherever they stand in the list.

Example The list 1, 3, 2 has one inversion, formed by $3$ and $2$ . The list 3, 1, 2 has two, since $3$ comes before both $1$ and $2$ , while $1$ and $2$ are in the right order. The list 4, 3, 2, 1 has all $4 \cdot 3/2 = 6$ of its pairs inverted. In the 15 puzzle with $14$ and $15$ exchanged, the list read row by row is $1$ to $13$ followed by $15$ and $14$ , so its only inversion is formed by $15$ and $14$ , and $I = 1$ .

Permutation parity

Definition A permutation of the numbers $1$ to $k$ is a list that contains each of them exactly once. Its parity is even when its number of inversions is even, and odd when that number is odd. Exchanging any two entries of a permutation changes its parity. Exchanging two neighboring entries changes the order of exactly one pair, so it changes the number of inversions by $1$ . Exchanging the entries in positions $i < j$ can be done by $2(j - i) - 1$ exchanges of neighbors, an odd number, so it changes the parity too. As a result, every way of sorting a permutation by exchanges uses an even number of exchanges if the permutation is even, and an odd number if it is odd.

In plain words A single swap of two entries always flips a permutation between even and odd. A list that is one swap away from sorted can never be sorted with an even number of swaps.

Example The permutation 3, 1, 2 is even, with two inversions, and it is sorted by two exchanges, first of $3$ and $1$ , which gives 1, 3, 2, and then of $3$ and $2$ . The list of tiles in the swapped 15 puzzle is odd, one exchange away from $1$ to $15$ . In the puzzle, a position with the blank back in the bottom right corner has $r = 1$ , so it can be reached from the goal only if $I$ is even. Every position reached from the goal with the blank in that corner therefore has its tiles in an even permutation, and the swapped position, whose permutation is odd, is not one of them.

Unsolvable position

Definition A position of a sliding puzzle is unsolvable if no sequence of legal moves leads from it to the goal position. On the 4 by 4 board, with $I$ and $r$ as above, every position with $I + r$ even is unsolvable, because $I + r$ is odd at the goal and its parity never changes. It is also a known theorem, with a longer proof, that every position with $I + r$ odd can be solved, so exactly half of the $16!$ positions are solvable. On a board with an odd number of columns, a vertical move passes an even number of tiles and changes $I$ by an even number, so there the parity of $I$ alone is the invariant, and a position is unsolvable when $I$ is odd.

In plain words A position is unsolvable when it carries the wrong label. On the 4 by 4 board the label is whether the number of inversions plus the row of the blank is even or odd.

Example Reverse the tiles, so that they read $15$ , $14$ and so on down to $1$ row by row, with the blank in the bottom right corner. Every pair is inverted, so

I = \frac{15 \cdot 14}{2} = 105,

and with $r = 1$ the sum $I + r = 106$ is even, so this position is unsolvable. Exchanging any two of its tiles leaves $r$ as it is and changes the parity of $I$ , so the new position has $I + r$ odd and, by the theorem, can be solved. The board has $16! = 20{,}922{,}789{,}888{,}000$ positions, and $10{,}461{,}394{,}944{,}000$ of them are solvable.

Check yourself

Start from the goal and slide tile $12$ down, then tile $11$ to the right, then tile $7$ down. Find $I$ and $r$ after each move and check that $I + r$ stays odd.

Show the answer

After tile $12$ moves down, the list ends 11, 13, 14, 15, 12, so $I = 3$ , and the blank is in the third row from the top, which is row $2$ from the bottom. The sum is $3 + 2 = 5$ . Sliding $11$ to the right is a horizontal move, so the list and the row stay the same, and the sum is still $5$ .

Tile $7$ then moves from the second row into the blank below it, and in reading order it passes $8$ , $9$ and $10$ . The list becomes

\begin{aligned} &1, 2, 3, 4, 5, 6, 8, 9, \\[0.4em] &10, 7, 11, 13, 14, 15, 12, \end{aligned}

with three inversions formed by $7$ and three formed by $12$ , so $I = 6$ . The blank is now in the second row from the top, which is row $3$ from the bottom, and the sum is $6 + 3 = 9$ . All three sums are odd, as the invariant requires.

Put the blank in the top left corner and the tiles $1$ to $15$ in order after it, reading row by row. The list of tiles has no inversions, just like the goal. Can this position be solved?

Show the answer

No. The list is $1$ to $15$ in order, so $I = 0$ , but the blank is in the top row, which is row $4$ from the bottom. Then $I + r = 0 + 4 = 4$ is even, while the goal has $I + r = 1$ , which is odd, so no sequence of legal moves reaches the goal. Counting inversions alone would wrongly suggest that this position is as good as solved. On a board with four columns the row of the blank is part of the invariant and cannot be left out.

Change the board. On a 3 by 3 board with tiles $1$ to $8$ and the goal in the same reading order, slide tile $6$ down from the goal and compute $I + r$ . Then find the invariant for this board and decide whether the goal position with $7$ and $8$ exchanged can be solved.

Show the answer

After the slide the rows read 1, 2, 3 and 4, 5 with the blank at the right, and then 7, 8, 6. The list is 1, 2, 3, 4, 5, 7, 8, 6, with two inversions formed by $6$ with $7$ and $8$ , so $I = 2$ . The blank is in row $2$ from the bottom, so $I + r = 4$ is even, although the position is one move from the goal. The rule for the 4 by 4 board does not hold here.

On a board with three columns, a tile moving vertically passes only the two tiles between its old and new squares in reading order. Each of those two pairs changes between inverted and not inverted, so $I$ changes by $-2$ , $0$ or $2$ , and a horizontal move does not change $I$ at all. The parity of $I$ alone is therefore the invariant. The goal has $I = 0$ , which is even, and the position with $7$ and $8$ exchanged has $I = 1$ , which is odd, so it cannot be solved.