Математика и алгоритмы в простой головоломке "Пятнашки". Часть 1

На сайте, наверное, с десяток реализаций головоломки Пятнашки. Реализовать просто, процесс залипательный, особенно если сделать тактильно, чтобы можно было мышкой перемещать костяшки на пустое место, и не по одной, а по две или три сразу, как в материальных пятнашках. Но у меня возник вдруг другой вопрос. А как собрать ее оптимально, за минимальное количество ходов из любого начального состояния. Есть у меня такое хобби, изучать разные занимательные механики и алгоритмы. Что ж, я поизучал вопрос и решил поделиться изысканиями. В общем, это не так просто.

📌 Лонгрид-предупреждение: Материал получился длинный, поэтому тут только преамбула и, в основном, теория.

1. Любое ли начальное состояние решаемо?

Всего существует 16! (20 922 789 888 000) способов расставить 16 элементов по клеткам. И только половина из них решаема.

Каждый, кто рассыпал в детстве костяшки пятнашек и собирал хаотично заново, знает, что нет, не каждое. В некоторых случаях последние две костяшки никак не собираются правильно, как ни крути, всегда идет 15, затем 14.

И так вопрос. Как из начального состояния определить, решается ли оно. Для начала соберем всю доску пятнашек в плоский одномерный массив. Второй ряд, поставим после первого, третий после второго и т.д.

Вот так будет выглядеть окончательно собранная головоломка, 0 - это пустая клетка:

[1,3,4,5,6,7,8,9,10,11,12,13,14,15,0]

Вот так - некий случайный расклад:

[15,2,11,7,4,3,5,1,10,14,0,6,12,9,13,8]

Решаемость проверяется через понятие инверсии. Инверсия - это пара элементов с нарушенным порядком, если порядок основной по возрастанию. В первом случае, в собранной головоломке - инверсий нет, если поле 0 мы не учитываем.

Если мы двигаем костяшку влево-вправо, это равносильно тому что мы двигаем 0 в массиве вправо-влево. При этом количество инверсий не меняется (0, напомню, мы не учитываем). А если мы двигаем костяшку вверх-вниз, то это равнозначно тому, что мы меняем местами 0 и элемент с индексом ±4. Это меняет количество инверсий на ±3. То есть - четность количества инверсий меняется. Но при этом меняется строка пустой клетки на ±1. То есть - четность строки пустой ячейки меняется. То есть - сумма количества инверсий и номера строки пустой ячейки не меняется.

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

Для правильного расположения количество инверсий ноль, номер строки пустой ячейки - четный. То есть сумма тоже четная. 

Соответственно, если в произвольном раскладе сумма количества инверсий и номера строки пустой ячейки - четное число - то расклад решаемый, иначе - нет.

Количество раскладов - это количество перестановок чисел от 0 до 15, то есть 16!. Ровно половина из них решаема.

Вот функция проверки:

Функция РешениеСуществует(Поле)
	
	Инверсии = 0;
	Плоский = Новый Массив(Поле);
	
	НулевойИндекс = Поле.Найти(0);
	
	Плоский.Удалить(НулевойИндекс);
	
	Для i = 0 По Плоский.Количество() - 1 Цикл
		Для j = i + 1 По Плоский.Количество() - 1 Цикл
			Если Плоский[i] > Плоский[j] Тогда
				Инверсии = Инверсии + 1;
			КонецЕсли;
		КонецЦикла;
	КонецЦикла;
	
	НомерСтрокиПустойЯчейки = 1 + Цел(НулевойИндекс / 4);
	Инверсии = Инверсии + НомерСтрокиПустойЯчейки;
	
	Возврат Инверсии % 2 = 0;
	
КонецФункции

Но это все преамбула. Самое интересное - это путь решения.

Наверное, каждый понимал, что хотя головоломку очень просто интуитивно собрать, тем не менее, мы действуем не оптимально. Перегоняем клетки по одной, при этом не смотрим на другие и в конце, бывает, мучаемся с перестановкой последних цифр. 

2. Как же математически оптимально собрать пятнашку?

На гифке видно, как алгоритм "понимает", что перед тем как собирать 1-2-3 нужно 13-14-15 выстроить в правильном порядке и не нарушить его, сдвигая другие. Хотя на самом деле, ничего он не понимает, просто выстроил оптимальный маршрут и двигается по нему.

Как же построить этот маршрут?

На помощь приходит, как обычно в таких задачах, теория графов. Построим мысленно граф, в котором каждая вершина - это вариант размещения костяшек в коробке. А дуги соединяют смежные вершины, которые отличаются перестановкой одной клетки. Находим в графе наше начальное состояние, потом поиском в глубину или в ширину находим все пути к решению и выбираем минимальный. Все просто!

Ну да, только при поиске в ширину мы быстро исчерпаем всю мыслимую память, а в глубину - не дождемся окончания поиска. Но это только если мы будем двигаться вслепую, по всем дугам.

3. Эвристика

Чтобы не блуждать в темноте, введем оценочную функцию состояния, эвристику. Грубо прикинем, сколько примерно минимально ходов нужно. Например, костяшка "1" у нас на второй строке в третьем столбце. Чтобы переместить ее в начальную клетку нужно переместить на одну строку вверх и 2 клетки влево. На самом деле, конечно, больше. Но точно не меньше. То есть, рассчитаем манхэттенское расстояние (сумму пути по горизонтали и по вертикали) для каждой костяшки до ее места в поле. Пустую клетку не считаем, она и так встанет куда надо. Если мы сложим все такие манхэттенские расстояния - то получим грубую нижнюю оценку нашей позиции. То есть скорее всего нам потребуется больше ходов, но точно не меньше.

Чтобы немного уточнить оценку, введем еще учет линейных конфликтов. Если две костяшки стоят в одном столбце или строке, причем в своем столбце-строке, в том где они и должны быть. Но при этом их порядок перепутан. То манхэттенское расстояние даст черезчур оптимистично малую оценку. Нам же придется убирать одну фишку в сторону, а потом возвращать обратно. Для всех таких обнаруженных пар, добавим к оценке еще два балла.

Функция ОценкаСостояния(ПолеИгры)

    МанхэттенскоеРасстояние = 0;
    
    Для НомерСтроки = 0 По 3 Цикл
        Для НомерСтолбца = 0 По 3 Цикл
            ЗначЯчейки = ПолеИгры[НомерСтроки * 4 + НомерСтолбца];
            Если ЗначЯчейки = 0 Тогда
                Продолжить;
            КонецЕсли;

			МанхэттенскоеРасстояние = МанхэттенскоеРасстояние 
                + АБС((ЗначЯчейки - 1) % 4 - НомерСтолбца) 
                + АБС(Цел((ЗначЯчейки - 1) / 4) - НомерСтроки);
        КонецЦикла;
    КонецЦикла;
    
    ЛинейныйКонфликт = 0;
    
    // Проверка конфликтов в строках
    Для НомерСтроки = 0 По 3 Цикл
        Для НомерСтолбца = 0 По 3 Цикл
            ЗначЯчейки = ПолеИгры[НомерСтроки * 4 + НомерСтолбца];
            
            Если ЗначЯчейки = 0 ИЛИ Цел((ЗначЯчейки - 1) / 4) <> НомерСтроки Тогда
                Продолжить;
            КонецЕсли;
            
            Для НомерСтолбца2 = НомерСтолбца + 1 По 3 Цикл
                ЗначЯчейки2 = ПолеИгры[НомерСтроки * 4 + НомерСтолбца2];
                
                Если ЗначЯчейки2 = 0 ИЛИ Цел((ЗначЯчейки2 - 1) / 4) <> НомерСтроки Тогда
                    Продолжить;
                КонецЕсли;

                Если ЗначЯчейки > ЗначЯчейки2 Тогда
                    ЛинейныйКонфликт = ЛинейныйКонфликт + 2;
                КонецЕсли;
            КонецЦикла;
        КонецЦикла;
    КонецЦикла;
    
    // Проверка конфликтов в столбцах
    Для НомерСтолбца = 0 По 3 Цикл
        Для НомерСтроки = 0 По 3 Цикл
            ЗначЯчейки = ПолеИгры[НомерСтроки * 4 + НомерСтолбца];
            
            Если ЗначЯчейки = 0 ИЛИ (ЗначЯчейки - 1) % 4 <> НомерСтолбца Тогда
                Продолжить;
            КонецЕсли;
            
            Для НомерСтроки2 = НомерСтроки + 1 По 3 Цикл
                ЗначЯчейки2 = ПолеИгры[НомерСтроки2 * 4 + НомерСтолбца];
                
                Если ЗначЯчейки2 = 0 ИЛИ (ЗначЯчейки2 - 1) % 4 <> НомерСтолбца Тогда
                    Продолжить;
                КонецЕсли;
                
                Если ЗначЯчейки > ЗначЯчейки2 Тогда
                    ЛинейныйКонфликт = ЛинейныйКонфликт + 2;
                КонецЕсли;
            КонецЦикла;
        КонецЦикла;
    КонецЦикла;
    
    Возврат МанхэттенскоеРасстояние + ЛинейныйКонфликт;
    
КонецФункции

4. Метод информированного поиска

4.1. Алгоритм А*

Чем плоха эвристика? Тем что она очень оптимистична, особенно на начальных этапах. Она не убывает монотонно при приближении к цели и не возрастает при отдалении от нее. Если бы это было так, то была бы не эвристика, это было бы решение задачи. Просто иди в сторону меньшей оценки и быстро придешь к цели. 

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

Для решения задачи придумали первый алгоритм информированного поиска в графе. Он называется A* (A-star, A со звездой). Звезду ему дали за то, что он математически лучший. 

Авторы алгоритма доказали его оптимальность: никакой другой алгоритм, использующий ту же самую эвристику, не сможет исследовать меньше вершин, чем A*, и при этом гарантированно найти кратчайший путь.

Но он тоже требовательный к памяти. Потому что это вариант поиска в ширину. 

Алгоритм A* работает как умный навигатор, который на каждом шаге выбирает следующую точку на основе двух вещей: сколько он уже прошёл и сколько, по его мнению, ещё осталось до цели.

Для этого алгоритм использует две очереди (или списка) и одну главную формулу.

Главная формула оценки: f(n) = g(n) + h(n)

Каждому перекрёстку (вершине (n)), который видит алгоритм, присваивается оценка привлекательности f(n):

1. g(n) - реальная стоимость пути от самого старта до текущей вершины n. Это то, сколько шагов мы уже реально потратили.
2. h(n) - эвристика, которую мы рассмотрели.
3. f(n) - итоговая оценка пути через эту вершину. Чем меньше это число, тем перспективнее выглядит маршрут.

    

Два главных списка алгоритма

Алгоритм раскладывает все известные ему точки по двум кучкам:

• ОткрытыйСписок: Перекрёстки, которые мы уже обнаружили, посчитали для них оценку f(n), но ещё не заходили на них, чтобы осмотреться дальше. Это список кандидатов на следующий шаг.
• ЗакрытыйСписок: Перекрёстки, которые мы уже посетили и проверили все ответвления от них. Туда возвращаться больше не нужно.

Пошаговый алгоритм:

1. Старт: Помещаем стартовую точку в ОткрытыйСписок. Её (g = 0), а f равна эвристике до цели.
2. Поиск лучшего: Пока ОткрытыйСписок не пуст, берём из него вершину с самым маленьким значением f(n).
3. Проверка на победу: Смотрим - не является ли эта выбранная вершина нашей целью?
   1. Если да, то ура, путь найден! Восстанавливаем маршрут по "хлебным крошкам" (указателям, откуда мы пришли).
4. Шаг вперёд (исследование соседей): Если это ещё не цель, переносим текущую вершину в ЗакрытыйСписок. Затем смотрим на всех её соседних соседей:
   1. Если сосед уже в ЗакрытыйСписок - игнорируем (мы там уже были).
   2. Если сосед уже в ОткрытыйСписок - тоже игнорируем, пока не пришло его время, значит мы его когда-то уже оценивали, новая оценка с учетом уже пройденного пути, точно будет больше.
   3. Считаем для соседа новый потенциальный путь через текущую вершину.
   4. Если соседа ещё нет в ОткрытыйСписок - добавляем его туда и записываем, откуда мы к нему пришли (чтобы потом собрать путь обратно).
5. Повтор: Возвращаемся к пункту 2. 
6. Если ОткрытыйСписок опустел, а до цели мы так и не дошли - значит, пути вообще не существует.
   Но этого в нашем случае не может быть, мы были к этому готовы поэтому сразу не пошли бы этим путем.

Хороший и быстрый алгоритм. Но не подходит для пятнашек в чистом виде. Тоже моментально заполнит всю память под огромное количество узлов. На такой случай есть разные модификации с управлением занимаемой памятью - под списки выделяется фиксированный объем, а по мере заполнения из него удаляют наименее перспективные узлы.

Но это приводит к ухудшению эффективности - накладные расходы на менеджмент памяти и повторное прохождение одних и тех же маршрутов, которые "забыли", но вдруг пришлось вспомнить.

4.2. Алгоритм IDА*

Тут нам на помощь приходит второй алгоритм информированного поиска - IDA* (Iterative deepening A*, итеративно углубляющийся A*).

Алгоритм выполняет поиск в глубину, в отличие от предшественника. Он использует те же функции, что и предок: глубина текущего пути g(n), эвристика h(n) и итоговая сумма f(n). 

Он ограничивает глубину поиска пороговым значением стоимости f(n) = g(n) + h(n).

1. В качестве первого значения порога принимается значение функции эвристики h(n) в начальной вершине. 
2. Запускаем итерацию поиска с этим значением порога.
3. Ведем поиск в глубину.
   1. Если мы уткнулись в тупик по порогу, то запоминаем минимальную оценку выше порога (МинимальнаяОценкаВышеПорога) из всех соседей тупиковой вершины.
   2. Возвращаемся к развилке - рекурсивно переходим к п.3, углубляемся в следующий возможный путь до следующего тупика.
   3. Если цель найдена - то ура! Выходим из рекурсии с возвращением значения
   4. Если тупик, то переходим к п. 3.a.
4. Если цель не найдена при выходе из рекурсии, порог увеличивается до МинимальнаяОценкаВышеПорога, и переход к п.2.

• A* хранит в памяти всю карту исследованных окрестностей (дерево поиска целиком). Для пятнашек эта память кончается молниеносно.
• IDA* хранит в памяти только текущую ветку (длиной максимум в L шагов). Расход памяти растёт не экспоненциально, а линейно. Именно поэтому пятнашки на рекордную глубину решают именно через IDA*.

Естественно за это надо платить скоростью работы. Т.к. мы очень много раз проходим по одним и тем же узлам.

Но с этого хотя бы можно начать. И это еще не конец истории, дальше тоже будет все очень непросто. Такая вот простая игра "Пятнашки"...

Об этом я, надеюсь, расскажу в следующий раз...