Language English Русский Navigation Home About STP Corner Links STP Corner STP Corner Glossary Mathematics Move metrics Goal configurations God's Algorithm Human Solutions Computer Solutions Walking Distance Results

## Mathematics

02 / 12 / 2012

15-14 unsolvable problem
12 34 12 34
56 78 56 78
910 1112 910 1112
1315 14 1314 15
Starting configuration Goal configuration

### 15-14 unsolvable problem

The 15 puzzle was a big craze in the early part of 1880. There were even prizes offered for solving the puzzle starting from the configuration with just tiles 14 and 15 swapped. However, this is impossible.

Moreover, it is impossible to swap just two physical tiles in any given configuration of any integer puzzle with 1 × 1 tiles with one slot.

Proof is based on the parity of permutation of the tiles. There are many explanations on the web.

### Sketch of the proof

Let S be set of k integer numbers 1, 2, ..., k, where k is the number of locations of our puzzle. For the 15 puzzle, k = 16.

Every configuration of the puzzle can be considered as a permutation of S applied to the goal configuration. All such permutations form a group under composition. This group is Sk (symmetric group of degree k).

Every valid single tile move is transposition of some physical tile and slot. Transposition is an odd permutation, thus each move changes parity of the permutation.

For any two locations l1 and l2, we can find Manhattan distance between them. This distance shows how many moves are needed to bring slot in l2 if it is currently in l1.

Each valid move will change parity of distance between slot and its home location. This can be shown using black-white checkered coloring of the puzzle board.

Both parities change after each move. Swapping two physical tiles changes parity of the permutation but leaves unchanged parity of the distance between slot and its home location and therefore impossible.

Note: Manhattan distance between two points, or taxicab geometry, is defined as the sum of the absolute differences of their coordinates. However, sliding tile puzzle may have obstacles, so the number of moves needed to bring slot from the location l1 to the location l2 can be more than the Manhattan distance between l1 and l2.

### Puzzle on an arbitrary graph

In the puzzle based on an arbitrary graph G with just one slot vertex, there are the following essentially different cases.

1. G is not connected. In other words, some tiles cannot reach some locations.
In this case, we can immediately discard any component of G if there are no slot locations in this component because we cannot move any tile in this component.
2. G is separable. A graph is called separable if removing a vertex increases the number of components.
3. G is a regular hexagon with one diagonal and a vertex at the center added.
In this case, only 1/6 of all configurations can be reached.
4. G is connected, non-separable bipartite graph. Equivalently, there are no odd-length cycles in G.
There is parity restriction in this case, namely that only even permutations are obtainable. Thus the state space is 1/2 of all configurations.
5. G is connected, non-separable graph with at least one odd-length cycle.
All configurations are reachable.

### Indistinguishable tiles

 "Rate Your Mind Pal" R A T E Y O U R M I N D P L A

In some puzzles, there are identical pieces. By swapping two identical tiles it is possible to change parity of permutation.

There is variation of the Fifteen Puzzle with letters on tiles. This variation is shown on the right. The objective is to swap tiles L and A to make phrase "Rate your mind pal".

Two tiles cannot be swapped as single swap is an odd permutation. However, there are two gray "R" tiles. Two swaps are even permutation and therefore possible.

In general case, when there are N objects M of which are identical, the number of possible arrangements of these objects is N! / M! 