Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
"Magic 15" перенаправляется сюда. Для пронумерованной сетки, где сумма каждой строки и столбца равна 15, см. Магический квадрат .
Чтобы решить загадку, числа необходимо переставить по порядку.

15 головоломки (также называется Gem Puzzle , Boss головоломка , игра Пятнадцать , Mystic Square и многих других) является скользящей головоломкой , которая состоит из рамы , пронумерованные квадратных плиток в случайном порядке с одной плитки отсутствует. Пазл также существует в других размерах, особенно пазл меньшего размера 8 . Если размер 3 × 3 плитки, головоломка называется головоломкой 8 или 9, а если плитки 4 × 4, головоломка называется головоломкой 15 или 16, названной, соответственно, по количеству плиток и количеству пробелы. Цель головоломки - расположить плитки по порядку, выполняя скользящие движения, которые используют пустое пространство.

Задача n - классическая задача моделирования алгоритмов с использованием эвристики . Обычно используемые эвристики для решения этой проблемы включают подсчет количества потерянных плиток и нахождение суммы расстояний такси между каждым блоком и его положением в конфигурации цели. [1] Обратите внимание, что оба варианта допустимы , т.е. они никогда не переоценивают количество оставшихся ходов, что обеспечивает оптимальность для определенных алгоритмов поиска, таких как A * . [1]

Математика [ править ]

Разрешимость [ править ]

Решенная головоломка из 15

Johnson & Story (1879) использовали аргумент о четности, чтобы показать, что половину начальных позиций n головоломки невозможно решить независимо от того, сколько ходов сделано. Это делается путем рассмотрения функции конфигурации плитки, которая инвариантна при любом допустимом перемещении, а затем ее использования для разделения пространства всех возможных помеченных состояний на два класса эквивалентности достижимых и недостижимых состояний.

Инвариант - это четность перестановки всех 16 квадратов плюс четность расстояния такси (количество строк плюс количество столбцов) до пустого квадрата из правого нижнего угла. Это инвариант, потому что каждый ход изменяет как четность перестановки, так и четность расстояния такси. В частности, если пустой квадрат находится в правом нижнем углу, головоломка разрешима тогда и только тогда, когда перестановка оставшихся частей четная.

Джонсон и история (1879) также показала , что обратное имеет место на досках размера м × п при условии т и п являются по меньшей мере , 2: все четными перестановками являются разрешимыми. Это просто, но немного запутано доказать индукцией по m и n, начиная с m = n = 2. Archer (1999) дал еще одно доказательство, основанное на определении классов эквивалентности через гамильтонова пути .

Уилсон (1974) изучал обобщение головоломки 15 на произвольные конечные графы , исходная задача - случай сеточного графа 4x4 . В задаче есть несколько вырожденных случаев, когда ответ либо тривиален, либо является простой комбинацией ответов на одну и ту же задачу на некоторых подграфах. А именно, для путей и многоугольников головоломка не имеет свободы; если граф несвязный , актуальна только связная компонента вершины с «пустым пространством»; и если есть вершина сочленения, задача сводится к одной и той же головоломке на каждом из двусвязныхкомпоненты этой вершины. Исключая эти случаи, Уилсон показал, что кроме одного исключительного графа на 7 вершинах, можно получить все перестановки, если только граф не двудольный , и в этом случае могут быть получены ровно четные перестановки. Исключительный граф - это правильный шестиугольник с одной диагональю и добавленной вершиной в центре; Только1/6 его перестановок могут быть достигнуты.

Для больших версий n головоломки найти решение легко, но проблема поиска кратчайшего решения NP-трудна . Также NP-сложно аппроксимировать наименьшее количество слайдов в пределах аддитивной константы, но есть приближение полиномиального времени с постоянным множителем. [2] [3] Для головоломки 15 длина оптимальных решений варьируется от 0 до 80 ходов с одной плиткой (есть 17 конфигураций, требующих 80 ходов) [4] [5] или 43 хода с несколькими плитками; [6] головоломку 8 всегда можно решить не более чем за 31 ход с одной плиткой или за 24 хода с несколькими плитками (целочисленная последовательность A087725). Метрика с несколькими плитками учитывает последующие перемещения пустой плитки в том же направлении как одно. [6]

Количество возможных позиций 24 головоломки равно 25!/2 ≈ 7,76 × 10 24, что слишком много для вычисления числа Бога . В 2011 году были установлены нижние границы для 152 ходов с одной плиткой или 41 хода с одной плиткой, а также верхние границы для 208 ходов с одной плиткой или 109 перемещений с одной плиткой. [7] [8] [9] [10] В 2016 году верхняя граница была улучшена до 205 одиночных ходов. [11]

Преобразования пятнадцати головоломок образуют группоид (не группу, так как не все ходы могут быть составлены); [12] [13] [14] этот группоид действует на конфигурации.

Теория групп [ править ]

Поскольку комбинации головоломки 15 могут быть созданы с помощью 3-х циклов , можно доказать, что головоломка 15 может быть представлена чередующейся группой . [15] Фактически, любая скользящая головоломка с квадратными плитками одинакового размера может быть представлена ​​символом .

Альтернативное доказательство [ править ]

С другой стороны, мы можем рассматривать инвариант как сумму четности числа инверсий в текущем порядке 15 пронумерованных частей и четности разницы в номере строки пустого квадрата из числа номер строки последней строки. (Назовем это расстоянием между строками от последней строки.) Это инвариант, потому что каждое перемещение столбца, когда мы перемещаем кусок внутри того же столбца, изменяет как четность количества инверсий (изменяя количество инверсий на ± 1). , ± 3) и четность расстояния между строками от последней строки (изменение расстояния между строками на ± 1); и каждый ход ряда, когда мы перемещаем фигуру в пределах одного ряда, не меняет ни одну из двух четностей. Теперь, если мы посмотрим на решенное состояние головоломки, эта сумма четная. Следовательно, легко доказать с помощьюиндукция, что любое состояние головоломки, для которого указанная сумма нечетная, не может быть разрешимо. В частности, если пустой квадрат находится в правом нижнем углу (даже где-нибудь в последней строке), тогда головоломка разрешима тогда и только тогда, когда количество перевертышей пронумерованных частей четное.

История [ править ]

Неразрешимая головоломка Сэма Лойда 15, с заменой плиток 14 и 15. Эта головоломка не разрешима, так как для ее перевода в решенное состояние потребуется изменить инвариант.
Политическая карикатура США о поисках кандидата в президенты от республиканцев в 1880 году

Головоломка была «изобретена» Нойесом Палмером Чепменом, [16] почтмейстером из Канастоты, штат Нью-Йорк , который, как говорят, показал друзьям еще в 1874 году загадку-предшественницу, состоящую из 16 пронумерованных блоков, которые должны были быть собраны вместе. ряды по четыре, в каждом по 34 . Копии улучшенной «Пятнадцати пазлов» добрались до Сиракуз, штат Нью-Йорк , через сына Нойеса, Фрэнка, а оттуда, через различные связи, в Уотч-Хилл, Род-Айленд , и, наконец, в Хартфорд (Коннектикут), где студенты Американская школа для глухонемых начали производство головоломки и, в декабре 1879 года , продавая их как локально , так и в Бостоне, Массачусетс. Показан один из них, Матиас Райс, который руководил модным деревообрабатывающим бизнесом в Бостоне, начал производство пазла где-то в декабре 1879 года и убедил дилера галантерейных товаров "Yankee Notions" продавать их под названием "Gem Puzzle". В конце января 1880 года доктор Чарльз Певи, дантист из Вустера, штат Массачусетс , привлек некоторое внимание, предложив денежное вознаграждение за решение «Загадки пятнадцати». [16]

Игра стала повальным увлечением в США в феврале 1880 года, в Канаде в марте, в Европе в апреле, но к июлю это увлечение рассеялось. Судя по всему, загадка появилась в Японии только в 1889 году [17].

21 февраля 1880 г. Нойес Чепмен подал заявку на патент на свой «Блок-пасьянс». Однако этот патент был отклонен, вероятно, потому, что он недостаточно отличался от патента «Блоки-головоломки» от 20 августа 1878 г. (US 207124). предоставлено Эрнесту У. Кинси. [16]

Сэм Лойд [ править ]

Иллюстрация Сэма Лойда 1914 года о неразрешимой вариации

Сэм Лойд утверждал с 1891 года до своей смерти в 1911 году, что он изобрел головоломку, например, написал в « Циклопедии головоломок» (опубликованной в 1914 году): «Пожилые жители страны головоломок помнят, как в начале семидесятых я сводил с ума весь мир из-за маленькая коробочка с подвижными частями, известная как «Головоломка 14-15» ». [18] [ неудачная проверка ] Однако Лойд не имел ничего общего с изобретением или первоначальной популярностью головоломки, и в любом случае повальное увлечение пришло в 1880 году, а не в начале 1870-х годов. Первая статья Лойда о загадке была опубликована в 1886 году, и только в 1891 году он впервые заявил, что является изобретателем. [16] [19]

Некоторый интерес позже подогрел Лойд, предложивший приз в размере 1000 долларов любому, кто сможет предложить решение для достижения определенной комбинации, указанной Лойдом, а именно перестановки 14 и 15, которую Лойд назвал головоломкой 14-15 . [1] Это было невозможно, как было показано более десяти лет назад Johnson & Story (1879) , так как требовалось преобразование четной перестановки в нечетную.

Разное [ править ]

Минус Куб , изготовленный в СССР , является 3D - головоломка с аналогичными операциями в 15 головоломки.

Бобби Фишер был экспертом в решении головоломки 15. Он был рассчитан на то, чтобы решить ее за 25 секунд; Фишер продемонстрировал это 8 ноября 1972 года в «Вечернем шоу» с Джонни Карсоном в главной роли . [ необходима цитата ]

См. Также [ править ]

  • Комбинированные пазлы
  • Jeu de taquin , операция над перекосом картин Юнга, похожая на ходы головоломки 15
  • Клоцкий
  • Механические пазлы
  • Проблемы с движением гальки
  • Кубик Рубика
  • Проблема трех чашек

Примечания [ править ]

  1. ^ a b c Корф, Р. Э. (2000), «Последние достижения в разработке и анализе допустимых эвристических функций» (PDF) , в Choueiry, BY; Уолш, Т. (ред.), Абстракция, переформулирование и приближение (PDF) , SARA 2000. Конспект лекций по информатике, том. 1864, Springer, Berlin, Heidelberg, стр. 45–55, DOI : 10.1007 / 3-540-44914-0_3 , ISBN 978-3-540-67839-7, дата обращения 26.04.2010
  2. ^ Даниэль Ратнер, Манфред К. Вармут. Найти кратчайшее решение для расширения N × N задачи 15-PUZZLE невозможно . Национальная конференция по искусственному интеллекту, 1986.
  3. ^ Ратнер, Дэниел; Вармут, Манфред (1990). «(N 2 −1) -задача и связанные с ней проблемы перемещения» . Журнал символических вычислений . 10 (2): 111–137. DOI : 10.1016 / S0747-7171 (08) 80001-6 .
  4. ^ Ричард Э. Корф, Дисковый неявный поиск в графах с линейным временем , Журнал ACM, том 55, выпуск 6 (декабрь 2008 г.), статья 26, стр. 29-30. «Для головоломки Fifteen 4 × 4 существует 17 различных состояний на глубине 80 ходов от начального состояния с пробелом в углу, в то время как для головоломки Fifteen 2 × 8 существует уникальное состояние при максимальном состоянии 140. переходит из исходного состояния ".
  5. ^ А. Брюнгер, А. Marzetta, К. Фукуда и Дж Nievergelt, параллельный поиск скамейка ZRAM и его применения , Анналы исследования операций 90 (1999), стр. 45-63.
    : «Гассер нашел 9 позиций, требующих 80 ходов ... Теперь мы доказали, что самые сложные позиции с 15 головоломками требуют 80 ходов. Мы также обнаружили две ранее неизвестные позиции, требующие ровно 80 ходов».
  6. ^ a b «Головоломку пятнадцати можно решить за 43 хода» . Домен куба Форум
  7. ^ "24 головоломки, новая нижняя граница: 152" . Домен куба Форум
  8. ^ "m × n головоломка (текущее состояние)" . Уголок головоломки раздвижной плитки.
  9. ^ "208s для 5x5" . Домен кубического форума.
  10. ^ «5x5 можно решить за 109 MTM» . Домен кубического форума.
  11. ^ «Раздвижную головоломку 5x5 можно решить за 205 ходов» . Домен кубического форума.
  12. ^ Джим Белк (2008) Головоломки, группы и группоиды , семинар по всему
  13. ^ 15-головоломка группоид (1) , нескончаемая книга
  14. ^ 15-головоломка группоид (2) , нескончаемая книга
  15. ^ Beeler, Роберт. «Загадка пятнадцати: мотивирующий пример для меняющейся группы» (PDF) . faculty.etsu.edu/ . Государственный университет Восточного Теннесси . Проверено 26 декабря 2020 года .
  16. ^ a b c d Головоломка 15 , Джерри Слокам и Дик Сонневельд, 2006. ISBN 1-890980-15-3 
  17. ↑ Куб: полное руководство по самой продаваемой головоломке в мире
  18. ^ Cyclopedia пазлов , с. 235
  19. ^ Barry R. Clarke, головоломки для удовольствия , pp.10-12, Cambridge University Press, 1994 ISBN 0-521-46634-2 . 

Ссылки [ править ]

  • Арчер, Аарон Ф. (1999), "Современное лечение 15 головоломки", Американский Математический Месячный , 106 (9): 793-799, CiteSeerX  10.1.1.19.1491 , DOI : 10,2307 / 2589612 , ISSN  0002-9890 , JSTOR  2589612 , MR  1732661
  • Джонсон, Wm. Вулси; История, William E. (1879), "Записки о "15" Головоломка", Американский журнал математики , 2 (4): 397-404, DOI : 10,2307 / 2369492 , ISSN  0002-9327 , JSTOR  2369492
  • Эдвард Каснер и Джеймс Ньюман (1940) Математика и воображение , стр 177–80, Саймон и Шустер .
  • Уилсон, Ричард М. (1974), «Графические головоломки, гомотопия и переменная группа», Журнал комбинаторной теории, серия B , 16 : 86–96, DOI : 10.1016 / 0095-8956 (74) 90098-7 , ISSN  0095-8956 , Руководство пользователя  0332555

Внешние ссылки [ править ]

  • История пазла 15
  • Пятнадцать Головоломок
  • Максимальное количество ходов, необходимое для m X n обобщения головоломки из 15
  • Оптимальный решатель из 15 головоломок с загрузкой (от Герберта Коциембы)