Есть два способа решить 15-головоломку. Один — тот, до которого рано или поздно доходит каждый игрок: собрать верхнюю строку, потом левый столбец, рекурсивно. Второй — то, как это делают компьютеры: эвристический поиск по миллионам состояний, направляемый умной нижней оценкой числа оставшихся ходов.
Это руководство покрывает оба, примерно в том порядке, в котором их обычно изучают.
15-головоломка в одном абзаце
Доска 4×4, пятнадцать нумерованных плиток, одна пустая клетка. Задвигаете плитки в пустоту, пока числа не выстроятся по порядку — 1 до 15, пустая в правом нижнем углу. Доску изобрёл Ноес Чепмен в 1874 году, и в 1880-х она стала международным помешательством после того, как Сэм Лойд объявил приз $1000 за решение нерешаемого варианта. Фундаментально это та же игра, что 8-puzzle, — просто на строку и столбец больше.
Решение вручную: метод строки-и-столбца
Технология, до которой каждый человек рано или поздно доходит, такова:
- Решите строку 1. Поставьте 1 и 2. Затем 3 в правый верхний угол. Г-образный манёвр — поднесите 4 на место 3, задвиньте 3 под, потом проверните пару в угол — это приём, который делает углы возможными.
- Решите столбец 1. Поставьте 5, потом 9, потом 13 в нижнем-левом углу тем же угловым приёмом.
- Рекурсия. Осталась подзадача 3×3 (с правой колонкой и нижней строкой), которая и есть 8-puzzle, решать который вы уже умеете.
Уверенный игрок решает 15-головоломку вручную за 3–5 минут. Новичок может потратить 20 минут в первый раз и треть от этого к третьему.
Тот же метод масштабируется до 5×5 и 6×6. Рекурсия всегда заканчивается эндшпилем 3×3.
Оптимальный солвер: A* с манхэттенским расстоянием
Компьютер может намного лучше метода строки-и-столбца. Конкретно: он может найти кратчайшее решение, в которое человек редко играет.
Математический факт: медианная 15-головоломка требует около 52 одиночных сдвигов при оптимальном решении. Худший случай — 80. Метод строки-и-столбца обычно делает 100–150 ходов на той же доске.
Чтобы найти оптимальное решение, A*-поиск рассматривает каждое состояние доски как узел, каждый ход — как ребро, и спрашивает: сколько ходов до цели, как минимум? Точно посчитать оставшееся число ходов без решения пазла невозможно, но хорошая нижняя оценка делает A* быстрым.
Классическая нижняя оценка — манхэттенское расстояние:
Для каждой плитки сложите расстояние по строкам и расстояние по столбцам от её текущей позиции до целевой. (Пустую игнорируем.)
Манхэттенское расстояние допустимо (admissible) — оно никогда не переоценивает истинное расстояние, потому что каждая плитка должна пройти как минимум столько. С A* и манхэттенским расстоянием 8-puzzle решается за микросекунды, а 15-головоломка — за секунды.
IDA*: память-дружелюбный кузен
A* должен помнить каждое исследованное состояние. Для 15-головоломок это сотни мегабайт ОЗУ на самых сложных досках. Iterative-deepening A (IDA)** меняет память на время, делая DFS с ограничением по глубине, увеличивая глубину каждую итерацию.
IDA* — то, что использует в реальности каждый эталонный солвер для 15-головоломки. Статья Ричарда Корфа 1985 года представила IDA* именно для того, чтобы решать 15-головоломки оптимально на железе начала 1980-х.
За пределами манхэттенского: walking distance и базы шаблонов
Манхэттенское расстояние быстрое, но рыхлое. Оно предполагает, что плитки могут свободно проходить друг через друга. Не могут — двум плиткам в одной строке нужно ходить по очереди, что стоит лишних ходов.
Walking distance учитывает эти лишние ходы. Заранее посчитайте, для каждой пары строк, минимальное число «своп-строки» нужных, чтобы переставить плитки в правильные строки. То же самое для столбцов. Сложите. Результат доказуемо плотнее манхэттенского расстояния — обычно примерно на 25% больше, что означает, что A*/IDA* исследует на 25% меньше узлов.
Сильнейшая известная эвристика для 15-головоломки — аддитивная база шаблонов с непересекающимися подмножествами (disjoint pattern database):
- Разбейте плитки на непересекающиеся группы (обычное разбиение — 5-5-5 плюс пустая).
- Для каждой группы предварительно посчитайте, для каждой возможной конфигурации плиток этой группы на доске, минимальное число ходов, чтобы поставить плитки группы в их целевые позиции, игнорируя остальные плитки.
- Во время поиска складывайте посчитанное для каждой группы.
Разбиение 7+8 для 15-головоломки занимает около 1 ГБ для хранения, но позволяет IDA* решать любую 15-головоломку за миллисекунды. Для 24-головоломки (5×5) базы шаблонов — по сути единственный практичный подход.
Почему ручное решение обычно быстрее (для одной партии)
Короткая проверка реальностью: написать A*, выбрать эвристику и дождаться его работы дольше, чем взять одну 15-головоломку и решить её вручную. Математика интересна; практичность в том, что человек, знающий метод строки-и-столбца, решает любую доску за пять минут ровно.
Солверы нужны для совокупности: исследовательских работ, сравнивающих эвристики на тысячах случайных инстансов; учебников по ИИ, использующих 15-головоломку как бенчмарк; и приложений, которым нужно генерировать пазлы, гарантированно решаемые примерно за N ходов для калибровки сложности.
Рекомендуемый порядок чтения
Если вы пришли сюда написать солвер, начните с A*/Manhattan, посмотрите как он решает несколько 8-puzzle, потом перенесите на IDA* для 15-головоломки. После этого walking distance — это 100 строк добавки, удваивающие скорость. Базы шаблонов — проект на выходные, который покупает ещё порядок ускорения.
Если вы пришли сюда сыграть в 15-головоломку, сначала изучите метод строки-и-столбца, потом прочтите почему некоторые доски нерешаемы, а потом возвращайтесь сюда за теорией.