Пятнашки — правила игры и стратегии решения¶

Пятнашки — головоломка, состоящая из квадратной рамки с углублением 4×4 клетки и пятнадцати квадратных плиток с числами от 1 до 15, которые перемещаются в свободную клетку. Цель игры — расставить плитки по порядку: 1, 2, 3, …, 15 — так, чтобы пустая клетка осталась в правом нижнем углу. Пятнашки относятся к классу механических головоломок и являются одним из самых известных примеров задач на комбинаторную оптимизацию.

¶История

Игра создана в 1874 году американским инженером Нойсом Пайтом (Noyes Chapman), почтовым служащим из штата Нью-Йорк. Первоначально плитки были вставлены в рамку неподвижно, и игрок должен был выдвигать их через прорезь сбоку. В таком виде игра не получила распространения.

В 1880 году игра была запатентована и выпущена компанией Milton Bradley. Плитки сделали подвижными — их можно было вынимать и переставлять через открытую сторону рамки. В том же году пятнашки стали настоящим хитом в США и Европе: за короткое время было продано свыше 400 000 экземпляров. Появился даже термин «пятнашечная лихорадка» (15 puzzle craze).

Интерес математиков к игре возник практически одновременно с её популярностью. В 1879 году в журнале «American Journal of Mathematics» было опубликовано доказательство того, что из 16! = 20 922 789 888 000 возможных расположений плиток достижимы лишь половинные — 16!/2. Это объясняет, почему некоторые начальные расстановки неразрешимы.

¶Правила

Игровое поле — рамка 4×4 клетки, в которой размещены 15 плиток с числами и одна пустая клетка. За один ход игрок сдвигает в пустую клетку одну из соседних плиток (по горизонтали или вертикали, по диагонали — нельзя). Цель — получить конфигурацию, при которой плитки выстроены по возрастанию слева направо и сверху вниз, а пустая клетка находится в правом нижнем углу.

Ключевое правило, определяющее разрешимость: перестановка плиток разрешима тогда и только тогда, когда чётность перестановки плиток (без учёта пустой клетки) совпадает с чётностью манхэттенского расстояния пустой клетки от правого нижнего угла.

¶Методы решения

¶Решение вручную

Классический подход — пошаговая сборка по рядам. Сначала расставляются плитки 1 и 2 в первой строке, затем 3 и 4, после чего первая строка «запирается» — плитки 1–4 больше не перемещаются. Далее аналогично собирается вторая строка (5–8), затем третья (9–12). Остаётся пятый ряд, который решается тривиально.

При сборке последних двух плиток в строке (например, 3 и 4) возникает типичная проблема: если поставить 3 на место, то 4 окажется под ней, и их нельзя переставить, не разрушив первую строку. Решение — временно увести 3 вниз, поставить 4 на место, затем вернуть 3. Этот приём требует планирования на 2–4 хода вперёд.

Для сборки последних двух рядов используется иной алгоритм: плитки 9–15 расставляются вокруг центральной области, а затем вся группа поворачивается на нужный угол. Этот этап считается самым сложным при ручном решении.

¶Алгоритмы для компьютеров

Для автоматического решения пятнашек применяются алгоритмы поиска с возвратом и эвристические методы:

• A\* — поиск кратчайшего решения с эвристикой, например суммой манхэттенских расстояний плиток от целевых позиций;
• IDA\ — итеративное углубление A\, экономящее память;
• Algorithm X — алгоритм поиска точного покрытия, применяемый в сочетании с методом Dancing Links;
• Королевский алгоритм (Robert Endre Tarjan, 1980-е) — метод, основанный на разложении перестановки на циклы.

Известно, что любую разрешимую конфигурацию пятнашек можно решить не более чем за 80 ходов (длина диаметра группы состояний). Наименьшее число ходов для худшей конфигурации было вычислено в 2010 году группой исследователей с использованием кластерных вычислений.

¶Разновидности

Помимо классической рамки 4×4, существуют варианты с полем 3×3 (8 плиток), 5×5 (24 плитки) и более крупные. Распространены тематические версии — с буквами, изображениями, цветами вместо чисел. В цифровом виде пятнашки реализованы во многих операционных системах: в частности, игра «15» поставлялась с Windows 3.1 и Windows 95, а в Windows 7 и 8 — как «Microsoft Puzzle».

¶Интересные факты

В 1880 году из-за популярности игры в США возникла мода на математические конкурсы: издатели предлагали денежные призы за решение специально подобранных конфигураций. Так как часть из них была неразрешима, победить было невозможно — это стало одним из первых случаев массового мошенничества с математической подоплёкой.

В 1996 году алгоритм A\* с эвристикой «линейное нарушение» позволил решать любую разрешимую конфигурацию в среднем за 22 хода.

Источники:

• Савелов А. А. «Математические основы теории игр»
• Gardner M. «Mathematical Games» (Scientific American)
• Korf R. E. «Depth-First Iterative-Deepening: An Optimal Admissible Tree Search»
• Ratner D., Warmuth M. «Finding a shortest solution for the N×N extension of the 15 puzzle is NP-complete»