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

15 головоломки (также называемая Драгоценный камень головоломкой , Boss головоломка , игры пятнадцать , Мистик площади и многих других) является скользящей головоломкой , имеющей 15 квадратных плиток пронумерованы 1-15 в кадре , который является 4 плитки высоты и шириной 4 плитки, оставляя один незанятый положение плитки. Плитки в одной строке или столбце открытой позиции можно перемещать, сдвигая их по горизонтали или вертикали соответственно. Цель головоломки - расположить плитки в порядке номеров.

Названная по количеству плиток в кадре, головоломка из 15 также может называться головоломкой из 16, ссылаясь на ее общую вместимость плитки. Подобные названия используются для вариантов пазла 15 разного размера, например пазла 8 , у которого 8 плиток в рамке 3 × 3.

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

Математика

Разрешимость

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

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

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

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

Уилсон (1974) изучал обобщение головоломки 15 на произвольные конечные графы , исходная задача - случай сеточного графа 4 × 4 . В задаче есть несколько вырожденных случаев, когда ответ либо тривиален, либо представляет собой простую комбинацию ответов на одну и ту же задачу на некоторых подграфах. А именно, для путей и многоугольников головоломка не имеет свободы; если граф отключен , актуальна только связная компонента вершины с «пустым пространством»; и если есть вершина сочленения, задача сводится к одной и той же головоломке на каждом из двусвязныхкомпоненты этой вершины. Исключая эти случаи, Уилсон показал, что кроме одного исключительного графа на 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 . Копии улучшенной Fifteen Puzzle добрались до Сиракуз, штат Нью-Йорк , через сына Нойса, Фрэнка, а оттуда, через различные связи, в Уотч-Хилл, Род-Айленд , и, наконец, в Хартфорд (Коннектикут), где студенты Американская школа для глухонемых начали производство головоломки и, в декабре 1879 года , продавая их как локально , так и в Бостоне, Массачусетс. Показан один из них, Матиас Райс, который руководил модным деревообрабатывающим бизнесом в Бостоне, начал производство пазла где-то в декабре 1879 года и убедил продавца галантерейных товаров "Yankee Notions" продавать их под названием "Gem Puzzle". В конце января 1880 года доктор Чарльз Певи, дантист из Вустера, штат Массачусетс , привлек некоторое внимание, предложив денежное вознаграждение за решение «Загадки пятнадцати». [16]

В 1880 году эта игра стала повальным увлечением в США. [17]

21 февраля 1880 года Нойес Чепмен подал заявку на патент на свой «Блок-пасьянс». Однако этот патент был отклонен, вероятно, потому, что он недостаточно отличался от патента «Puzzle-Blocks» от 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 головоломок. [20] Он был рассчитан на то, чтобы решить ее за 25 секунд; Фишер продемонстрировал это 8 ноября 1972 года в «Вечернем шоу» с Джонни Карсоном в главной роли . [21] [22]

Смотрите также

  • Комбинированные пазлы
  • 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. ^ А. Брюнггер, А. Марцетта, К. Фукуда и Дж. Нивергельт, Стенд параллельного поиска ZRAM и его приложения , Annals of Operations Research 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. ^ Билер, Роберт. «Головоломка пятнадцати: мотивирующий пример для меняющейся группы» (PDF) . faculty.etsu.edu/ . Государственный университет Восточного Теннесси . Проверено 26 декабря 2020 года .
  16. ^ a b c d Головоломка 15 , Джерри Слокам и Дик Сонневельд, 2006. ISBN 1-890980-15-3 
  17. ↑ Slocum & Singmaster (2009 , стр. 15)
  18. Перейти ↑ Cyclopedia of Puzzles , p. 235
  19. Перейти ↑ Barry R. Clarke, Puzzles for Pleasure , pp. 10-12, Cambridge University Press, 1994 ISBN 0-521-46634-2 . 
  20. ^ Клиффорд А. Пиковер, Математическая книга: от Пифагора до 57-го измерения, 250 вех в истории математики , стр. 262, Sterling Publishing, 2009 ISBN 1402757964 . 
  21. ^ "Бобби Фишер решает 15 головоломок за 17 секунд на Carson Tonight Show - 11.08.1972" , The Tonight Show , 8 ноября 1972 года, Johnny Carson Productions, вышедший на пенсию 1 августа 2021 года.
  22. ↑ Адам Спенсер, Большая книга чисел Адама Спенсера: все, что вы хотели знать о числах от 1 до 100 , стр. 58, Brio Books, 2014 ISBN 192113433X . 

использованная литература

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

внешняя ссылка

  • История пазла 15
  • Пятнадцать Головоломок
  • Максимальное количество ходов, необходимых для m X n обобщения головоломки из 15
  • Оптимальный решатель из 15 головоломок с загрузкой (от Герберта Коциембы)
Получено с https://en.wikipedia.org/w/index.php?title=15_puzzle&oldid=1058438932 .
Contribute a better translation