Solution to: Fourteen Fifteen
It is impossible to solve this puzzle. All possible configurations of the 15 tiles and the empty space can be divided into two groups. Each configuration in one of these groups is reachable through moves from any other configuration in the same group, but not from the other group. The desired end configuration (all tiles in the correct order with the empty space back in the bottom right corner) and the given start configuration are not in the same group. However, it is possible to arrange all tiles in the correct order with the empty space in the top left corner (see the second question of the puzzle)!
A proof for this can be provided based on the so-called parity of each configuration: a configuration is even or odd. This parity is preserved in all allowed moves.
First, we will explain how the parity of a configuration is determined. Then we will prove that the parity remains unchanged in all allowed moves.
The parity of a configuration is determined by the sum of N1 and N2. Here, N2 is the number of the row in which the empty space is located (numbered from 1 to 4). N1 is the number of pairs of numbers that are in the wrong order. N1 is determined as follows:
- List all the numbers of the tiles in a row (from left to right and from top to bottom).
- Consider all 105 possible pairs of numbers in this row (all possible combinations of two numbers).
- N1 is the number of pairs of numbers that are in the wrong order.
An example. Suppose the current configuration of the tiles is as follows:
| 1 | 2 | 3 | 4 |
| 5 | 6 | 9 | 7 |
| 11 | 8 | 12 | 10 |
| 13 | 14 | 15 |
Now we list the numbers in a row: 1, 2, 3, 4, 5, 6, 9, 7, 11, 8, 12, 10, 13, 14, 15.
To determine which pairs of numbers are in the wrong order, we look for each number in the row to see which numbers to the right of it are smaller. We find that for 5 out of the 105 pairs of numbers, the numbers are in the wrong order: (9, 7), (9, 8), (11, 8), (11, 10), and (12, 10). So, N1 = 5.
The empty space in this example is located in row 4, so N2 = 4.
The parity of the configuration in this example is therefore odd, because N1 + N2 = 5 + 4 = 9.
Now we will prove that the parity does not change when making an allowed move. There are two types of moves possible: a tile can be moved horizontally or vertically.
In a horizontal move (see the example in the image below), both N1 and N2 remain the same. The order of the tiles does not change, and the empty space also remains in the same row. Thus, a horizontal move has no effect on the parity.
| X | → | ||
In a vertical move (see the example in the image below), the empty space moves one row up or down. As a result, N2 increases or decreases by 1. N1 will increase or decrease by 1 or 3. When the numbers are in a row, there are always exactly three numbers enclosed between the old and new position of the moved tile. Changes can only occur in the pairs of numbers that include both the moved tile (X) and one of the enclosed numbers (a, b, and c). All other pairs of numbers remain unchanged. In the example below, where tile X is moved one row down, the value of N2 increases by 1. The value of N1 increases or decreases by 1 for each of the three pairs of numbers (X, a), (X, b), and (X, c) (see the table below).
| X | a | ||
| b | c | ↓ | |
| Situation before move | Contribution to N1 before move | Contribution to N1 after move | Change in N1 | ||
|---|---|---|---|---|---|
| X > a | X > b | X > c | |||
| no | no | no | 0 | 3 | +3 |
| yes | no | no | 1 | 2 | +1 |
| no | yes | no | 1 | 2 | +1 |
| yes | yes | no | 2 | 1 | -1 |
| no | no | yes | 1 | 2 | +1 |
| yes | no | yes | 2 | 1 | -1 |
| no | yes | yes | 2 | 1 | -1 |
| yes | yes | yes | 3 | 0 | -3 |
Because both N1 and N2 change by an odd value, the value of N1 + N2 changes by an even value. As a result, the parity of N1 + N2 remains the same even with a vertical move.
The parity of the given initial configuration (with the numbers 14 and 15 swapped and the empty space in the bottom right corner) is odd (since N1 + N2 = 4 + 1 = 5). The parity of the desired end configuration (all numbers in the correct order with the empty space in the bottom right corner) is even (since N1 + N2 = 4 + 0 = 4). Therefore, it is impossible to reach the desired end configuration from the given initial configuration.
However, the parity of the configuration in which all numbers are in the correct order and the empty space is in the top left corner is indeed odd (since N1 + N2 = 1 + 0 = 1). This configuration can therefore be reached from the given initial configuration.
Back to the puzzle