Головоломка пятнашки представляет собой квадратную коробку с 15 пронумерованными костяшками и одним пустым полем. Задача выглядит просто — упорядочить числа последовательно, но за внешней простотой скрывается глубокая математическая структура, которая десятилетиями привлекала внимание математиков и программистов.
Происхождение и первая математическая загадка
Ной Палмер Чепмен, почтмейстер из Канастоты, в 1874 году показал друзьям первый вариант головоломки. Изначально требовалось расположить 16 квадратиков в ряды так, чтобы сумма чисел каждого ряда равнялась 34. К 1880 году игра захватила США, а весной достигла Европы, распространившись в России, Германии, Франции и других странах.
Американский шахматист Сэмюэл Лойд в 1891 году предложил задачу, которая стала легендарной. “Головоломка остаётся решаемой для большинства начальных позиций. Переставленные 14 и 15 делают задачу неразрешимой” – пишет Gallerix.ru. Лойд обещал награду в 1000 долларов тому, кто соберёт пятнашки с переставленными последними двумя числами. Приз никто не получил — математика исключала решение.
Теория инверсий и решаемость
Ключ к пониманию решаемости головоломки лежит в концепции инверсий. Инверсия возникает, когда большее число стоит перед меньшим при последовательном обходе позиций. Для финальной позиции количество инверсий равно нулю, поскольку все числа выстроены по возрастанию.
При горизонтальном перемещении костяшки число инверсий остаётся неизменным. Порядок чисел сохраняется, пустая клетка не учитывается. Вертикальное перемещение меняет ситуацию — между перемещаемым числом и пустой клеткой всегда находятся три других числа. Поскольку три нечётно, изменение количества инверсий также будет нечётным — добавится или убавится 1 или 3 инверсии.
Каждый вертикальный ход меняет чётность инверсий. Если начальная позиция имеет чётное число инверсий, а конечная — нулевое (тоже чётное), задача решаема. Перестановка двух костяшек создаёт одну инверсию — нечётное число — и делает головоломку нерешаемой из стандартной финальной позиции.
Алгоритмы оптимального решения
Компьютерное решение пятнашек требует обхода графа всех возможных состояний поля. Алгоритм A* стал стандартом для этой задачи. Он использует эвристическую функцию для оценки перспективности каждого хода, выбирая направление с минимальной предполагаемой ошибкой.
Манхэттенское расстояние
Наиболее популярная эвристика — манхэттенское расстояние. Для каждой костяшки вычисляется сумма абсолютных разностей текущих и целевых координат по вертикали и горизонтали. Общая оценка складывается из манхэттенских расстояний всех костяшек. Эта метрика даёт нижнюю границу необходимых ходов — реальное решение не может требовать меньше перемещений.
Алгоритм без учёта номера шага находит решение быстро, но не оптимально. Программа может выдать 90 ходов там, где оптимум составляет 44 хода. Добавление веса текущего шага замедляет вычисления, но гарантирует минимальное решение. Разница во времени расчёта может достигать сотен раз.
Проверка валидности начальной позиции
Перед запуском алгоритма необходимо проверить решаемость позиции. Простой обмен двух соседних костяшек создаёт нерешаемую конфигурацию — программа будет бесконечно перебирать варианты, не приближаясь к цели. Алгоритм проверки подсчитывает инверсии и определяет чётность. Для поля с нечётной шириной решаемость зависит от совпадения чётности инверсий начальной и конечной позиций.
При случайной перетасовке костяшек половина позиций оказывается нерешаемой. Практическое решение — поменять местами два самых больших числа (14 и 15 для стандартного поля), что изменит чётность инверсий и сделает позицию решаемой.
Вычислительная сложность
Количество возможных позиций в пятнашках равно 16!/2, что составляет более 10 триллионов комбинаций. Половина из них нерешаема, но даже среди решаемых позиций поиск оптимального пути представляет серьёзную задачу. Глубина решения может достигать 80 ходов для наихудших случаев.
Различные эвристики дают разный баланс между скоростью вычислений и качеством решения. Более точные эвристики требуют драматически больше времени — в некоторых случаях вычисления могут занимать более часа на современном компьютере. Оптимизация с помощью специализированных интерпретаторов сокращает время в десятки раз, но общая сложность остаётся высокой.
Современные решатели предлагают выбор из нескольких эвристик, позволяя пользователю выбрать приоритет — скорость или минимальное число ходов. Некоторые реализации выводят не линейный, а спиральный порядок чисел, добавляя вариативность в классическую задачу.
