Игра «пятнашки». Игра "Пятнашки"

Пятнашки — популярная головоломка, придуманная в 1878 году Ноем Чемэном. Существует вариант для восьми элементов. Представляет собой набор одинаковых квадратных костяшек с нанесёнными числами, заключённых в квадратную коробку. Длина стороны коробки в четыре раза больше длины стороны костяшек для набора из 15 элементов и в три раза больше для набора в 8 элементов, соответственно в коробочке остаётся незаполненным одно квадратное поле. Цель игры — перемещая костяшки по коробке добиться упорядочивания их по номерам, желательно сделав как можно меньше перемещений.

История создания

С 1891 года до самой смерти Сэм Ллойд считал, что изобрёл головоломку именно он. Однако существуют доказательства того, что он был непричастен к созданию «пятнашек». Настоящим изобретателем был Ной Палмер Чепмэн, почтмейстер из Канастоты, который ещё в 1874 году показывал друзьям головоломку, состоящую из шестнадцати пронумерованных квадратиков, которые надо было сложить в ряды по четыре штуки так, чтобы сумма чисел в каждом ряду была равна 34. Затем сын Ноя Чепмэна, Фрэнк Чепмэн привёз доработанные головоломки в Сиракузы (штат Нью-Йорк), а затем в Хартфорд (Коннектикут), где слушатели Американской школы для слабослышащих начали производство головоломки. К 1879 году она уже продавалась не только в Хартфорде, но и в Бостоне. Тогда о «пятнашках» узнал художник по дереву Маттиас Райс. В декабре 1879 года он начал бизнес по производству новой головоломки под названием «Драгоценная головоломка» (англ. Gem Puzzle). В начале 1880 года некий Чарльз Певи, дантист из Ворчестера, привлёк внимание общественности, предложил денежное вознаграждение за решение задачи собирания головоломки, что добавило популярности новой забаве. Весной того же года игра достигла Европы. 21 февраля 1880 года Ной Чепмэн попытался оформить патент на своё изобретение (патент назывался «Головоломка из бриллиантовых блоков», «Block Solitaire Puzzle»), однако заявка на патент была отклонена, так как мало отличалась от уже оформленного тремя годами ранее патента «Хитрые блоки», «Puzzle-Blocks».

Математическое описание

Пятнашки представляют собой классическую задачу для моделирования эвристических алгоритмов. Обычно задачу решают через количество перемещений и поиск манхттенского расстояния между каждой костяшкой и ёё позицией в собранной головоломке. Для решения используются алгоритмы наподобие алгоритма А*.

Нерешаемая комбинация, предложенная Ноем Чепменом Можно показать, что ровно половину из всех возможных 1 307 674 368 000 (=15!) начальных положений пятнашки невозможнопривести к собранному виду: пусть квадратик с числом i расположен до (если считать слева на право и сверху вниз) k квадратиков с числами меньшими i. Будем считать ni = k, то есть если после костяшки с i-м числом нет чисел, меньших i, то k = 0. Также введем чмсло е — номер ряда пустой клетки (считая с 1). Если сумма является нечётной, то решения головоломки не существует.

Для вариантов пятнашек с большим, чем 15, количеством костяшек задача поиска кратчайшего решения является NP-полной.