Войти
Чтобы решить головоломку, числа должны быть переставлены в порядок Загадка 15 (также называемая Gem Puzzle, Boss Puzzle, Game of Fifteen, Mystic Square и многие другие) - это скользящая головоломка который состоит из рамки пронумерованных квадратных плиток в случайном порядке с одной пропущенной плиткой. Головоломка также существует в других размерах, особенно меньшая 8 головоломка . Если размер 3 × 3 плитки, головоломка называется головоломкой 8 или 9, а если плитки 4 × 4, головоломка называется головоломкой 15 или 16, названной, соответственно, по количеству плиток и количеству пробелы. Цель головоломки - расположить плитки по порядку, выполняя скользящие движения, которые используют пустое пространство.
n-головоломка - это классическая задача для моделирования алгоритмов с использованием эвристики. Обычно используемые эвристики для этой проблемы включают подсчет количества потерянных плиток и нахождение суммы расстояний такси между каждым блоком и его положением в конфигурации цели. Обратите внимание, что оба являются допустимыми, т.е. они никогда не переоценивают количество оставшихся ходов, что обеспечивает оптимальность для некоторых алгоритмов поиска, таких как A*.
Решенная головоломка Johnson Story (1879) использовал аргумент четность, чтобы показать, что половину начальных позиций n головоломки невозможно решить, независимо от того, сколько ходов сделано. Это делается путем рассмотрения функции конфигурации плитки, которая инвариантна при любом допустимом перемещении, а затем с ее использованием для разделения пространства всех возможных помеченных состояний на два класса эквивалентности достижимых и недостижимые состояния.
Инвариант - это четность перестановки всех 16 квадратов плюс четность расстояния такси (количество строк плюс количество столбцов) пустого квадрата. из правого нижнего угла. Это инвариант, потому что каждый ход изменяет как четность перестановки, так и четность расстояния такси. В частности, если пустой квадрат находится в правом нижнем углу, головоломка разрешима тогда и только тогда, когда перестановка оставшихся частей четная.
Johnson Story (1879) также показали, что обратное верно для досок размера m × n при условии, что оба m и n равны как минимум 2: все четные перестановки разрешимы. Это просто, но немного запутано доказать индукцией по m и n, начиная с m = n = 2. Арчер (1999) дал другое доказательство, основанное на определении классов эквивалентности через гамильтонов путь.
Уилсон (1974) изучил аналог головоломки 15 на произвольные конечные двусвязные графы. Он показал, что, за исключением многоугольников и одного исключительного графа на 7 вершинах, можно получить все перестановки, если граф не является двудольным, и в этом случае могут быть получены ровно четные перестановки. Исключительный граф - это правильный шестиугольник с одной диагональю и добавленной вершиной в центре; можно получить только 1/6 его перестановок.
Для больших версий n головоломки найти решение легко, но проблема поиска кратчайшего решения NP-сложна. Также NP-сложно аппроксимировать наименьшее количество слайдов в пределах аддитивной константы, но есть приближение полиномиального времени с постоянным множителем. Для головоломки 15 длина оптимальных решений варьируется от 0 до 80 ходов с одной плиткой (есть 17 конфигураций, требующих 80 ходов) или 43 хода с несколькими плитками; головоломка 8 всегда может быть решена не более чем за 31 ход с одной плиткой или 24 хода с несколькими плитками (целочисленная последовательность A087725 ). Метрика с несколькими плитками учитывает последующие перемещения пустой плитки в том же направлении, что и один.
Количество возможных позиций головоломки из 24 составляет 25! / 2 ≈ 7,76 × 10, что слишком много для вычисления Число Бога. В 2011 году были установлены нижние границы для 152 ходов с одной плиткой или 41 хода с одной плиткой, а также верхние границы для 208 ходов с одной плиткой или 109 перемещений с одной плиткой. В 2016 году верхняя граница была улучшена до 205 одиночных ходов.
Преобразования пятнадцати головоломок образуют группоид (не группу, поскольку не все ходы могут быть составлены); этот группоид действует на конфигурации.
С другой стороны, мы можем рассматривать инвариант как сумму четности числа инверсий в текущем порядке 15 пронумерованных частей и четность разницы в номере строки пустого квадрата с номером строки последней строки. (Назовем это расстоянием между строками от последней строки.) Это инвариант, потому что каждое перемещение столбца, когда мы перемещаем кусок внутри того же столбца, изменяет как четность количества инверсий (изменяя количество инверсий на ± 1)., ± 3) и четность расстояния между строками от последней строки (изменение расстояния между строками на ± 1); и каждый ход ряда, когда мы перемещаем фигуру в пределах одного ряда, не меняет ни одну из двух четностей. Теперь, если мы посмотрим на решенное состояние головоломки, эта сумма четная. Следовательно, с помощью индукции легко доказать, что любое состояние головоломки, для которого указанная сумма нечетная, не может быть разрешимо. В частности, если пустой квадрат находится в правом нижнем углу (даже где-нибудь в последней строке), тогда головоломка разрешима тогда и только тогда, когда количество перевертышей пронумерованных частей четное.
Неразрешимая головоломка Сэма Лойда с заменой плиток 14 и 15. Эту загадку невозможно решить, так как для ее перевода в решенное состояние потребуется изменить инвариант. 
США Политическая карикатура о поиске кандидата в президенты от республиканцев в 1880 году Загадка была «изобретена» Нойесом Палмером Чепменом, почтмейстером в Канастота, Нью-Йорк, который, как говорят, показывал друзей еще в 1874 году., головоломка-предшественник, состоящая из 16 пронумерованных блоков, которые должны были быть собраны в ряды по четыре, каждый в сумме до 34. Копии улучшенной «Пятнадцатой головоломки» добрались до Сиракуз, штат Нью-Йорк, через сына Нойеса, Фрэнка, а оттуда, через различные связи, в Уотч-Хилл, Род-Айленд и, наконец, в Хартфорд (Коннектикут), где ученики Американской школы для глухих начали изготавливать пазл и к декабрю 1879 года продавать их как на местном уровне, так и в Бостоне., Массачусетс. Показан один из них, Матиас Райс, который руководил модным деревообрабатывающим бизнесом в Бостоне, начал производство пазла где-то в декабре 1879 года и убедил дилера галантерейных товаров "Yankee Notions" продавать их под названием "Gem Puzzle". В конце января 1880 года доктор Чарльз Певи, дантист из Вустера, штат Массачусетс, привлек некоторое внимание, предложив денежное вознаграждение за решение головоломки «Пятнадцать».
Игра стала безумной. в США в феврале 1880 года, в Канаде в марте, в Европе в апреле, но к июлю это увлечение рассеялось. Судя по всему, головоломка не была представлена в Японии до 1889 года.
21 февраля 1880 года Нойес Чепмен подал заявку на патент на свою «головоломку с блочным пасьянсом». Однако этот патент был отклонен, вероятно, потому, что это не так. существенно отличается от патента «Puzzle-Blocks» от 20 августа 1878 г. (US 207124), выданного Эрнесту У. Кинси.
Иллюстрация Сэма Лойда 1914 года неразрешимого варианта Сэм Лойд утверждал с 1891 года до своей смерти в 1911 году, что он изобрел головоломку, например, писал в «Циклопедии головоломок» (опубликованной в 1914 году): «Старые жители страны головоломок вспомнят, как в начале семидесятых годов я сводил с ума весь мир из-за маленькая коробочка с подвижными частями, известная как «Головоломка 14-15» ». Однако Лойд не имел ничего общего с изобретением или первоначальной популярностью головоломки, и в любом случае повальное увлечение имело место в 1880 году, а не в начале 1870-х годов. Первая статья Лойда о загадке была опубликована в 1886 году, и только в 1891 году он впервые заявил, что является изобретателем.
Некоторый интерес позже подогрел Лойд, предложивший приз в 1000 долларов каждому, кто сможет предложить решение. для достижения определенной комбинации, указанной Лойдом, а именно перестановки 14 и 15, которую Лойд назвал загадкой 14-15 . Это было невозможно, как было показано более десяти лет назад в Johnson Story (1879), поскольку требовалось преобразование четной перестановки в нечетную.
Минус-Куб, изготовленный в СССР, представляет собой головоломку 3D с аналогичными действиями, что и у 15 головоломка.
Бобби Фишер был экспертом в решении головоломки 15. Он был рассчитан на то, чтобы решить ее за 25 секунд; Фишер продемонстрировал это 8 ноября 1972 года на Вечернем шоу с Джонни Карсоном.
Некоторые браузерные игры вдохновлены механикой головоломок, например, «Непрерывность» или «Комнаты».
 | На Викискладе есть материалы, связанные с 15 головоломкой. |
