Игра в 15, пятнашки, такен — популярная перестановочная головоломка, придуманная в 1878 году Ноем Чепмэном. Головоломка представляет собой набор из 15 одинаковых квадратных костяшек с нанесёнными на них числами, лежащих в квадратной коробке. Длина стороны коробки в четыре раза больше длины стороны костяшки, поэтому в коробке остаётся незаполненным одно квадратное поле. Цель игры — упорядочить костяшки по возрастанию номеров, перемещая их внутри коробки, желательно сделав как можно меньше перемещений.
История
Авторство С 1891 года до самой смерти Сэмюэл Лойд утверждал, что изобрёл головоломку именно он, и долгое время считалось, что это действительно так. Однако существуют доказательства того, что он не был причастен ни к созданию «пятнашек», ни к вариации с переставленными фишками 14 и 15. Пик популярности головоломки в США пришёлся на первую половину 1880 года; при этом не было обнаружено никаких упоминаний Сэма Лойда в связи с «пятнашками» вплоть до января 1891 года. В частности, The New York Times дважды публиковала материалы о головоломке, 22 марта 1880 года и 11 июня 1880 года, ни разу не упомянув при этом Лойда, несмотря на то что Лойд жил в Нью-Йорке.
Настоящим изобретателем головоломки был Ной Палмер Чепмэн, почтмейстер из Канастоты, который ещё в 1874 году показывал друзьям головоломку, состоящую из шестнадцати пронумерованных квадратиков, которые надо было сложить в ряды по четыре штуки так, чтобы сумма чисел в каждом ряду была равна 34.
Сын Ноя Чепмэна, Фрэнк Чепмэн, привёз доработанные головоломки в Сиракузы (штат Нью-Йорк) и передал их Анне и Джеймсу Бельден (Anna and James Belden). Они, в свою очередь, забрали головоломку в , где были сделаны копии головоломки; одна из этих копий не известным в точности путём попала в Хартфорд, где слушатели начали делать грубые копии головоломки. К 1879 году головоломка уже продавалась не только в Хартфорде, но и в Бостоне. Тогда о «пятнашках» узнал художник по дереву Маттиас Райс (Matthias J. Rice). В декабре 1879 года Маттиас Райс начал в Бостоне бизнес по производству новой головоломки под названием «Драгоценная головоломка» ().
В начале 1880 года некий Чарльз Певи, дантист из Вустера, привлёк внимание общественности, предложив денежное вознаграждение за решение задачи собирания головоломки, что добавило популярности новой забаве. Весной того же года игра достигла Европы.
21 февраля 1880 года Ной Чепмэн попытался оформить патент на своё изобретение под наименованием «Block Solitaire Puzzle» («Головоломка—пасьянс с блоками»), однако заявка на патент была отклонена; не сохранилось записей, объясняющих, почему это произошло. По-видимому, это было вызвано тем, что, по мнению патентного инспектора Бурке, новая заявка мало отличалась от патента «Хитрые блоки», «Puzzle-Blocks», выданного Эрнесту У. Кинси (Ernest U. Kinsey) более чем за год до того, как Ной Чепмэн подал свою заявку.
Распространение
В США 6 января 1880 года в газете появилось объявление о головоломке под названием Boss Puzzle. 12 января Boston Transcript упомянула несколько версий других производителей, включая Gem Puzzle, Solitaire, Fifteen и Number Puzzle. 19 января в той же газете была анонсирована головоломка под названием The New Puzzle; на следующий же день Worcester Gazette разместила объявление о головоломке The Boss Puzzle. Популярность головоломки стремительно росла, и предприниматели уже начали её производство и продажу.
В промежуток времени с 26 по 30 января Boston Evening Transcript опубликовала объявление Маттиаса Райса, раздосадованного появлением копий головоломки. В объявлении говорилось:
В феврале 1880 года в разных газетах начали появляться подробные статьи, посвящённые головоломке. Ряд журналов национального масштаба, включая , Illustrated Newspaper, Harper’s Weekly, Scientific American, , в течение нескольких недель публиковали объявления о головоломке. Новости о головоломке распространялись в другие города. К началу марта многие производители выпускали версии головоломки под разными названиями.
12 февраля газета опубликовала поэму о головоломке, за которой последовал ряд произведений в стихотворной форме в других газетах. 17 февраля в газете была опубликована статья о влиянии головоломки на общество. 20 февраля в нью-йоркском журнале Ontario County Journal появилась заметка следующего содержания:
17 марта 1880 года газета опубликовала статью, которая описывала «начало безумия» в Бостоне три месяца тому назад (в декабре 1879).
На основании газетных объявлений и статей авторы книги The 15 Puzzle Слокум и Зонневельд делают вывод, что в большинстве городов «безумие» длилось один-два месяца; впрочем, во многих городах головоломка становилась популярной до появления публикаций в местных газетах и оставалась популярной даже тогда, когда публикации прекращались.
За пределами США В марте 1880 года головоломка начала распространяться за пределами США. До конца марта она достигла Канады и Франции. В течение апреля «безумие» достигло Англии, Германии, Латвии, Австрии, Эстонии, Норвегии, Швеции, России, Финляндии, в мае — Новой Зеландии, Нидерландов, Италии, Мексики, Дании, Австралии.
В России 25 апреля 1880 года газета на немецком языке разместила объявление «Neues Spiel — Das Spiel der Funfzehn» («Новая игра — Игра в 15»).
Задачи
The Gem Puzzle В головоломке The Gem Puzzle, которую в 1879 году производил и продавал Матиас Райс, игрок высыпал плитки из коробочки и случайным образом укладывал их обратно, после чего пытался восстановить упорядоченную конфигурацию:
В этой версии задача оказывалась неразрешимой ровно в половине случаев.
Головоломка 14-15 В другой версии все плитки, за исключением 14 и 15, изначально находятся на своих местах; задача состоит в том, чтобы поменять местами неправильно стоящие плитки 14 и 15. Эта задача неразрешима; тем не менее, в этом случае можно упорядочить плитки с пустой ячейкой в верхнем левом углу либо выстроить фишки столбцами.
Современные модификации Выпущено множество вариантов головоломки. В некоторых вариантах вместо упорядочивания чисел ставится цель восстановить некоторое изображение. Вместо чисел могут использоваться буквы; присутствие хотя бы двух одинаковых букв может сделать решение головоломки нетривиальной задачей.
Магический квадрат
Одна из задач — переставить плитки таким образом, чтобы сумма чисел в каждом ряду (горизонтали, вертикали или большой диагонали) была равна одному и тому же числу; при этом числовое значение пустой ячейки считается равным нулюSam Loyd; Martin Gardner: Mathematical puzzles of Sam Loyd. Dover Pubs., New York 1959, pp. 19 und 20. Google books. При этом магическая сумма равна 30. Требуется по меньшей мере 35 ходов, чтобы получить магический квадрат из начального расположения, и существует лишь один магический квадрат, достижимый в 35 ходов.
Математическое описание Можно показать, что ровно половину из всех возможных (=16!) начальных положений пятнашек невозможно привести к собранному виду. Пусть плитка с числом расположена до (если считать слева направо и сверху вниз) плиток с числами, меньшими ; тогда обозначим . В частности, если после плитки с числом нет плиток с числами, меньшими , то . Также введём число — номер ряда пустой клетки (считая с 1). Если сумма
(то есть сумма числа пар костяшек, в которых костяшка с большим номером идёт перед костяшкой с меньшим номером, и номера ряда пустой клетки) нечётна, то решения головоломки не существует.
Если допустить поворот коробки на 90 градусов, при котором изображения цифр окажутся лежащими на боку, то можно перевести неразрешимые комбинации в разрешимые (и наоборот). Таким образом, если вместо цифр на костяшки нанести точки и не фиксировать положение коробки, то неразрешимых комбинаций вообще не окажется.
Оптимальное решение Для обобщённых пятнашек (с бо́льшим, чем 15, количеством костяшек) задача поиска кратчайшего решения для заданной конфигурации является NP-полной.
Любую из разрешимых конфигураций «классической» головоломки можно перевести в начальную не более чем за 80 ходов, если под ходом понимать перемещение одной плитки, или не более чем за 43 хода, если под ходом понимать одновременное перемещение сплошного ряда из не более чем трёх плиток. Только 17 из всех разрешимых конфигураций не могут быть решены менее чем за 80 ходов, то есть требуют 80 перемещений отдельных плиток для решения; только 16 разрешимых конфигураций требуют 43 перемещений сплошных рядов плиток.
В 1995 году было показано, что любая конфигурация головоломки может быть решена не более чем за 219 одиночных ходов, то есть была получена верхняя граница в 219 ходов для длины оптимального решения произвольной конфигурации. В 1996 году была найдена конфигурация, которая не может быть решена меньше чем за 112 перемещений плиток. В 2000 году верхняя граница была улучшена до 210 ходов; в 2011 году для «числа Бога» головоломки были получены нижняя граница в 152 хода и верхняя граница в 208 ходов.
n2 - 1 В 2023 году было показано, что среднее оптимальное решение обобщенной версии головоломки требует одиночных ходов, а «число Бога» оценивается .
Текущие результаты В таблице сведены данные для ряда обобщений «пятнашек». Когда точный результат неизвестен, приводятся лучшие известные оценки снизу и сверху в форме . Размер Целевая конфигурация Число решаемыхконфигураций «Длинные»ходыВ столбце указано, считается ли за один ход одновременное перемещение нескольких плиток, образующих сплошной вертикальный или горизонтальный ряд «Число Бога»Число ходов, за которое головоломку можно решить из самого трудного положения (требующего больше всего ходов) Число«антиподов»«Антиподы» — конфигурации головоломки, требующие наибольшего числа ходов для решения пустая ячейка в углу 12 нет 6 1 пустая ячейка в углу 360 нет 21 1 пустая ячейка в углу нет 36 1 пустая ячейка в углу нет 55 2 пустая ячейка в углу нет 80 2 пустая ячейка в углу нет 108 пустая ячейка в углу нет 140 пустая ячейка в углу нет 31 2 да 24 пустая ячейка в углу нет 53 18 пустая ячейка в углу нет 84 пустая ячейка в центре нет 84 пустая ячейка в углу нет 80 17 да 43 16 пустая ячейка в углу 7,7556 нет 152 — 208
Использование пятнашек в информатике «Пятнашки» разных размеров с 1960-х годов регулярно используются в исследованиях в области ИИ; в частности, на них испытываются и сравниваются алгоритмы поиска в пространстве состояний с разными эвристическими функциями и другими оптимизациями, влияющими на число посещённых в процессе поиска конфигураций головоломки (вершин графа). В исследованиях так или иначе использовались головоломки размеров , , , , , .
Можно перечислить основные причины выбора пятнашек в качестве «испытательного стенда» для алгоритмов поиска: пространство состояний классических пятнашек является доступным для анализа, но всё же достаточно большим, чтобы представлять интерес и использовать и сравнивать разнообразные эвристики; не известен ни один алгоритм, находящий кратчайшее решение для обобщённых пятнашек за разумное время; сама задача поиска кратчайшего решения для пятнашек проста для понимания и программного манипулирования; головоломка поддаётся описанию с помощью небольшого и чётко определённого набора простых правил; для моделирования головоломки не требуется передачи семантических тонкостей, присущих более сложным предметным областям; задачи с пятнашками — удачные представители класса проблем, в которых требуется найти кратчайший путь между двумя заданными вершинами неориентированного конечного графа; размер графа поиска зависит от размера головоломки экспоненциально, хотя любое состояние можно описать с затратой (2) памяти; одна и та же эвристическая функция может применяться ко всем состояниям, так как все состояния описываются одинаково; в реальных применениях разные состояния могут иметь разные описания, что требует введения нескольких эвристик; использование в исследованиях игр и головоломок не порождает финансовых или этических проблем.
Эвристический поиск