15 Puzzle Game: Existence Of The Solution
This game is played on a \(4 \times 4\) board. On this board there are \(15\) playing tiles numbered from 1 to 15. One cell is left empty (denoted by 0). You need to get the board to the position presented below by repeatedly moving one of the tiles to the free space:
The game "15 Puzzle” was created by Noyes Chapman in 1880.
Existence Of The Solution
Let's consider this problem: given a position on the board, determine whether a sequence of moves which leads to a solution exists.
Suppose we have some position on the board:
where one of the elements equals zero and indicates an empty cell \(a_z = 0\)
Let’s consider the permutation:
i.e. the permutation of numbers corresponding to the position on the board without a zero element
Let \(N\) be the number of inversions in this permutation (i.e. the number of such elements \(a_i\) and \(a_j\) that \(i < j\), but \(a_i > a_j\)).
Suppose \(K\) is an index of a row where the empty element is located (i.e. using our convention, \(K = (z - 1) \div \ 4 + 1\)).
Then, the solution exists iff \(N + K\) is even.
The algorithm above can be illustrated with the following program code:
int a; for (int i=0; i<16; ++i) cin >> a[i]; int inv = 0; for (int i=0; i<16; ++i) if (a[i]) for (int j=0; j<i; ++j) if (a[j] > a[i]) ++inv; for (int i=0; i<16; ++i) if (a[i] == 0) inv += 1 + i / 4; puts ((inv & 1) ? "No Solution" : "Solution Exists");
In 1879 Johnson proved that if \(N + K\) is odd, then the solution doesn’t exist, and in the same year Story proved that all positions when \(N + K\) is even have a solution.
However, all these proofs were quite complex.
In 1999 Archer proposed a much simpler proof (you can download his article here).