15-головоломка была бенчмарком для алгоритмов AI-поиска с 1960-х. Каждое поколение алгоритма изобреталось, чтобы пробить стену, в которую упёрся предыдущий. Эта статья проходит их в порядке изобретения, рассказывая, для чего каждый был хорош и что сделало необходимым следующий.
1960-е — Breadth-first search
Первый алгоритм, который пробует каждый. Исследовать состояния по уровням: на глубине 1 — 4 состояния, на 2 — 16, на 3 — 64, и так далее. Продолжать, пока не найдёте цель.
Для 8-puzzle BFS завершается быстро — худшая глубина 31, поэтому максимум 4³¹ состояний (намного меньше на практике из-за повторов). Для 15-головоломки худшая глубина 80, поэтому 4⁸⁰ состояний. Это больше состояний, чем атомов в наблюдаемой Вселенной. BFS не завершается.
Стена: экспоненциальный взрыв. Решение неинформированным поиском безнадёжно за пределами 3×3.
1968 — A*-поиск
Hart, Nilsson и Raphael публикуют A Formal Basis for the Heuristic Determination of Minimum Cost Paths. Идея: вместо исследования состояний в порядке расстояния от старта, исследовать в порядке f = g + h, где h — нижняя оценка расстояния до цели.
Для 15-головоломки h — манхэттенское расстояние: сумма строчных+столбцовых дистанций каждой плитки до её цели. Manhattan допустим (никогда не переоценивает) и консистентен (удовлетворяет неравенству треугольника). С этими свойствами A* находит оптимальное решение.
Производительность на 15-головоломке: решает любую доску, но на самых сложных инстансах исследует миллионы состояний и съедает сотни мегабайт памяти. Стена: память.
1985 — IDA*
Depth-first iterative-deepening: An optimal admissible tree search Ричарда Корфа. Озарение: вместо приоритетной очереди A* (что держит все исследованные состояния), сделать итеративно-углубляющийся DFS, где порог глубины — это f-стоимость, а не глубина.
IDA* исследует те же состояния, что и A*, примерно в том же порядке, но без запоминания между итерациями. Каждый «глубинный проход» использует O(глубина) памяти вместо O(исследованных).
Производительность на 15-головоломке: решает любую доску за секунды на железе 1985 года, помещается в килобайты памяти. Стена: эвристика всё ещё Manhattan. Ускорение поиска требует более плотной эвристики.
1990-е — Linear conflict
Criticizing solutions to relaxed models yields powerful admissible heuristics — Hansson, Mayer и Yung. Эвристика Manhattan предполагает, что плитки могут проходить друг через друга. Не могут.
Linear conflict добавляет 2 хода к эвристике за каждую пару плиток в одной строке, обе принадлежащие этой строке, но в неправильном порядке — одну из них придётся вытолкнуть из строки, чтобы пропустить другую. Аналогично для столбцов.
Эффект: обычно 5–15% снижение развёрнутых узлов на сложных 15-puzzle. Строгое улучшение Manhattan; нет реальных минусов.
1996 — Walking distance
Эвристика, ловящая структуру пазла глубже. Для каждой конфигурации плиток, спроецированной только на строки (игнорируя позицию внутри строки), предварительно посчитайте минимальное число операций своп-строки, чтобы поставить каждую плитку в правильную строку. То же для столбцов.
Walking distance допустима и значительно плотнее Manhattan + linear conflict — обычно в 1,5–2 раза значение Manhattan, что означает, что IDA* разворачивает гораздо меньше узлов.
Стоимость реализации: маленькая предрассчитанная таблица (~500 КБ для 4×4). Золотая середина для 15-головоломки.
2002 — Аддитивные непересекающиеся базы шаблонов
Disjoint pattern database heuristics — Корф и Фелнер. Сильнейшая известная эвристика для слайдинг-пазлов.
Идея: разбейте плитки на непересекающиеся группы (разбиение 7+8 для 15-puzzle — стандарт). Для каждой группы предварительно посчитайте оптимальную стоимость перемещения только этой группы в её целевые позиции, игнорируя остальные плитки. Табулируйте каждую возможную конфигурацию группы.
Во время поиска складывайте вклад каждой группы. Из-за непересечения и аккуратного аргумента, что нужные ходы каждой группы не конфликтуют, сумма допустима.
Стоимость памяти: около 1 ГБ для 15-puzzle. Производительность: решает самую сложную 15-puzzle за несколько тысяч развёртываний узлов — миллисекунды.
2005+ — большие базы для больших пазлов
Та же техника масштабируется до 24-puzzle (5×5) и дальше. Разбиение 5+5+5+9 для 24-puzzle — около 4 ГБ. С ним любая случайная 24-puzzle решается за секунды.
35-puzzle (6×6) — на грани решаемого. Самые сложные 6×6 инстансы — всё ещё открытое исследование на 2026 год.
2010-е+ — нейросетевые эвристики
Нейросети обучают предсказывать Manhattan-подобную величину для слайдинг-пазлов, иногда давая более плотные эвристики, чем ручные. Подвох: NN-эвристики обычно недоказуемо допустимы, поэтому построенные на них солверы дают вероятно-оптимальные, а не гарантированно-оптимальные ответы.
Для исследовательских статей интересно. Для отгружаемого ПО, где оптимальность важна (калибровка сложности в играх), классические базы шаблонов остаются правильным инструментом.
Почему эта история важна
Каждая волна исследований по слайд-пазл-алгоритмам шла под одним давлением: пазл достаточно мал, чтобы алгоритмы можно было бенчмаркить, и достаточно велик, чтобы плохие уходили в таймаут. 15-головоломка была полигоном для общих продвижений в эвристическом поиске — A*, IDA*, базы шаблонов — которые сейчас питают планирование маршрутов, доказательство теорем и многие другие домены.
Когда вы решаете 15-головоломку в приложении с помощью кнопки подсказки, вы используете алгоритмы, разработанные именно для этой игры, и потом обобщённые везде.
Сводная таблица
| Год | Алгоритм | Время на сложную 15-puzzle | Память | Что позволило |
|---|---|---|---|---|
| 1960-е | BFS | Не завершается | Гигантская | — |
| 1968 | A* + Manhattan | Минуты | Сотни МБ | Эвристический поиск |
| 1985 | IDA* + Manhattan | Секунды | КБ | Iterative deepening |
| 1996 | IDA* + walking distance | < 1 с | + 500 КБ предрасчёт | Лучшая эвристика |
| 2002 | IDA* + 7+8 база | Миллисекунды | + 1 ГБ предрасчёт | Перебор подмножеств |
Каждая строка — реальный качественный скачок, не маргинальное улучшение. История решения 15-головоломки — это также история современного эвристического поиска.