Пятнашки
Пятнашки (англ. Fifteen puzzle) — это слайдинг-головоломка, которая состоит из квадратной коробки, в которой находятся пронумерованные квадратные блоки, расположенные в произвольном порядке; при этом одно место для блока в коробке свободно.
Цель головоломки заключается в размещении блоков по порядку (см. рисунки), делая ими скользящие движения, используя пустое пространство в коробке.
В виде N-головоломки (англ. n-puzzle) пятнашки являются классической задачей для моделирования алгоритмов с использованием эвристики. Обычно использование эвристики для решения этой задачи включает подсчет количества перемещений блоков и нахождение суммы манхеттенских расстояний между каждым блоком и его положением в целевой конфигурации.
Решаемость головоломки
[править]Джонсон и Стори в 1879 году[1][2] использовали аргумент паритета, чтобы показать, что половину стартовых позиций для N-головоломки невозможно решить; и при этом не важно, сколько ходов было сделано.
Примечания
[править]- ↑ Johnson Wm. Woolsey, Story William E. "Notes on the "15" Puzzle"
- ↑ статья в открытом доступе