Пятнашки

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Пятнашки

Игра в 15[1] или Пятна́шки[источник не указан 60 дней] — популярная головоломка, придуманная в 1878 году Ноем Чепмэном. Представляет собой набор одинаковых квадратных костяшек с нанесёнными числами, заключённых в квадратную коробку. Длина стороны коробки в четыре раза больше длины стороны костяшек для набора из 15 элементов (и в три раза больше для набора в 8 элементов), соответственно в коробке остаётся незаполненным одно квадратное поле. Цель игры — перемещая костяшки по коробке, добиться упорядочивания их по номерам, желательно сделав как можно меньше перемещений.

История создания[править | править исходный текст]

Пятнашки в сборе

С 1891 года до самой смерти Сэмюэл Лойд утверждал, что изобрёл головоломку именно он[2]. Однако существуют доказательства того, что он был непричастен к созданию «пятнашек»[3][4].

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

Сын Ноя Чепмэна, Фрэнк Чепмэн, привёз доработанные головоломки в Сиракузы (штат Нью-Йорк), а затем в Хартфорд (Коннектикут), где слушатели Американской школы для слабослышащих (англ.) начали производство головоломки. К 1879 году она уже продавалась не только в Хартфорде, но и в Бостоне. Тогда о «пятнашках» узнал художник по дереву Маттиас Райс. В декабре 1879 года он начал бизнес по производству новой головоломки под названием «Драгоценная головоломка» (англ. Gem Puzzle).

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

21 февраля 1880 года Ной Чепмэн попытался оформить патент на своё изобретение под наименованием «Block Solitaire Puzzle»[5], однако заявка на патент была отклонена, так как мало отличалась от уже оформленного тремя годами ранее патента «Хитрые блоки», «Puzzle-Blocks»[3].

Математическое описание[править | править исходный текст]

Нерешаемая комбинация, предложенная Ноем Чепменом

Пятнашки представляют собой классическую задачу для моделирования эвристических алгоритмов. Обычно задачу решают через количество перемещений и поиск манхэттенского расстояния между каждой костяшкой и её позицией в собранной головоломке. Для решения обычно используется алгоритм IDA*[6].

Можно показать, что ровно половину из всех возможных 20 922 789 888 000 (=16!) начальных положений пятнашек невозможно привести к собранному виду: пусть квадратик с числом  i расположен до (если считать слева направо и сверху вниз)  k квадратиков с числами меньшими  i . Будем считать  n_i = k , то есть если после костяшки с i-м числом нет чисел, меньших i, то  k = 0. Также введем число e — номер ряда пустой клетки (считая с 1). Если сумма

N = \sum_{i=1}^{15} n_i + e

является нечётной, то решения головоломки не существует[7].

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

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

См. также[править | править исходный текст]

Примечания[править | править исходный текст]

  1. Гарднер М. Математические досуги / Пер. с англ. Ю. А. Данилова. Под ред. Я. А. Смородинского. — М.: Мир, 1972. — С. 401.
  2. Cyclopedia of Puzzles, p. 235
  3. 1 2 The 15 Puzzle, by Jerry Slocum & Dic Sonneveld, 2006. ISBN 1-890980-15-3
  4. Barry R. Clarke, Puzzles for Pleasure, pp.10-12, Cambridge University Press, 1994 ISBN 0-521-46634-2.
  5. Block Solitaire Puzzle — «Головоломка—пасьянс с блоками» (solitaire — солитер, пасьянс, игра для одного человека)
  6. Brian S. Borowski. Optimal 8/15-Puzzle Solver. Brian's Project Gallery. Проверено 29 июля 2013. Архивировано из первоисточника 17 августа 2013.
  7. Jerry Slocum and Eric W. Weisstein Пятнашки (англ.) на сайте Wolfram MathWorld.
  8. Daniel Ratner, Manfred K. Warmuth. Finding a Shortest Solution for the N × N Extension of the 15-PUZZLE Is Intractable. National Conference on Artificial Intelligence, 1986.
  9. Ratner, Daniel; Warmuth, Manfred (1990). «The (n2−1)-puzzle and related relocation problems». Journal of Symbolic Computation 10 (2): 111–137. DOI:10.1016/S0747-7171(08)80001-6.

Ссылки[править | править исходный текст]