Пятнашки

Статья "Пятнашки" является частью вспомогательных материалов кафедры веб-технологий.

Пятнашки (англ. Fifteen puzzle) — это слайдинг-головоломка, которая состоит из квадратной коробки, в которой находятся пронумерованные квадратные блоки, расположенные в произвольном порядке; при этом одно место для блока в коробке свободно.

Пятнашки в одном из исходных (нерешённых) положений

Пятнашки в решённом положении

Цель головоломки заключается в размещении блоков по порядку (см. рисунки), делая ими скользящие движения, используя пустое пространство в коробке.

В виде N-головоломки (англ. n-puzzle) пятнашки являются классической задачей для моделирования алгоритмов с использованием эвристики. Обычно использование эвристики для решения этой задачи включает подсчет количества перемещений блоков и нахождение суммы манхеттенских расстояний между каждым блоком и его положением в целевой конфигурации.

Решаемость головоломки

Джонсон и Стори в 1879 году использовали аргумент паритета, чтобы показать, что половину стартовых позиций для N-головоломки невозможно решить; и при этом не важно, сколько ходов было сделано.

Примечания

При создании этой страницы использовались материалы страницы en:Fifteen puzzle согласно лицензии Creative Commons Attribution/Share-Alike 3.0