Русская Википедия:Игра в 15

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Шаблон:Другие значения

Файл:Пятнашки.jpg
Файл:15-puzzle-01.jpg
Головоломка-брелок

Шаблон:Другие значения слова Игра в 15Шаблон:SfnШаблон:Sfn[1], пятнашкиШаблон:Sfn[2], такенШаблон:Sfn[2][3] — популярная головоломка, придуманная в 1878 году Ноем Чепмэном. Головоломка представляет собой набор из 15 одинаковых квадратных костяшек с нанесёнными на них числами, лежащих в квадратной коробке. Длина стороны коробки в четыре раза больше длины стороны костяшки, поэтому в коробке остаётся незаполненным одно квадратное поле. Цель игры — упорядочить костяшки по возрастанию номеров, перемещая их внутри коробки, желательно сделав как можно меньше перемещений.

История

Авторство

С 1891 года до самой смерти Сэмюэл Лойд утверждал, что изобрёл головоломку именно он, и долгое время считалось, что это действительно так[4][5]. Однако существуют доказательства того, что он не был причастен ни к созданию «пятнашек», ни к вариации с переставленными фишками 14 и 15Шаблон:SfnШаблон:SfnШаблон:Sfn[5]. Пик популярности головоломки в США пришёлся на первую половину 1880 года; при этом не было обнаружено никаких упоминаний Сэма Лойда в связи с «пятнашками» вплоть до января 1891 годаШаблон:SfnШаблон:Sfn. В частности, The New York Times дважды публиковала материалы о головоломке, 22 марта 1880 года и 11 июня 1880 года, ни разу не упомянув при этом Лойда, несмотря на то что Лойд жил в Нью-ЙоркеШаблон:Sfn.

Настоящим изобретателем головоломки был Ной Палмер Чепмэн, почтмейстер из КанастотыШаблон:SfnШаблон:Sfn, который ещё в 1874 году показывал друзьям головоломку, состоящую из шестнадцати пронумерованных квадратиков, которые надо было сложить в ряды по четыре штуки так, чтобы сумма чисел в каждом ряду была равна 34Шаблон:Sfn.

Сын Ноя Чепмэна, Фрэнк Чепмэн, привёз доработанные головоломки в Сиракузы (штат Нью-Йорк) и передал их Анне и Джеймсу Бельден (Anna and James Belden)Шаблон:Sfn. Они, в свою очередь, забрали головоломку в Шаблон:Нп5, где были сделаны копии головоломкиШаблон:Sfn; одна из этих копий не известным в точности путём попала в ХартфордШаблон:Sfn, где слушатели Шаблон:Нп5 начали делать грубые копии головоломкиШаблон:Sfn. К 1879 году головоломка уже продавалась не только в Хартфорде, но и в Бостоне. Тогда о «пятнашках» узнал художник по дереву Маттиас Райс (Matthias J. Rice). В декабре 1879 года Маттиас Райс начал в Бостоне бизнес по производству новой головоломки под названием «Драгоценная головоломка» (Шаблон:Lang-en)Шаблон:SfnШаблон:Sfn[6].

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

21 февраля 1880 года Ной Чепмэн попытался оформить патент на своё изобретение под наименованием «Block Solitaire Puzzle» («Головоломка—пасьянс с блоками»)Шаблон:Sfn, однако заявка на патент была отклонена; не сохранилось записей, объясняющих, почему это произошлоШаблон:Sfn. По-видимому, это было вызвано тем, что, по мнению патентного инспектора Бурке, новая заявка мало отличалась от патента[7] «Хитрые блоки», «Puzzle-Blocks», выданного Эрнесту У. Кинси (Ernest U. Kinsey) более чем за год до того, как Ной Чепмэн подал свою заявкуШаблон:SfnШаблон:Sfn.

Распространение

В США

6 января 1880 года в газете Шаблон:Нп5 появилось объявление о головоломке под названием Boss Puzzle. 12 января Boston Transcript упомянула несколько версий других производителей, включая Gem Puzzle, Solitaire, Fifteen и Number Puzzle. 19 января в той же газете была анонсирована головоломка под названием The New Puzzle; на следующий же день Worcester Gazette разместила объявление о головоломке The Boss Puzzle. Популярность головоломки стремительно росла, и предприниматели уже начали её производство и продажуШаблон:Sfn.

В промежуток времени с 26 по 30 января Boston Evening Transcript опубликовала объявление Маттиаса Райса, раздосадованного появлением копий головоломки. В объявлении говорилосьШаблон:Sfn: Шаблон:Coquote

В феврале 1880 года в разных газетах начали появляться подробные статьи, посвящённые головоломкеШаблон:Sfn. Ряд журналов национального масштаба, включая Шаблон:Нп5, Illustrated Newspaper, Harper’s Weekly, Scientific American, Шаблон:Нп5, в течение нескольких недель публиковали объявления о головоломкеШаблон:Sfn. Новости о головоломке распространялись в другие города. К началу марта многие производители выпускали версии головоломки под разными названиямиШаблон:Sfn.

12 февраля газета Шаблон:Нп5 опубликовала поэму о головоломке, за которой последовал ряд произведений в стихотворной форме в других газетахШаблон:Sfn. 17 февраля в газете Шаблон:Нп5 была опубликована статья о влиянии головоломки на общество. 20 февраля в нью-йоркском журнале Ontario County Journal появилась заметка следующего содержанияШаблон:Sfn: Шаблон:Coquote

17 марта 1880 года газета Шаблон:Нп5 опубликовала статью, которая описывала «начало безумия» в Бостоне три месяца тому назад (в декабре 1879)Шаблон:Sfn.

На основании газетных объявлений и статей авторы книги The 15 Puzzle Слокум и Зонневельд делают вывод, что в большинстве городов «безумие» длилось один-два месяца; впрочем, во многих городах головоломка становилась популярной до появления публикаций в местных газетах и оставалась популярной даже тогда, когда публикации прекращалисьШаблон:Sfn.

За пределами США

В марте 1880 года головоломка начала распространяться за пределами США. До конца марта она достигла Канады и Франции. В течение апреля «безумие» достигло Англии, Германии, Латвии, Австрии, Эстонии, Норвегии, Швеции, России, Финляндии, в мае — Новой Зеландии, Нидерландов, Италии, Мексики, Дании, АвстралииШаблон:Sfn.

В России

25 апреля 1880 года газета Шаблон:Нп5 на немецком языке разместила объявление «Neues Spiel — Das Spiel der Funfzehn»Шаблон:Sfn («Новая игра — Игра в 15»).

Задачи

The Gem Puzzle

В головоломке The Gem Puzzle, которую в 1879 году производил и продавал Матиас Райс, игрок высыпал плитки из коробочки и случайным образом укладывал их обратно, после чего пытался восстановить упорядоченную конфигурацию[6]Шаблон:Sfn: Шаблон:Coquote

В этой версии задача оказывалась неразрешимой ровно в половине случаев.

Головоломка 14-15

В другой версии все плитки, за исключением 14 и 15, изначально находятся на своих местах; задача состоит в том, чтобы поменять местами неправильно стоящие плитки 14 и 15. Эта задача неразрешима; тем не менее, в этом случае можно упорядочить плитки с пустой ячейкой в верхнем левом углу либо выстроить фишки столбцамиШаблон:Sfn.

Современные модификации

Выпущено множество вариантов головоломки. В некоторых вариантах вместо упорядочивания чисел ставится цель восстановить некоторое изображение. Вместо чисел могут использоваться буквы; присутствие хотя бы двух одинаковых букв может сделать решение головоломки нетривиальной задачей.

Магический квадрат

Файл:15-puzzle magical.svg
Магический квадрат

Одна из задач — переставить плитки таким образом, чтобы сумма чисел в каждом ряду (горизонтали, вертикали или большой диагонали) была равна одному и тому же числу; при этом числовое значение пустой ячейки считается равным нулюШаблон:Sfn[8]. При этом магическая сумма равна 30. Требуется по меньшей мере 35 ходов, чтобы получить магический квадрат из начального расположения, и существует лишь один магический квадрат, достижимый в 35 ходов[9].

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

Можно показать, что ровно половину из всех возможных Шаблон:Число (=16!) начальных положений пятнашек невозможно привести к собранному виду. Пусть плитка с числом <math> i </math> расположена до (если считать слева направо и сверху вниз) <math> k </math> плиток с числами, меньшими <math> i </math>; тогда обозначим <math> n_i = k </math>. В частности, если после плитки с числом <math>i</math> нет плиток с числами, меньшими <math>i</math>, то <math> n_i = 0</math>. Также введём число <math>e</math> — номер ряда пустой клетки (считая с 1). Если сумма

Файл:15-puzzle-loyd.svg
Нерешаемая комбинация
<math>N = \sum_{i=1}^{15} n_i + e</math>

(то есть сумма числа пар костяшек, в которых костяшка с большим номером идёт перед костяшкой с меньшим номером, и номера ряда пустой клетки) нечётна, то решения головоломки не существует[10][1].

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

Оптимальное решение

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

Шаблон:Times

Любую из Шаблон:Num разрешимых конфигураций «классической» головоломки Шаблон:Times можно перевести в начальную не более чем за 80 ходов, если под ходом понимать перемещение одной плитки[13][14][9][15], или не более чем за 43 хода, если под ходом понимать одновременное перемещение сплошного ряда из не более чем трёх плиток[16]. Только 17 из всех разрешимых конфигураций не могут быть решены менее чем за 80 ходов, то есть требуют 80 перемещений отдельных плиток для решения[14][9][17]; только 16 разрешимых конфигураций требуют 43 перемещений сплошных рядов плиток[16].

Шаблон:Times

В 1995 году было показано, что любая конфигурация головоломки Шаблон:Times может быть решена не более чем за 219 одиночных ходов[18], то есть была получена верхняя граница в 219 ходов для длины оптимального решения произвольной конфигурации. В 1996 году была найдена конфигурация, которая не может быть решена меньше чем за 112 перемещений плиток[19]. В 2000 году верхняя граница была улучшена до 210 ходов[20]; в 2011 году для «числа Бога» головоломки Шаблон:Times были получены нижняя граница в 152 хода и верхняя граница в 208 ходов[15].

Текущие результаты

В таблице сведены данные для ряда обобщений «пятнашек». Когда точный результат неизвестен, приводятся лучшие известные оценки снизу и сверху в форме Шаблон:S.

Размер Целевая конфигурация Число решаемых
конфигураций 		«Длинные»
ходы[К 1] 		«Число Бога» Число
«антиподов»[К 2]
Шаблон:Times пустая ячейка в углу 12 нет 6[20][21] 1[20]
Шаблон:Times пустая ячейка в углу 360 нет 21[20][21] 1[20]
Шаблон:Times пустая ячейка в углу Шаблон:Num нет 36[20][21] 1[20]
Шаблон:Times пустая ячейка в углу Шаблон:Num нет 55[22][21] 2[22]
Шаблон:Times пустая ячейка в углу Шаблон:Num нет 80[23][21] 2[23]
Шаблон:Times пустая ячейка в углу Шаблон:Num нет 108[24][21]
Шаблон:Times пустая ячейка в углу Шаблон:Num нет 140[24][21]
Шаблон:Times пустая ячейка в углу Шаблон:Num нет 31[20][15][21] 2[20][25]
да 24[15]
Шаблон:Times пустая ячейка в углу Шаблон:Num нет 53[20][21] 18[20]
Шаблон:Times пустая ячейка в углу Шаблон:Num нет 84[21]
Шаблон:Times пустая ячейка в центре Шаблон:Num нет 84[26]
Шаблон:Times пустая ячейка в углу Шаблон:Num нет 80[14][9][15][21] 17[14][9][17]
да 43[16] 16[16]
Шаблон:Times пустая ячейка в углу 7,7556Шаблон:E нет 152[15] — 208[15]

Использование пятнашек в информатике

«Пятнашки» разных размеров с 1960-х годов регулярно используются в исследованиях в области ИИ; в частности, на них испытываются и сравниваются алгоритмы поиска в пространстве состояний с разными эвристическими функциямиШаблон:SfnШаблон:SfnШаблон:Sfn[27] и другими оптимизациями, влияющими на число посещённых в процессе поиска конфигураций головоломки (вершин графа). В исследованиях так или иначе использовались головоломки размеров Шаблон:Times[28][29], Шаблон:Times[30][31][14], Шаблон:Times[19][32][33], Шаблон:Times[34], Шаблон:Times[26], Шаблон:Times[26].

Можно перечислить основные причины выбора пятнашек в качестве «испытательного стенда» для алгоритмов поискаШаблон:Sfn[11]Шаблон:Sfn:

  1. пространство состояний классических пятнашек является доступным для анализа, но всё же достаточно большим, чтобы представлять интерес и использовать и сравнивать разнообразные эвристикиШаблон:Sfn;
  2. не известен ни один алгоритм, находящий кратчайшее решение для обобщённых пятнашек Шаблон:Times за разумное время[11];
  3. сама задача поиска кратчайшего решения для пятнашек проста для понимания и программного манипулированияШаблон:Sfn[11]; головоломка поддаётся описанию с помощью небольшого и чётко определённого набора простых правилШаблон:Sfn[11];
  4. для моделирования головоломки не требуется передачи семантических тонкостей, присущих более сложным предметным областямШаблон:Sfn;
  5. задачи с пятнашками — удачные представители класса проблем, в которых требуется найти кратчайший путь между двумя заданными вершинами неориентированного конечного графа[11];
  6. размер графа поиска зависит от размера головоломки Шаблон:Mvar экспоненциально, хотя любое состояние можно описать с затратой Шаблон:Mvar(Шаблон:Mvar2) памяти[11];
  7. одна и та же эвристическая функция может применяться ко всем состояниям, так как все состояния описываются одинаково; в реальных применениях разные состояния могут иметь разные описания, что требует введения нескольких эвристикШаблон:Sfn;
  8. использование в исследованиях игр и головоломок не порождает финансовых или этических проблемШаблон:Sfn.

Эвристический поиск

В качестве алгоритма поиска может использоваться алгоритм A*, IDA*[35], поиск в ширину.

Головоломка Шаблон:Times легко решается любым алгоритмом поиска. Произвольные конфигурации пятнашек Шаблон:Times решаются с помощью современных алгоритмов поиска за несколько миллисекундШаблон:Sfn. Для оптимального решения головоломки Шаблон:Times требуются больши́е затраты ресурсов даже с применением современных компьютеров и алгоритмовШаблон:Sfn[32]; процесс поиска может длиться несколько недель и генерировать триллионы узлов[33][34]. Оптимальное решение произвольных конфигураций головоломки Шаблон:Times до сих пор находится за пределами возможностей[34], в связи с чем в исследованиях делаются лишь попытки предсказать относительную производительность алгоритма IDA* с разными эвристическими функциями[34].

Одна из самых простых эвристик для пятнашек может быть выражена следующим образомШаблон:SfnШаблон:SfnШаблон:Sfn:

Число ходов, требуемых для решения, не меньше, чем число плиток, находящихся не на своих местах.

Верность утверждения, то есть допустимость эвристической функции «число плиток, находящихся не на своих местах», следует из того, что за один ход может быть поставлена на место только одна плитка. Эта эвристика не использует всю имеющуюся информацию: например, она не принимает во внимание расстояния, на которые должны быть перемещены отдельные плитки.

Более «умная» эвристика сопоставляет каждому расположению плиток сумму расстояний от текущей позиции каждой плитки до её целевой позицииШаблон:Sfn. В литературе эта эвристика встречается под именем «манхэттенское расстояние» (Manhattan distance)Шаблон:SfnШаблон:Sfn. Допустимость функции следует из того, что за один ход перемещается только одна фишка, и расстояние между этой фишкой и её конечной позицией изменяется на 1. Тем не менее, эта эвристика также не использует всю имеющуюся информацию, из-за того, что в одной позиции не могут находиться одновременно две плитки. Существуют более информированные варианты «манхэттенского расстояния», такие, как Linear ConflictШаблон:Sfn.

Для быстрого поиска оптимального решения головоломки Шаблон:Times, а также для возможности находить оптимальное решение головоломки Шаблон:Times в разумные сроки, разработаны эвристики, основанные на базах данных образцов (pattern databases)[31][32][27]. Подобные эвристики являются по сути заранее вычисленными и хранящимися в оперативной памяти таблицами, в которых закодированы оптимальные решения для подзадач; каждая из подзадач сводится к перемещению в целевые позиции определённой группы плиток[31]. Эти эвристики также могут быть применены к кубику Рубика и другим головоломкам[32].

См. также

Комментарии

Шаблон:Примечания

Примечания

Шаблон:Примечания

Литература

Книги
Статьи

Ссылки

Шаблон:NP-полные задачи

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ 1,0 1,1 Ошибка цитирования Неверный тег <ref>; для сносок etudes-puzzle15 не указан текст
  2. ↑ 2,0 2,1 Ошибка цитирования Неверный тег <ref>; для сносок twistypuzzles не указан текст
  3. ↑ Шаблон:Cite web
  4. ↑ Шаблон:Cite web
  5. ↑ 5,0 5,1 5,2 Ошибка цитирования Неверный тег <ref>; для сносок jaap не указан текст
  6. ↑ 6,0 6,1 Ошибка цитирования Неверный тег <ref>; для сносок Gem Puzzle не указан текст
  7. ↑ Шаблон:Cite web
  8. ↑ Sam Loyd; Martin Gardner: Mathematical puzzles of Sam Loyd. Dover Pubs., New York 1959, pp. 19 und 20. Google books
  9. ↑ 9,0 9,1 9,2 9,3 9,4 Ошибка цитирования Неверный тег <ref>; для сносок fifteensolver не указан текст
  10. ↑ Ошибка цитирования Неверный тег <ref>; для сносок mathworld15 не указан текст
  11. ↑ 11,0 11,1 11,2 11,3 11,4 11,5 11,6 Ошибка цитирования Неверный тег <ref>; для сносок intractable не указан текст
  12. ↑ Ошибка цитирования Неверный тег <ref>; для сносок ratner_warmuth_1990 не указан текст
  13. ↑ Ошибка цитирования Неверный тег <ref>; для сносок Brungger99 не указан текст
  14. ↑ 14,0 14,1 14,2 14,3 14,4 Ошибка цитирования Неверный тег <ref>; для сносок korf_schultze_2005 не указан текст
  15. ↑ 15,0 15,1 15,2 15,3 15,4 15,5 15,6 Ошибка цитирования Неверный тег <ref>; для сносок oeis-a087725 не указан текст
  16. ↑ 16,0 16,1 16,2 16,3 Ошибка цитирования Неверный тег <ref>; для сносок node/view/223 не указан текст
  17. ↑ 17,0 17,1 Ошибка цитирования Неверный тег <ref>; для сносок oeis-a089484 не указан текст
  18. ↑ Ошибка цитирования Неверный тег <ref>; для сносок 10.1.1.39.6069 не указан текст
  19. ↑ 19,0 19,1 Ошибка цитирования Неверный тег <ref>; для сносок taylor_korf_1996 не указан текст
  20. ↑ 20,00 20,01 20,02 20,03 20,04 20,05 20,06 20,07 20,08 20,09 20,10 Ошибка цитирования Неверный тег <ref>; для сносок 10.1.1.55.7558 не указан текст
  21. ↑ 21,00 21,01 21,02 21,03 21,04 21,05 21,06 21,07 21,08 21,09 21,10 Ошибка цитирования Неверный тег <ref>; для сносок oeis-a151944 не указан текст
  22. ↑ 22,0 22,1 Шаблон:OEIS long
  23. ↑ 23,0 23,1 Шаблон:OEIS long
  24. ↑ 24,0 24,1 Шаблон:OEIS long
  25. ↑ Шаблон:OEIS long
  26. ↑ 26,0 26,1 26,2 Ошибка цитирования Неверный тег <ref>; для сносок 10.1.1.519.9720 не указан текст
  27. ↑ 27,0 27,1 Ошибка цитирования Неверный тег <ref>; для сносок yang_et_al_2008 не указан текст
  28. ↑ Ошибка цитирования Неверный тег <ref>; для сносок reinefeld_1993 не указан текст
  29. ↑ Ошибка цитирования Неверный тег <ref>; для сносок kunkle_2001 не указан текст
  30. ↑ Ошибка цитирования Неверный тег <ref>; для сносок korf_1985 не указан текст
  31. ↑ 31,0 31,1 31,2 Ошибка цитирования Неверный тег <ref>; для сносок culberson_schaeffer_1998 не указан текст
  32. ↑ 32,0 32,1 32,2 32,3 Ошибка цитирования Неверный тег <ref>; для сносок korf_2000 не указан текст
  33. ↑ 33,0 33,1 Ошибка цитирования Неверный тег <ref>; для сносок korf_felner_2002 не указан текст
  34. ↑ 34,0 34,1 34,2 34,3 Ошибка цитирования Неверный тег <ref>; для сносок felner_korf_hanan_2004 не указан текст
  35. ↑ Ошибка цитирования Неверный тег <ref>; для сносок brian_borowski не указан текст


Ошибка цитирования Для существующих тегов <ref> группы «К» не найдено соответствующего тега <references group="К"/>

Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Игра_в_15&oldid=9973938