Игра Пятнашки: существование решения

Напомним, что игра представляет собой поле $4$ на $4$ , на котором расположены $15$ фишек, пронумерованных числами от $1$ до $15$ , а одно поле оставлено пустым. Требуется, передвигая на каждом шаге какую-либо фишку на свободную позицию, прийти в конце концов к следующей позиции:

$\matrix{ 1&2&3&4\cr 5&6&7&8\cr 9&10&11&12\cr [...]$

Игру Пятнашки ("15 puzzle") изобрёл в 1880 г. Нойес Чэпман (Noyes Chapman).

Существование решения

Здесь мы рассмотрим такую задачу: по данной позиции на доске сказать, существует ли последовательность ходов, приводящая к решению, или нет.

Пусть дана некоторая позиция на доске:

$\matrix{ a_1 & a_2 & a_3 & a_4 \cr a_5 & a_6 &[...]$

где один из элементов равен нулю и обозначает пустую клетку $a_z = 0$ .

Рассмотрим перестановку:

$a_1 a_2 \ldots a_{z-1} a_{z+1} \ldots a_{15} a_{1[...]$

(т.е. перестановка чисел, соответствующая позиции на доске, без нулевого элемента)

Обозначим через $N$ количество инверсий в этой перестановке (т.е. количество таких элементов $a_i$ и $a_j$ , что $i < j$ , но $a_i > a_j$ ).

Далее, пусть $K$ — номер строки, в которой находится пустой элемент (т.е. в наших обозначениях $K = (z-1)\ {\rm div}\ 4 + 1)$ .

Тогда, решение существует тогда и только тогда, когда $N+K$ чётно.

Реализация

Проиллюстрируем указанный выше алгоритм с помощью программного кода:

int a[16];
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");

Доказательство

Джонсон (Johnson) в 1879 г. доказал, что если $N+K$ нечётно, то решения не существует, а Стори (Story) в том же году доказал, что все позиции, для которых $N+K$ чётно, имеют решение.

Однако оба эти доказательства были достаточно сложны.

В 1999 г. Арчер (Archer) предложил значительно более простое доказательство (скачать его статью можно здесь).