История создания самых известных головоломок


Пятнашки (The 15 Puzzle, Fifteen)

Этой логической игре более ста лет. И за свою долгую историю эта головоломка носила разные имена: Fifteen Puzzle, Puzzle-Blocks , Gem Puzzle, Boss Puzzle, Game of Fifteen и Mystic Square.

С 1891 года до самой смерти Сэмюэл Лойд (Samuel Loyd) утверждал, что изобрёл головоломку именно он. Однако существуют доказательства того, что он был непричастен к созданию «пятнашек».

Настоящим изобретателем головоломки был Ной Палмер Чепмэн (Noyes Palmer Chapman), почтмейстер из Канастоты (штат Нью-Йорк, США), который ещё в 1874 году показывал друзьям головоломку, состоящую из шестнадцати пронумерованных квадратиков, которые надо было сложить в ряды по четыре штуки так, чтобы сумма чисел в каждом ряду была равна 34.

Сын Ноя Чепмэна, Фрэнк Чепмэн, привёз доработанные головоломки в Сиракузы (штат Нью-Йорк, США), а затем в Хартфорд (штат Коннектикут, США), где слушатели Американской школы для слабослышащих начали производство головоломки. К 1879 году она уже продавалась не только в Хартфорде, но и в Бостоне. Тогда о «пятнашках» узнал художник по дереву Маттиас Райс. В декабре 1879 года он начал бизнес по производству новой головоломки под названием «Драгоценная головоломка» (Gem Puzzle).

В начале 1880 года некий Чарльз Певи, дантист из Вустера, привлёк внимание общественности, предложив денежное вознаграждение за решение задачи собирания головоломки, что добавило популярности новой забаве. Весной того же года игра достигла Европы.

21 февраля 1880 года Ной Чепмэн попытался оформить патент на своё изобретение под наименованием «Block Solitaire Puzzle», однако заявка на патент была отклонена, так как мало отличалась от уже оформленного тремя годами ранее патента «Хитрые блоки», «Puzzle-Blocks».

Но всех больше остался в истории Сэм Ллойд – он больше всех утверждал, что именно он является изобретателем этой головоломки. И именно он назначил приз в 1000 долларов (грандиозной по тем временам призовой сумме) любому, кто сможет решить задачу по перестановке местами двух частей головоломки – фишек с числами 15 и 14. Так что теперь весьма распространённой ошибкой является то, что именно Сэм Ллойд является изобретателем головоломки «Пятнашки». Масса людей бросилась искать решение этой задачи. Конечно же, все они предварительно купили у предприимчивого Сэма Ллойда его продукцию. Началось так называемое «пятнашечное сумасшествие».



Карикатура изображающая Сэма Ллойда и проблему «15-14»


Довольно быстро массовое движение по всеобщей заинтересованности головоломкой «Пятнашки» охватило Америку, Европу, Австралию, Новую Зеландию и даже азиатские страны. Разгадка перестановки двух фишек стало почти всеобщим помешательством. Желающие найти решение увлечённо искали способ, забывая про еду, сон, учёбу и работу. Владельцы предприятий запрещали приносить на работу эту адскую игру, так как работники переставали работать. Владельцы бакалейных лавочек забывали открывать двери своих магазинов и принимать посетителей, лоцманы сажали суда на мель, а машинисты поездов проезжали станции увлечённо решая задачу по перестановке фишек. Рассказывали даже об одном известном священнике, который простоял зимнюю ночь под уличным фонарём и всё это время пытался вспомнить как ему удалось переставить местами фишки 15 и 14. Самое удивительное, что никто из тех кто утверждал, что нашёл решение не мог вспомнить и повторить последовательность ходов, которая привела к победе.




"…За последние несколько недель вошла в моду новая игрушка-головоломка... и что от Атлантического океана до Тихого все население Соединенных Штатов прекратило работу и занимается только этой игрушкой; что в связи с этим вся деловая жизнь в стране замерла, ибо судьи, адвокаты, взломщики, священники, воры, торговцы, рабочие, убийцы, женщины, дети, грудные младенцы, — словом, все с утра до ночи заняты одним-единственным высокоинтеллектуальным и сложным делом... что веселье и радость покинули народ — на смену им пришли озабоченность, задумчивость, тревога, лица у всех вытянулись, на них появились отчаяние и морщины — следы прожитых лет и пережитых трудностей, а вместе с ними и более печальные признаки, указывающие на умственную неполноценность и начинающееся помешательство; что в восьми городах день и ночь работают фабрики, и все же до сих пор не удалось удовлетворить спрос на головоломку…"

Марк Твен «Американский претендент»




Политическая карикатура о поиске кандидата в президенты США
от республиканской партии в 1880 году

Но оказывается, что в задаче, за решение которой Ллойд предложил фантастическую призовую сумму, нет решения. Головоломку не получится собрать, у неё просто нет решения. Эта задача из области так называемых нерешаемых. Головоломка «Пятнашки» имеет решение, если число пар чисел, в которых большее число предшествует меньшему, четное. А так как по заданию надо поменять только одну пару (15 и 14), то так называемый параметр беспорядка делает задачу в таком расположении фишек нерешаемой. Ллойд знал об этом с самого начала, но общественность узнала этот важный момент значительно позже, когда ажиотаж на игру сошёл на нет, а хитрец Сэм Ллойд вошёл в историю и прилично подзаработал.

В процессе поиска решения для задачи по перестановке фишек 14 и 15 были разработаны другие задачи. И сейчас они так же актуальны и непросты как и почти полтора века назад.

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

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

Можно показать, что ровно половину из всех возможных 20 922 789 888 000 начальных положений пятнашек невозможно привести к собранному виду: пусть квадратик с числом i расположен до (если считать слева направо и сверху вниз) k квадратиков с числами меньшими i. Будем считать ni = k, то есть если после костяшки с i-м числом нет чисел, меньших i, то k = 0. Также введем число e — номер ряда пустой клетки (считая с единицы).

Если сумма является нечётной, то решения головоломки не существует.

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

Если допустить поворот коробки на 90 градусов, при котором изображения цифр окажутся лежащими на боку, то можно перевести неразрешимые комбинации в разрешимые (и наоборот). Таким образом, если вместо цифр на костяшки нанести точки и не фиксировать положение коробки, то неразрешимых комбинаций вообще не окажется.