MAXimal

добавлено: 11 Jun 2008 11:27
редактировано: 27 Dec 2008 16:39

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

Напомним, что игра представляет собой поле 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) предложил значительно более простое доказательство (скачать его статью можно здесь).