Введение
Пятнашки — классическая головоломка-слайдер, состоящая из 15 пронумерованных квадратных плиток, размещённых в коробке 4×4 с одной пустой ячейкой. Задача — упорядочить плитки от 1 до 15, перемещая их в пустое пространство. Несмотря на кажущуюся простоту, головоломка обладает глубокой математической структурой и более чем 140-летней историей.
История
Происхождение пятнашек долгое время приписывалось Сэму Лойду — знаменитому американскому автору головоломок, который в 1878 году предложил призовую задачу: переставить плитки 14 и 15 местами. Однако историки установили, что головоломку изобрёл Ноайес Чэпмен (Noyes Chapman) из штата Нью-Йорк в 1874 году. В 1880 году пятнашки вызвали массовое увлечение в США и Европе — газеты писали о «пятнашечной лихорадке». Задача Лойда (поменять 14 и 15) была доказана неразрешимой, что подогрело интерес публики.
Правила
Игровое поле представляет собой квадратную рамку 4×4, содержащую 15 плиток с числами от 1 до 15 и одно пустое место. За один ход можно сдвинуть одну плитку, смежную с пустой клеткой, на это пустое место (вверх, вниз, влево или вправо). Цель — расположить все плитки по порядку: от 1 в верхнем левом углу до 15 в нижнем правом, оставив пустую клетку в правом нижнем углу.
Математика пятнашек
Общее число перестановок 16 позиций (включая пустую) составляет 16! = 20 922 789 888 000. Однако ровно половина из них достижима из начальной позиции — 10 461 394 944 000 состояний. Разделение на два класса определяется чётностью перестановки: если сумма числа инверсий и номера строки пустой клетки (считая снизу) чётна, позиция разрешима; если нечётна — нет. Именно поэтому задача Лойда неразрешима: перестановка плиток 14 и 15 меняет чётность.
Диаметр графа пятнашек (максимальное число ходов для оптимального решения наихудшей позиции) равен 80. Это значение было определено в 2011 году путём полного компьютерного перебора. Среднее оптимальное решение требует около 52,5 хода.
Стратегии решения
Для ручного решения наиболее распространён послойный метод. Сначала собирается первая строка (числа 1, 2, 3, 4), затем вторая (5, 6, 7, 8), после чего оставшиеся числа 9–15 собираются в нижних двух строках столбец за столбцом. Ключевой приём — «парковка»: чтобы установить крайнюю плитку ряда, временно нужно разместить предпоследнюю в специальную позицию.
Для компьютерного решения применяются алгоритмы поиска: A* с манхэттенской эвристикой (сумма расстояний каждой плитки до целевой позиции), IDA* (Iterative Deepening A*) и Pattern Database (базы предвычисленных шаблонов). IDA* с аддитивными базами паттернов решает любую позицию за доли секунды.
Варианты
Помимо классических пятнашек 4×4, существуют версии 3×3 (восьмёрка), 5×5 (двадцать четыре) и более крупные. Вариант 3×3 тривиален (максимум 31 ход), а 5×5 значительно сложнее — задача оптимального решения NP-трудна для обобщённого n×n поля. Также популярны пятнашки с картинками вместо чисел и цифровые версии на смартфонах.
Заключение
Пятнашки — элегантная головоломка, сочетающая доступность и математическую глубину. Её простые правила скрывают богатую комбинаторную структуру, а история с неразрешимой задачей Лойда остаётся одним из самых ярких примеров взаимосвязи математики и популярных развлечений.
