Просмотр кода страницы Игра в 15

{{другие значения|15 (значения)}}
{{другие значения|Пятнашки}}
[[Файл:Пятнашки.jpg|thumb|right]]
[[Файл:15-puzzle-01.jpg|thumb|right|Головоломка-[[брелок]]]]
'''Игра в 15'''{{sfn|Математические досуги|1972|с=401}}{{sfn|Занимательные задачи и опыты|1972|с=365}}<ref name="etudes-puzzle15" />, '''пятнашки'''{{sfn|Искусственный интеллект: стратегии и методы решения сложных проблем|2003|с=43, 114, 163, 166, 168, 181-182}}<ref name="twistypuzzles" />, '''такен'''{{sfn|Занимательные задачи и опыты|1972|с=365}}<ref name="twistypuzzles" /><ref>{{cite web
 |url = http://old.computerra.ru/offline/2000/331/2868/
 |title = Головоломки из близкой дали. Часть 2
 |author = Владимир Белов
 |date = 2000-01-18
 |publisher = [[Компьютерра]]
 |archiveurl = https://web.archive.org/web/20151128225508/http://old.computerra.ru/offline/2000/331/2868/
 |archivedate = 2015-11-28
 |ref = Головоломки из близкой дали. Часть 2
}}</ref> — популярная [[перестановочная головоломка]], придуманная в 1878 году Ноем Чепмэном. Головоломка представляет собой набор из 15 одинаковых [[квадрат]]ных костяшек с нанесёнными на них числами, лежащих в квадратной коробке. Длина стороны коробки в четыре раза больше длины стороны костяшки, поэтому в коробке остаётся незаполненным одно квадратное поле. Цель игры — упорядочить костяшки по возрастанию номеров, перемещая их внутри коробки, желательно сделав как можно меньше перемещений.

== История ==

=== Авторство ===
С [[1891 год]]а до самой смерти [[Лойд, Сэмюэл|Сэмюэл Лойд]] утверждал, что изобрёл головоломку именно он, и долгое время считалось, что это действительно так<ref>{{Cite web |url=http://www.mathpuzzle.com/loyd/cop234-235.jpg |title=''Cyclopedia of Puzzles'', p. 235 |access-date=2013-08-08 |archive-date=2012-05-24 |archive-url=https://web.archive.org/web/20120524044802/http://www.mathpuzzle.com/loyd/cop234-235.jpg |deadlink=no }}</ref><ref name="jaap" />. Однако существуют доказательства того, что он не был причастен ни к созданию «пятнашек», ни к вариации с переставленными фишками 14 и 15{{sfn|The 15 Puzzle|2006}}{{sfn|Review of ''The 15 Puzzle'' by Aaron Archer|p=1}}{{sfn|Puzzles for Pleasure|1994|p=10—12}}<ref name="jaap" />. Пик популярности головоломки в США пришёлся на первую половину 1880 года; при этом не было обнаружено никаких упоминаний Сэма Лойда в связи с «пятнашками» вплоть до января 1891 года{{sfn|The 15 Puzzle|2006|p=76}}{{sfn|Review of ''The 15 Puzzle'' by Aaron Archer|p=1}}. В частности, ''[[The New York Times]]'' дважды публиковала материалы о головоломке, 22 марта 1880 года и 11 июня 1880 года, ни разу не упомянув при этом Лойда, несмотря на то что Лойд жил в Нью-Йорке{{sfn|Puzzles for Pleasure|1994|p=11}}.

Настоящим изобретателем головоломки был Ной Палмер Чепмэн, почтмейстер из [[Канастота (Нью-Йорк)|Канастоты]]{{sfn|The 15 Puzzle|2006|p=109}}{{sfn|Review of ''The 15 Puzzle'' by Aaron Archer|p=1, 3}}, который ещё в 1874 году показывал друзьям головоломку, состоящую из шестнадцати пронумерованных квадратиков, которые надо было сложить в ряды по четыре штуки так, чтобы [[Магический квадрат|сумма чисел в каждом ряду была равна 34]]{{sfn|The 15 Puzzle|2006|p=98—99}}.

Сын Ноя Чепмэна, Фрэнк Чепмэн, привёз доработанные головоломки в [[Сиракузы (Нью-Йорк)|Сиракузы (штат Нью-Йорк)]] и передал их Анне и Джеймсу Бельден (Anna and James Belden){{sfn|The 15 Puzzle|2006|p=103—104, 109}}. Они, в свою очередь, забрали головоломку в {{нп5|Уотч-Хилл, Род-Айленд|Уотч-Хилл (Род-Айленд)|en|Watch Hill, Rhode Island}}, где были сделаны копии головоломки{{sfn|The 15 Puzzle|2006|p=109}}; одна из этих копий не известным в точности путём попала в [[Хартфорд (Коннектикут)|Хартфорд]]{{sfn|The 15 Puzzle|2006|p=109}}, где слушатели {{нп5|Американская школа для слабослышащих|Американской школы для слабослышащих|en|American School for the Deaf}} начали делать грубые копии головоломки{{sfn|The 15 Puzzle|2006|p=109}}<!--<ref group="К">В {{harv|По следам Пифагора|1961|с=231}} утверждается, что игра «происходит из Америки, где её изобрёл некий глухонемой в 1878 году». Предположение, что головоломку изобрёл некий глухонемой, подробно рассматривается в {{harv|The 15 Puzzle|2006|pp=68, 69, 71, 95-97}}.</ref>-->. К 1879 году головоломка уже продавалась не только в Хартфорде, но и в [[Бостон]]е. Тогда о «пятнашках» узнал художник по дереву Маттиас Райс (Matthias J. Rice). В декабре 1879 года Маттиас Райс начал в Бостоне бизнес по производству новой головоломки под названием «Драгоценная головоломка» ({{lang-en|The Gem Puzzle}}){{sfn|The 15 Puzzle|2006|p=11, 109}}{{sfn|Review of ''The 15 Puzzle'' by Aaron Archer|p=2}}<ref name="Gem Puzzle" />.

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

21 февраля 1880 года Ной Чепмэн попытался оформить патент на своё изобретение под наименованием «Block Solitaire Puzzle» («Головоломка—пасьянс с блоками»){{sfn|The 15 Puzzle|2006|p=100—101}}, однако заявка на патент была отклонена; не сохранилось записей, объясняющих, почему это произошло{{sfn|The 15 Puzzle|2006|p=101}}. По-видимому, это было вызвано тем, что, по мнению патентного инспектора Бурке, новая заявка мало отличалась от патента<ref>{{cite web |url=http://www.jaapsch.net/puzzles/patents/us207124.pdf |title=E. U. Kinsey. Puzzle-Blocks. No. 207124. Patented Aug. 20, 1878 |access-date=2015-12-03 |archive-date=2015-12-27 |archive-url=https://web.archive.org/web/20151227113348/http://www.jaapsch.net/puzzles/patents/us207124.pdf |deadlink=no }}</ref> «Хитрые блоки», «Puzzle-Blocks», выданного Эрнесту У. Кинси (Ernest U. Kinsey) более чем за год до того, как Ной Чепмэн подал свою заявку{{sfn|The 15 Puzzle|2006|p=102}}{{sfn|Review of ''The 15 Puzzle'' by Aaron Archer|p=3}}.

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

==== В США ====
6 января 1880 года в газете {{нп5|Boston Evening Transcript||en|Boston Evening Transcript}} появилось объявление о головоломке под названием ''Boss Puzzle''. 12 января Boston Transcript упомянула несколько версий других производителей, включая ''Gem Puzzle'', ''Solitaire'', ''Fifteen'' и ''Number Puzzle''. 19 января в той же газете была анонсирована<!--was advertised--> головоломка под названием ''The New Puzzle''; на следующий же день Worcester Gazette разместила объявление о головоломке ''The Boss Puzzle''. Популярность головоломки стремительно росла, и предприниматели уже начали её производство и продажу{{sfn|The 15 Puzzle|2006|p=14—15}}.

В промежуток времени с 26 по 30 января Boston Evening Transcript опубликовала объявление Маттиаса Райса, раздосадованного появлением копий головоломки. В объявлении говорилось{{sfn|The 15 Puzzle|2006|p=15—16}}:
{{coquote|Остерегайтесь подделок. Убедитесь, что вы приобретаете эту, единственную аккуратно сделанную, тщательно испытанную головоломку.||Rice’s Gem Puzzle. The Great Original. Beware of Imitations. Be sure you ask for this, the only accurately made, thoroughly reliable Puzzle in the market, and take no other.|en}}

В феврале 1880 года в разных газетах начали появляться подробные статьи, посвящённые головоломке{{sfn|The 15 Puzzle|2006|p=12}}. Ряд журналов национального масштаба, включая {{нп5|The Youth's Companion||en|The Youth's Companion}}, Illustrated Newspaper, [[Harper’s Weekly]], [[Scientific American]], {{нп5|The Independent (Нью-Йорк)|The Independent|en|The Independent (New York)}}, в течение нескольких недель публиковали объявления о головоломке{{sfn|The 15 Puzzle|2006|p=20}}. Новости о головоломке распространялись в другие города. К началу марта многие производители выпускали версии головоломки под разными названиями{{sfn|Review of ''The 15 Puzzle'' by Aaron Archer|p=2}}.

12 февраля газета {{нп5|Boston Herald||en|Boston Herald}} опубликовала поэму о головоломке, за которой последовал ряд произведений в стихотворной форме в других газетах{{sfn|The 15 Puzzle|2006|p=21}}.
17 февраля в газете {{нп5|Democrat and Chronicle|Rochester Democrat and Chronicle|en|Democrat and Chronicle}} была опубликована статья о влиянии головоломки на общество. 20 февраля в нью-йоркском журнале Ontario County Journal появилась заметка следующего содержания{{sfn|The 15 Puzzle|2006|p=24, 98}}:
{{coquote|Вероятно, Н. П. Чепмэн, почтмейстер из Канастоты, в течение ближайших нескольких недель будет самым проклинаемым человеком в стране. Он изобрёл Игру в 15.||Probably N. P. Chapman, postmaster of Canastota, N.Y., will, during the coming few weeks, be the most heartily cursed man in the country. He invented the 'Game of 15'.|en}}

17 марта 1880 года газета {{нп5|Boston Daily Advertiser||en|Boston Daily Advertiser}} опубликовала статью, которая описывала «начало безумия» в Бостоне три месяца тому назад (в декабре 1879){{sfn|The 15 Puzzle|2006|p=12}}.

На основании газетных объявлений и статей авторы книги ''The 15 Puzzle'' Слокум и Зонневельд делают вывод, что в большинстве городов<!--cities and towns--> «безумие» длилось один-два месяца; впрочем, во многих городах головоломка становилась популярной до появления публикаций в местных газетах и оставалась популярной даже тогда, когда публикации прекращались{{sfn|The 15 Puzzle|2006|p=59}}.

==== За пределами США ====
В марте 1880 года головоломка начала распространяться за пределами США. До конца марта она достигла Канады и Франции. В течение апреля «безумие» достигло Англии, Германии, Латвии, Австрии, Эстонии, Норвегии, Швеции, России, Финляндии, в мае — Новой Зеландии, Нидерландов, Италии, Мексики, Дании, Австралии{{sfn|The 15 Puzzle|2006|p=60}}.

==== В России ====
25 апреля 1880 года газета {{нп5|Sankt Petersburger Herold|St. Petersburg Herold|de|Sankt Petersburger Herold}} на немецком языке разместила объявление «Neues Spiel — Das Spiel der Funfzehn»{{sfn|The 15 Puzzle|2006|p=63}} («Новая игра — Игра в 15»).

== Задачи ==

=== The Gem Puzzle ===
В головоломке ''The Gem Puzzle'', которую в 1879 году производил и продавал Матиас Райс, игрок высыпал плитки из коробочки и случайным образом укладывал их обратно, после чего пытался восстановить упорядоченную конфигурацию<ref name="Gem Puzzle" />{{sfn|Review of ''The 15 Puzzle'' by Aaron Archer|p=1}}:
{{coquote|Поместите блоки в коробочку беспорядочным образом, затем перемещайте, пока они не выстроятся в правильном порядке.||Place the blocks in the box irregularly, then move until in regular order.|en}}

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

=== Головоломка 14-15 ===
В другой версии все плитки, за исключением 14 и 15, изначально находятся на своих местах; задача состоит в том, чтобы поменять местами неправильно стоящие плитки 14 и 15. Эта задача неразрешима; тем не менее, в этом случае можно упорядочить плитки с пустой ячейкой в верхнем левом углу либо выстроить фишки столбцами{{sfn|Занимательные задачи и опыты|1972|с=370}}.

<gallery>
Файл:15-puzzle-loyd.svg|Рис. 1. В начальном положении в головоломке 14-15 плитки 14 и 15 поменяны местами
Файл:15-puzzle.svg|Рис. 2. Это расположение недостижимо из начального расположения головоломки 14-15 (Рис. 1)
Файл:15-puzzle-loyd-bis2.svg|Рис. 3. Но это расположение достижимо из начального расположения головоломки 14-15 (Рис. 1)
Файл:15-puzzle vertical.svg|Рис. 4. Ещё одно достижимое расположение для головоломки 14-15 (Рис. 1)
</gallery>

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

<gallery>
15-puzzle-Slon-Spit-Stoya.svg|Слон спит стоя. А вы?
15-puzzle-Rate-Your-Mind-Pal.svg|На английском языке («Измерь свой разум, дружок»)<ref name="jaap" />
15-puzzle-Ohne-Fleiß-kein-Preis.svg|На немецком языке («Без трудолюбия нет награды»)
</gallery>

=== Магический квадрат ===
[[Файл:15-puzzle_magical.svg|thumb|right|Магический квадрат]]
Одна из задач — переставить плитки таким образом, чтобы сумма чисел в каждом ряду (горизонтали, вертикали или большой диагонали) [[Магический квадрат|была равна одному и тому же числу]]; при этом числовое значение пустой ячейки считается равным нулю{{sfn|Занимательные задачи и опыты|1972|с=371}}<ref>Sam Loyd; Martin Gardner: ''Mathematical puzzles of Sam Loyd''. Dover Pubs., New York 1959, pp. 19 und 20. [https://books.google.com/books?id=QCy6DzgqcI4C&pg=PA20 Google books]</ref>. При этом магическая сумма равна 30. Требуется по меньшей мере 35 ходов, чтобы получить магический квадрат из начального расположения, и существует лишь один магический квадрат, достижимый в 35 ходов<ref name="fifteensolver" />.

== Математическое описание ==
Можно показать, что ровно половину из всех возможных {{число|20922789888000}} (=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|thumb|left|Нерешаемая комбинация]]

: <math>N = \sum_{i=1}^{15} n_i + e</math>

(то есть сумма числа пар костяшек, в которых костяшка с большим номером идёт перед костяшкой с меньшим номером, и номера ряда пустой клетки) [[Чётные и нечётные числа|нечётна]], то решения головоломки не существует<ref name="mathworld15" /><ref name="etudes-puzzle15" />.

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

== Оптимальное решение ==
Для обобщённых пятнашек (с бо́льшим, чем 15, количеством костяшек) задача поиска кратчайшего решения для заданной конфигурации является [[NP-полная задача|NP-полной]]<ref name="intractable" /><ref name="ratner_warmuth_1990" />.

=== {{times|4|4}} ===
Любую из {{num|10461394944000}} разрешимых конфигураций «классической» головоломки {{times|4|4}} можно перевести в начальную не более чем за 80 ходов, если под ходом понимать перемещение одной плитки<ref name="Brungger99" /><ref name="korf_schultze_2005" /><ref name="fifteensolver" /><ref name="oeis-a087725" />, или не более чем за 43 хода, если под ходом понимать одновременное перемещение сплошного ряда из не более чем трёх плиток<ref name="node/view/223" />. Только 17 из всех разрешимых конфигураций не могут быть решены менее чем за 80 ходов, то есть требуют 80 перемещений отдельных плиток для решения<ref name="korf_schultze_2005" /><ref name="fifteensolver" /><ref name="oeis-a089484" />; только 16 разрешимых конфигураций требуют 43 перемещений сплошных рядов плиток<ref name="node/view/223" />.

=== {{times|5|5}} ===
В 1995 году было показано, что любая конфигурация головоломки {{times|5|5}} может быть решена не более чем за 219 одиночных ходов<ref name="10.1.1.39.6069" />, то есть была получена верхняя граница в 219 ходов для длины оптимального решения произвольной конфигурации.
В 1996 году была найдена конфигурация, которая не может быть решена меньше чем за 112 перемещений плиток<ref name="taylor_korf_1996" />.
В 2000 году верхняя граница была улучшена до 210 ходов<ref name="10.1.1.55.7558" />; в 2011 году для «[[Число Бога|числа Бога]]» головоломки {{times|5|5}} были получены нижняя граница в 152 хода и верхняя граница в 208 ходов<ref name="oeis-a087725" />.

=== n<sup>2</sup> - 1 ===
В 2023 году было показано, что среднее оптимальное решение обобщенной версии головоломки требует <math> \frac{2}{3} n^3 + O(n^{2.75})</math> одиночных ходов, а «[[число Бога]]» оценивается <math>n^3 + O(n^{2.75})</math><ref>{{Статья|ссылка=https://link.springer.com/10.1007/978-3-031-39344-0_10|автор=Zhixian Zhong|заглавие=Additive Approximation Algorithms for Sliding Puzzle|год=2023|ответственный=Minming Li, Xiaoming Sun, Xiaowei Wu|язык=en|место=Cham|издание=Frontiers of Algorithmics|издательство=Springer Nature Switzerland|том=13933|страницы=129–146|isbn=978-3-031-39343-3|doi=10.1007/978-3-031-39344-0_10}}</ref>.

=== Текущие результаты ===
В таблице сведены данные для ряда обобщений «пятнашек». Когда точный результат неизвестен, приводятся лучшие известные оценки снизу и сверху в форме {{s|''lb'' — ''ub''}}.
{|class="wikitable" style="text-align:center"
|-
! Размер
! Целевая конфигурация
! Число решаемых<br>конфигураций
! «Длинные»<br>ходы<ref group="К">В столбце указано, считается ли за один ход одновременное перемещение нескольких плиток, образующих сплошной вертикальный или горизонтальный ряд</ref>
! «[[Число Бога]]»<ref group="К">Число ходов, за которое головоломку можно решить из самого трудного положения (требующего больше всего ходов)</ref>
! Число<br>«антиподов»<ref group="К">«Антиподы» — конфигурации головоломки, требующие наибольшего числа ходов для решения</ref>
|-
| {{times|2|2}}
| пустая ячейка в углу
| 12
| нет
| 6<ref name="10.1.1.55.7558" /><ref name="oeis-a151944" />
| 1<ref name="10.1.1.55.7558" />
|-
| {{times|2|3}}
| пустая ячейка в углу
| 360
| нет
| 21<ref name="10.1.1.55.7558" /><ref name="oeis-a151944" />
| 1<ref name="10.1.1.55.7558" />
|-
| {{times|2|4}}
| пустая ячейка в углу
| {{num|20160}}
| нет
| 36<ref name="10.1.1.55.7558" /><ref name="oeis-a151944" />
| 1<ref name="10.1.1.55.7558" />
|-
| {{times|2|5}}
| пустая ячейка в углу
| {{num|1814400}}
| нет
| 55<ref name="oeis-a090036">{{OEIS long|90036}}</ref><ref name="oeis-a151944" />
| 2<ref name="oeis-a090036" />
|-
| {{times|2|6}}
| пустая ячейка в углу
| {{num|239500800}}
| нет
| 80<ref name="oeis-a090167">{{OEIS long|90167}}</ref><ref name="oeis-a151944" />
| 2<ref name="oeis-a090167" />
|-
| {{times|2|7}}
| пустая ячейка в углу
| {{num|43589145600}}
| нет
| 108<ref name="oeis-a151943">{{OEIS long|151943}}</ref><ref name="oeis-a151944" />
|
|-
| {{times|2|8}}
| пустая ячейка в углу
| {{num|10461394944000}}
| нет
| 140<ref name="oeis-a151943" /><ref name="oeis-a151944" />
|
|-
|rowspan=2 | {{times|3|3}}
|rowspan=2 | пустая ячейка в углу
|rowspan=2 | {{num|181440}}
| нет
| 31<ref name="10.1.1.55.7558" /><ref name="oeis-a087725" /><ref name="oeis-a151944" />
| 2<ref name="10.1.1.55.7558" /><ref>{{OEIS long|89473}}</ref>
|-
| да
| 24<ref name="oeis-a087725" />
|
|-
| {{times|3|4}}
| пустая ячейка в углу
| {{num|239500800}}
| нет
| 53<ref name="10.1.1.55.7558" /><ref name="oeis-a151944" />
| 18<ref name="10.1.1.55.7558" />
|-
| {{times|3|5}}
| пустая ячейка в углу
| {{num|653837184000}}
| нет
| 84<ref name="oeis-a151944" />
|
|-
| {{times|3|5}}
| пустая ячейка в центре
| {{num|653837184000}}
| нет
| 84<ref name="10.1.1.519.9720" />
|
|-
|rowspan=2 | {{times|4|4}}
|rowspan=2 | пустая ячейка в углу
|rowspan=2 | {{num|10461394944000}}
| нет
| 80<ref name="korf_schultze_2005" /><ref name="fifteensolver" /><ref name="oeis-a087725" /><ref name="oeis-a151944" />
| 17<ref name="korf_schultze_2005" /><ref name="fifteensolver" /><ref name="oeis-a089484" />
|-
| да
| 43<ref name="node/view/223" />
| 16<ref name="node/view/223" />
|-
| {{times|5|5}}
| пустая ячейка в углу
| 7,7556{{e|24}}
| нет
| 152 — 208<ref name="oeis-a087725" />
|
|}

== Использование пятнашек в информатике ==
«Пятнашки» разных размеров с 1960-х годов регулярно используются в исследованиях в области [[Искусственный интеллект|ИИ]]; в частности, на них испытываются и сравниваются алгоритмы [[Поиск в пространстве состояний|поиска в пространстве состояний]] с разными [[Эвристическая функция|эвристическими функциями]]{{sfn|Искусственный интеллект: стратегии и методы решения сложных проблем|2003|с=114}}{{sfn|Искусственный интеллект: современный подход|2006|с=118}}{{sfn|Generating Admissible Heuristics by Criticizing Solutions to Relaxed Models|1985}}<ref name="yang_et_al_2008" /> и другими оптимизациями, влияющими на число посещённых в процессе поиска конфигураций головоломки (вершин графа). В исследованиях так или иначе использовались головоломки размеров {{times|3|3}}<ref name="reinefeld_1993" /><ref name="kunkle_2001" />, {{times|4|4}}<ref name="korf_1985" /><ref name="culberson_schaeffer_1998" /><ref name="korf_schultze_2005" />, {{times|5|5}}<ref name="taylor_korf_1996" /><ref name="korf_2000" /><ref name="korf_felner_2002" />, {{times|6|6}}<ref name="felner_korf_hanan_2004" />, {{times|2|7}}<ref name="10.1.1.519.9720" />, {{times|3|5}}<ref name="10.1.1.519.9720" />.

Можно перечислить основные причины выбора пятнашек в качестве «испытательного стенда» для алгоритмов поиска{{sfn|Искусственный интеллект: стратегии и методы решения сложных проблем|2003|с=43, 114, 163}}<ref name="intractable" />{{sfn|Generating Admissible Heuristics by Criticizing Solutions to Relaxed Models|1985|p=3}}:
# [[Поиск в пространстве состояний|пространство состояний]] классических пятнашек является доступным для анализа, но всё же достаточно большим, чтобы представлять интерес и использовать и сравнивать разнообразные эвристики{{sfn|Искусственный интеллект: стратегии и методы решения сложных проблем|2003|с=114, 163}};
# не известен ни один алгоритм, находящий кратчайшее решение для обобщённых пятнашек {{times|{{mvar|n}}|{{mvar|n}}}} за разумное время<ref name="intractable" />;
# сама задача поиска кратчайшего решения для пятнашек проста для понимания и программного манипулирования{{sfn|Искусственный интеллект: стратегии и методы решения сложных проблем|2003|с=114}}<ref name="intractable" />; головоломка поддаётся описанию с помощью небольшого и чётко определённого набора простых правил{{sfn|Искусственный интеллект: стратегии и методы решения сложных проблем|2003|с=43, 163}}<ref name="intractable" />;
# для моделирования головоломки не требуется передачи семантических тонкостей, присущих более сложным предметным областям{{sfn|Искусственный интеллект: стратегии и методы решения сложных проблем|2003|с=43}};
# задачи с пятнашками — удачные представители класса проблем, в которых требуется найти кратчайший путь между двумя заданными вершинами неориентированного конечного графа<ref name="intractable" />;
# размер графа поиска зависит от размера головоломки {{mvar|n}} экспоненциально, хотя любое состояние можно описать с затратой {{mvar|O}}({{mvar|n}}<sup>2</sup>) памяти<ref name="intractable" />;
# одна и та же эвристическая функция может применяться ко всем состояниям, так как все состояния описываются одинаково; в реальных применениях разные состояния могут иметь разные описания, что требует введения нескольких эвристик{{sfn|Искусственный интеллект: стратегии и методы решения сложных проблем|2003|с=163}};
# использование в исследованиях игр и головоломок не порождает финансовых или этических проблем{{sfn|Искусственный интеллект: стратегии и методы решения сложных проблем|2003|с=43}}.

=== Эвристический поиск ===
В качестве алгоритма поиска может использоваться алгоритм [[A*]], [[IDA*]]<ref name="brian_borowski" />, [[поиск в ширину]].

Головоломка {{times|3|3}} легко решается любым алгоритмом поиска. Произвольные конфигурации пятнашек {{times|4|4}} решаются с помощью современных алгоритмов поиска за несколько миллисекунд{{sfn|Искусственный интеллект: современный подход|2006|с=118}}. Для оптимального решения головоломки {{times|5|5}} требуются больши́е затраты ресурсов даже с применением современных компьютеров и алгоритмов{{sfn|Искусственный интеллект: современный подход|2006|с=118}}<ref name="korf_2000" />; процесс поиска может длиться несколько недель и генерировать [[триллион]]ы узлов<ref name="korf_felner_2002" /><ref name="felner_korf_hanan_2004" />. Оптимальное решение произвольных конфигураций головоломки {{times|6|6}} до сих пор находится за пределами возможностей<ref name="felner_korf_hanan_2004" />, в связи с чем в исследованиях делаются лишь попытки предсказать относительную производительность алгоритма [[IDA*]] с разными эвристическими функциями<ref name="felner_korf_hanan_2004" />.

Одна из самых простых [[Эвристическая функция|эвристик]] для пятнашек может быть выражена следующим образом{{sfn|Искусственный интеллект: стратегии и методы решения сложных проблем|2003|с=156}}{{sfn|Занимательное программирование: Самоучитель|2005|с=171}}{{sfn|Generating Admissible Heuristics by Criticizing Solutions to Relaxed Models|1985|p=4—5}}:
: ''Число ходов, требуемых для решения, не меньше, чем число плиток, находящихся не на своих местах.''
Верность утверждения, то есть допустимость эвристической функции «число плиток, находящихся не на своих местах», следует из того, что за один ход может быть поставлена на место только одна плитка. Эта эвристика не использует всю имеющуюся информацию: например, она не принимает во внимание расстояния, на которые должны быть перемещены отдельные плитки.

Более «умная» эвристика сопоставляет каждому расположению плиток сумму [[Расстояние городских кварталов|расстояний]] от текущей позиции каждой плитки до её целевой позиции{{sfn|Искусственный интеллект: стратегии и методы решения сложных проблем|2003|с=157}}. В литературе эта эвристика встречается под именем «манхэттенское расстояние» (Manhattan distance){{sfn|Generating Admissible Heuristics by Criticizing Solutions to Relaxed Models|1985|p=4—5}}{{sfn|Занимательное программирование: Самоучитель|2005|с=173}}. Допустимость функции следует из того, что за один ход перемещается только одна фишка, и расстояние между этой фишкой и её конечной позицией изменяется на 1. Тем не менее, эта эвристика также не использует всю имеющуюся информацию, из-за того, что в одной позиции не могут находиться одновременно две плитки. Существуют [[Эвристическая функция|более информированные]] варианты «манхэттенского расстояния», такие, как Linear Conflict{{sfn|Generating Admissible Heuristics by Criticizing Solutions to Relaxed Models|1985}}.

Для быстрого поиска оптимального решения головоломки {{times|4|4}}, а также для возможности находить оптимальное решение головоломки {{times|5|5}} в разумные сроки, разработаны эвристики, основанные на базах данных образцов (pattern databases)<ref name="culberson_schaeffer_1998" /><ref name="korf_2000" /><ref name="yang_et_al_2008" />. Подобные эвристики являются по сути заранее вычисленными и хранящимися в оперативной памяти таблицами, в которых закодированы оптимальные решения для подзадач; каждая из подзадач сводится к перемещению в целевые позиции определённой группы плиток<ref name="culberson_schaeffer_1998" />. Эти эвристики также могут быть применены к [[кубик Рубика|кубику Рубика]] и другим головоломкам<ref name="korf_2000" />.

== См. также ==
* [[Кубик Рубика]]
* [[Минус-кубик]]

== Комментарии ==
{{примечания|group="К"}}

== Примечания ==
{{примечания|2|refs=

<ref name="intractable">''Ratner D., Warmuth M. K.'' [https://www.aaai.org/Papers/AAAI/1986/AAAI86-027.pdf Finding a Shortest Solution for the N × N Extension of the 15-PUZZLE Is Intractable] {{Wayback|url=https://www.aaai.org/Papers/AAAI/1986/AAAI86-027.pdf |date=20120309151834 }} // National Conference on Artificial Intelligence, 1986.</ref>

<ref name="ratner_warmuth_1990">{{статья|автор= Ratner D., Warmuth M.|заглавие= The (n<sup>2</sup>−1)-puzzle and related relocation problems|ссылка= http://users.soe.ucsc.edu/~manfred/pubs/J15.pdf|язык= |издание= Journal of Symbolic Computation|тип= |год= 1990|том= 10|номер= 2|страницы= 111–137|doi= 10.1016/S0747-7171(08)80001-6|issn= |archivedate= 2017-08-13|archiveurl= https://web.archive.org/web/20170813234226/https://users.soe.ucsc.edu/~manfred/pubs/J15.pdf}}</ref>

<ref name="mathworld15">{{MathWorld|15Puzzle|15 Puzzle|author=Slocum J., Weisstein E. W.}}</ref>

<ref name="brian_borowski">{{cite web|url=http://www.brian-borowski.com/Software/Puzzle/|author=Borowski B. S.|title=Optimal 8/15-Puzzle Solver|publisher=// Brian's Project Gallery|accessdate=2013-07-29|archiveurl=https://www.webcitation.org/6IviU8lzX?url=http://www.brian-borowski.com/Software/Puzzle/|archivedate=2013-08-17}}</ref>

<ref name="Brungger99">A. Brüngger, A. Marzetta, K. Fukuda and J. Nievergelt, [http://www.iro.umontreal.ca/~gendron/Pisa/References/BB/Brungger99.pdf The parallel search bench ZRAM and its applications] {{Wayback|url=http://www.iro.umontreal.ca/~gendron/Pisa/References/BB/Brungger99.pdf |date=20171111193526 }}, Annals of Operations Research 90 (1999), pp. 45-63.</ref>

<ref name="reinefeld_1993">{{статья
 | автор = Alexander Reinefeld
 | заглавие = Complete Solution of the Eight-Puzzle and the Benefit of Node Ordering in IDA*
 | год = 1993
 | ссылка = http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.40.9889
 | archivedate = 2015-12-14
 | archiveurl = https://web.archive.org/web/20151214011915/http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.40.9889
 }}</ref>

<ref name="kunkle_2001">{{статья
 | автор = Daniel R. Kunkle
 | заглавие = Solving the 8 Puzzle in a Minimum Number of Moves: An Application of the A* Algorithm
 | год = 2001
 | ссылка = http://web.mit.edu/6.034/wwwbob/EightPuzzle.pdf
 | archivedate = 2015-12-11
 | archiveurl = https://web.archive.org/web/20151211155022/http://web.mit.edu/6.034/wwwbob/EightPuzzle.pdf
 }}</ref>

<ref name="korf_1985">{{статья
 | автор = Richard E. Korf
 | заглавие = Depth-first Iterative-Deepening: An Optimal Admissible Tree Search
 | год = 1985
 | ссылка = http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.91.288
 | archivedate = 2015-12-14
 | archiveurl = https://web.archive.org/web/20151214012258/http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.91.288
 }}</ref>

<ref name="culberson_schaeffer_1998">{{статья
 |автор = Joseph C. Culberson, Jonathan Schaeffer
 |заглавие = Pattern Databases
 |год = 1998
 |ссылка = https://webdocs.cs.ualberta.ca/~jonathan/publications/ai_publications/compi.pdf
 |archivedate = 2015-12-08
 |archiveurl = https://web.archive.org/web/20151208125329/https://webdocs.cs.ualberta.ca/~jonathan/publications/ai_publications/compi.pdf
 }}</ref>

<ref name="korf_schultze_2005">{{статья
 | автор = Richard E. Korf, Peter Schultze
 | заглавие = Large-Scale Parallel Breadth-First Search
 | год = 2005
 | ссылка = http://www.aaai.org/Papers/AAAI/2005/AAAI05-219.pdf
 | archivedate = 2016-03-04
 | archiveurl = https://web.archive.org/web/20160304101625/http://www.aaai.org/Papers/AAAI/2005/AAAI05-219.pdf
 }}</ref>

<ref name="taylor_korf_1996">{{статья
 | автор = Richard E. Korf, Larry A. Taylor
 | заглавие = Finding Optimal Solutions to the Twenty-Four Puzzle
 | год = 1996
 | ссылка = http://www.aaai.org/Library/AAAI/1996/aaai96-178.php
 | archivedate = 2015-09-10
 | archiveurl = https://web.archive.org/web/20150910194314/http://www.aaai.org/Library/AAAI/1996/aaai96-178.php
 }}</ref>

<ref name="korf_2000">{{статья
 | автор = Richard E. Korf
 | заглавие = Recent Progress in the Design and Analysis of Admissible Heuristic Functions
 | год = 2000
 | ссылка = http://www.aaai.org/Papers/AAAI/2000/AAAI00-212.pdf
 | archivedate = 2016-03-04
 | archiveurl = https://web.archive.org/web/20160304000754/https://www.aaai.org/Papers/AAAI/2000/AAAI00-212.pdf
 }}</ref>

<ref name="korf_felner_2002">{{статья
 | автор = Richard E. Korf, Ariel Felner
 | заглавие = Disjoint Pattern Database Heuristics
 | год = 2002
 | ссылка = http://www.sciencedirect.com/science/article/pii/S0004370201000923
 | archivedate = 2018-11-26
 | archiveurl = https://web.archive.org/web/20181126155044/https://www.sciencedirect.com/science/article/pii/S0004370201000923
 }}</ref>

<ref name="felner_korf_hanan_2004">{{статья
 | автор = Ariel Felner, Richard E. Korf, Sarit Hanan
 | заглавие = Additive Pattern Database Heuristics
 | год = 2004
 | ссылка = http://www.aaai.org/Library/JAIR/Vol22/jair22-009.php
 | archivedate = 2021-12-01
 | archiveurl = https://web.archive.org/web/20211201071922/https://aaai.org/Library/JAIR/Vol22/jair22-009.php
 }}</ref>

<ref name="10.1.1.519.9720">{{статья
 | автор = Richard E. Korf
 | заглавие = Breadth-first frontier search with delayed duplicate detection
 | год = 2004
 | ссылка = http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.519.9720
 | archivedate = 2015-12-14
 | archiveurl = https://web.archive.org/web/20151214012309/http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.519.9720
 }}</ref>

<ref name="10.1.1.39.6069">{{статья
 | автор = Ralph Udo Gasser
 | заглавие = Harnessing Computational Resources for Efficient Exhaustive Search
 | год = 1995
 | ссылка = http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.39.6069
 | archivedate = 2015-12-14
 | archiveurl = https://web.archive.org/web/20151214011745/http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.39.6069
 }}</ref>

<ref name="10.1.1.55.7558">''Filip R. W. Karlemo and Patric R. J. Östergård'' [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.55.7558 On Sliding Block Puzzles] {{Wayback|url=http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.55.7558 |date=20151001185055 }}, Journal of Combinatorial Mathematics and Combinatorial Computing 34 (2000), 97-107</ref>

<ref name="yang_et_al_2008">''F. Yang, J. Culberson, R. Holte, U. Zahavi and A. Felner'' [http://www.jair.org/papers/paper2486.html A General Theory of Additive State Space Abstractions] {{Wayback|url=http://www.jair.org/papers/paper2486.html |date=20151208063247 }}, Volume 32 (2008), pages 631-662</ref>

<ref name="node/view/223">{{cite web
 |url = http://cubezzz.dyndns.org/drupal/?q=node%2Fview%2F223
 |title = The Fifteen Puzzle can be solved in 43 "moves"
 |author = Bruce Norskog
 |date = 2010-12-08
 |publisher = Domain of the Cube Forum
 |access-date = 2015-12-03
 |archive-date = 2013-12-13
 |archive-url = https://web.archive.org/web/20131213120029/http://cubezzz.dyndns.org/drupal/?q=node%2Fview%2F223
 |deadlink = no
 }}</ref>

<ref name="jaap">{{cite web
 |url = http://www.jaapsch.net/puzzles/fifteen.htm
 |title = 14-15 puzzle / Boss puzzle
 |author = Jaap Scherphuis
 |work = Jaap's Puzzle Page
 |access-date = 2015-12-03
 |archive-date = 2015-12-17
 |archive-url = https://web.archive.org/web/20151217091909/http://www.jaapsch.net/puzzles/fifteen.htm
 |deadlink = no
 }}</ref>

<ref name="fifteensolver">{{cite web
 |url = http://kociemba.org/fifteen/fifteensolver.html
 |title = Fifteen Puzzle Optimal Solver
 |author = Herbert Kociemba
 |archiveurl = https://web.archive.org/web/20151002183638/http://kociemba.org/fifteen/fifteensolver.html
 |archivedate = 2015-10-02
}}</ref>

<ref name="oeis-a087725">{{OEIS long|87725|ru=наибольшее число ходов, которое может потребоваться для обобщения {{times|n|n}} головоломки «пятнашки»}}</ref>

<ref name="oeis-a089484">{{OEIS long|89484|ru=число конфигураций пятнашек, оптимальное решение которых содержит {{mvar|n}} ходов}}</ref>

<ref name="oeis-a151944">{{OEIS long|151944|ru=наибольшее число ходов, которое может потребоваться для обобщения {{times|m|n}} головоломки «пятнашки»}}</ref>

<ref name="twistypuzzles">{{cite web
 |url = http://twistypuzzles.ru/forum/index.php/topic,734.0.html
 |title = Название "Пятнашки"
 |publisher = TwistyPuzzles.RU
 |access-date = 2015-12-08
 |archive-date = 2015-12-10
 |archive-url = https://web.archive.org/web/20151210183400/http://twistypuzzles.ru/forum/index.php/topic,734.0.html
 |deadlink = no
 }}</ref>

<ref name="Gem Puzzle">Jerry Slocum: ''[http://www.indiana.edu/~liblilly/collections/overview/puzzle_docs/Sam_Loyd_Successful_Hoax.pdf Sam Loyd’s Most Successful Hoax] {{Wayback|url=http://www.indiana.edu/~liblilly/collections/overview/puzzle_docs/Sam_Loyd_Successful_Hoax.pdf |date=20151223102701 }} (PDF; 672 kB)''. Vortrag auf: Seventh Gathering for Gardner, March 2006, The Convention of the Association of Game and Puzzle Collectors. Publiziert in: E. Pegg, A.H. Schoen & T. Rodgers: Homage to a Pied Puzzler. A.K. Peters, Wellesley / Massachusetts, 2009, S. 3-21. (hier: S. 4)</ref>

<ref name="etudes-puzzle15">{{cite web
 |url = https://book.etudes.ru/articles/puzzle-15/
 |title = Игра в «15»
 |subtitle = Математическая составляющая
 |publisher = [[Математические этюды]]
 |access-date = 2021-12-22
 |archive-date = 2021-12-22
 |archive-url = https://web.archive.org/web/20211222114142/https://book.etudes.ru/articles/puzzle-15/
 |deadlink = no
 }}</ref>

}}

== Литература ==
; Книги
* {{книга
 |автор = [[Гарднер, Мартин|Гарднер М.]]
 |заглавие = Математические досуги
 |ответственный = Пер. с англ. [[Данилов, Юлий Александрович|Ю. А. Данилова]]. Под ред. [[Смородинский, Яков Абрамович|Я. А. Смородинского]]
 |место = М.
 |издательство = [[Мир (издательство)|Мир]]
 |год = 1972
 |ref = Математические досуги
}}
* {{книга
 |автор = [[Перельман, Яков Исидорович|Перельман Я. И.]]
 |заглавие = Занимательные задачи и опыты
 |место = М.
 |издательство = [[Детская литература (издательство)|Детская литература]]
 |год = 1972
 |ref = Занимательные задачи и опыты
}}
* {{книга
 |заглавие = The 15 Puzzle
 |ссылка = https://archive.org/details/trent_0116405758388
 |автор = Jerry Slocum and Dic Sonneveld
 |год = 2006
 |isbn = 1-890980-15-3
 |ref = The 15 Puzzle
}}
* {{книга
 |заглавие = По следам Пифагора: Занимательная математика
 |автор = {{нп5|Щепан Еленьский||pl|Szczepan Jeleński}}
 |оригинал = Śladami Pitagorasa
 |ответственный = Перевод с польского Г. Ф. Боярской, Б. В. Боярского и А. А. Якушева
 |место = М.
 |издательство = [[Детгиз]]
 |год = 1961
 |страницы = 231—233
 |ref = По следам Пифагора
}}
* {{книга
 |автор = Clarke B. R.
 |заглавие = Puzzles for Pleasure
 |ссылка = https://books.google.com/books?id=vOlM0CBKAb0C&pg=PA11
 |издательство = Cambridge University Press
 |год = 1994
 |isbn = 0-521-46634-2
 |ref = Puzzles for Pleasure
}}
* {{книга
 |автор = Люгер, Джордж Ф.
 |заглавие = Искусственный интеллект: стратегии и методы решения сложных проблем
 |оригинал = Artificial Intelligence: Structures and Strategies for Complex Problem Solving
 |издание = 4-е издание
 |год = 2003
 |издательство = {{ifexist|Издательский дом «Вильямс»}}
 |страниц = 864
 |isbn = 5-8459-0437-4
 |isbn2 = 978-5-845-90437-9
 |ref = Искусственный интеллект: стратегии и методы решения сложных проблем
 |ссылка = https://books.google.com/books?id=jaoDX9-e_McC&pg=PA43
}}
* {{книга
 |автор = Стюарт Рассел, [[Норвиг, Питер|Питер Норвиг]]
 |заглавие = Искусственный интеллект: современный подход
 |издание = 2-е изд
 |оригинал = Artificial Intelligence: A Modern Approach
 |место = М.
 |издательство = {{ifexist|Издательский дом «Вильямс»}}
 |год = 2006
 |страниц = 1408
 |isbn = 5-8459-0887-6
 |ref = Искусственный интеллект: современный подход
}}
* {{книга
 |автор = Мозговой М. В.
 |заглавие = Занимательное программирование: Самоучитель
 |ссылка = https://books.google.com/books?id=JO9-7RiwldcC&pg=PA171
 |место = СПб.
 |издательство = [[Питер (издательство)|Питер]]
 |год = 2005
 |страниц = 208
 |isbn = 5-94723-853-5
 |ref = Занимательное программирование: Самоучитель
}}
; Статьи
* {{h|Johnson & Story|1879|3=Wm. Woolsey Johnson, and William E. Story. 1879. [https://www.jstor.org/stable/2369492 «Notes on the „15“ Puzzle»]. ''American Journal of Mathematics'' 2 (4). The Johns Hopkins University Press: 397—404. doi:10.2307/2369492.}}
* {{статья
 |заглавие = The 15 Puzzle: How it Drove the World Crazy by Jerry Slocum and Dic Sonneveld
 |автор = Aaron Archer
 |ссылка = http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.145.2797
 |ref = Review of ''The 15 Puzzle'' by Aaron Archer
}}
* {{статья
 |заглавие = Generating Admissible Heuristics by Criticizing Solutions to Relaxed Models
 |автор = Othar Hansson, Andrew E. Mayer, Mordechai M. Yung
 |год = 1985
 |ссылка = http://academiccommons.columbia.edu/download/fedora_content/download/ac:141290/CONTENT/cucs-219-85.pdf
 |ref = Generating Admissible Heuristics by Criticizing Solutions to Relaxed Models
}}

== Ссылки ==
{{Навигация }}
* [http://www.brian-borowski.com/Software/Puzzle/ Optimal 8/15-Puzzle Solver] // brian-borowski.com (Java source)
* [http://www.ic-net.or.jp/home/takaken/e/15pz/ «15puzzle Optimal solver» for Windows] — Ken’ichiro Takahashi (takaken)
* [http://kociemba.org/fifteen/fifteensolver.html Fifteen Puzzle Optimal Solver] {{Wayback|url=http://kociemba.org/fifteen/fifteensolver.html |date=20151002183638 }} — Herbert Kociemba`s Homepage
* [http://пятнашки.com Пятнашки.com] — Играть в пятнашки онлайн

{{NP-полные задачи}}

[[Категория:Перестановочные головоломки]]
[[Категория:Теория графов]]
[[Категория:Механические головоломки]]