Как играть в головоломку пятнашки


Игра в 15 — Википедия

У этого термина существуют и другие значения, см. 15 (значения). У слова «Пятнашки» есть и другие значения; см. Пятнашки.

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

Авторство[править | править код]

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

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

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

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

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

Распространение[править | править код]

В США[править | править код]

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

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

Остерегайтесь подделок. Убедитесь, что вы приобретаете эту, единственную аккуратно сделанную, тщательно испытанную головоломку.

Оригинальный текст (англ.): 

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.

В феврале 1880 года в разных газетах начали появляться подробные статьи, посвящённые головоломке[27]. Ряд журналов национального масштаба, включая The Youth's Companion[en], Illustrated Newspaper, Harper’s Weekly, Scientific American, The Independent[en], в течение нескольких недель публиковали объявления о головоломке[28]. Новости о головоломке распространялись в другие города. К началу марта многие производители выпускали версии головоломки под разными названиями[18].

12 февраля газета Boston Herald[en] опубликовала поэму о головоломке, за которой последовал ряд произведений в стихотворной форме в других газетах[29]. 17 февраля в газете Rochester Democrat and Chronicle[en] была опубликована статья о влиянии головоломки на общество. 20 февраля в нью-йоркском журнале Ontario County Journal появилась заметка следующего содержания[30]:

Вероятно, Н. П. Чепмэн, почтмейстер из Канастоты, в течение ближайших нескольких недель будет самым проклинаемым человеком в стране. Он изобрёл Игру в 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'.

17 марта 1880 года газета Boston Daily Advertiser[en] опубликовала статью, которая описывала «начало безумия» в Бостоне три месяца тому назад (в декабре 1879)[27].

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

За пределами США[править | править код]

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

В России[править | править код]

25 апреля 1880 года газета St. Petersburg Herold[de] на немецком языке разместила объявление «Neues Spiel — Das Spiel der Funfzehn»[33] («Новая игра — Игра в 15»).

The Gem Puzzle[править | править код]

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

Поместите блоки в коробочку беспорядочным образом, затем перемещайте, пока они не выстроятся в правильном порядке.

Оригинальный текст (англ.): 

Place the blocks in the box irregularly, then move until in regular order.

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

Головоломка 14-15[править | править код]

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

  • Рис. 1. В начальном положение в головоломке 14-15 плитки 14 и 15 поменяны местами

  • Рис. 2. Это расположение недостижимо из начального расположения головоломки 14-15 (Рис. 1)

  • Рис. 3. Но это расположение достижимо из начального расположения головоломки 14-15 (Рис. 1)

  • Рис. 4. Ещё одно достижимое расположение для головоломки 14-15 (Рис. 1)

Современные модификации[править | править код]

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

  • Слон спит стоя. А вы?

  • На английском языке[7]

  • На немецком языке

Магический квадрат[править | править код]

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

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

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

Нерешаемая комбинация
N=∑i=115ni+e{\displaystyle N=\sum _{i=1}^{15}n_{i}+e}

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

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

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

4 × 4[править | править код]

Любую из 10 461 394 944 000 разрешимых конфигураций «классической» головоломки 4 × 4 можно перевести в начальную не более чем за 80 ходов, если под ходом понимать перемещение одной плитки[41][42][37][43], или не более чем за 43 хода, если под ходом понимать одновременное перемещение сплошного ряда из не более чем трёх плиток[44]. Только 17 из всех разрешимых конфигураций не могут быть решены менее чем за 80 ходов, то есть требуют 80 перемещений отдельных плиток для решения[42][37][45]; только 16 разрешимых конфигураций требуют 43 перемещений сплошных рядов плиток[44].

5 × 5[править | править код]

В 1995 году было показано, что любая конфигурация головоломки 5 × 5 может быть решена не более чем за 219 одиночных ходов[46], то есть была получена верхняя граница в 219 ходов для длины оптимального решения произвольной конфигурации. В 1996 году была найдена конфигурация, которая не может быть решена меньше чем за 112 перемещений плиток[47]. В 2000 году верхняя граница была улучшена до 210 ходов[48]; в 2011 году для «числа Бога» головоломки 5 × 5 были получены нижняя граница в 152 хода и верхняя граница в 208 ходов[43].

Текущие результаты[править | править код]

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

Размер Целевая конфигурация Число решаемых
конфигураций
«Длинные»
ходы[К 1]
«Число Бога» Число
«антиподов»[К 2]
2 × 2 пустая ячейка в углу 12 нет 6[48][49] 1[48]
2 × 3 пустая ячейка в углу 360 нет 21[48][49] 1[48]
2 × 4 пустая ячейка в углу 20 160 нет 36[48][49] 1[48]
2 × 5 пустая ячейка в углу 1 814 400 нет 55[50][49] 2[50]
2 × 6 пустая ячейка в углу 239 500 800 нет 80[51][49] 2[51]
2 × 7 пустая ячейка в углу 43 589 145 600 нет 108[52][49]
2 × 8 пустая ячейка в углу 10 461 394 944 000 нет 140[52][49]
3 × 3 пустая ячейка в углу 181 440 нет 31[48][43][49] 2[48][53]
да 24[43]
3 × 4 пустая ячейка в углу 239 500 800 нет 53[48][49] 18[48]
3 × 5 пустая ячейка в углу 653 837 184 000 нет 84[49]
3 × 5 пустая ячейка в центре 653 837 184 000 нет 84[54]
4 × 4 пустая ячейка в углу 10 461 394 944 000 нет 80[42][37][43][49] 17[42][37][45]
да 43[44] 16[44]
5 × 5 пустая ячейка в углу 7,7556⋅1024 нет 152[43] — 208[43]

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

«Пятнашки» разных размеров с 1960-х годов регулярно используются в исследованиях в области ИИ; в частности, на них испытываются и сравниваются алгоритмы поиска в пространстве состояний с разными эвристическими функциями[55][56][57][58] и другими оптимизациями, влияющими на число посещённых в процессе поиска конфигураций головоломки (вершин графа). В исследованиях так или иначе использовались головоломки размеров 3 × 3[59][60], 4 × 4[61][62][42], 5 × 5[47][63][64], 6 × 6[65], 2 × 7[54], 3 × 5[54].

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

  1. пространство состояний классических пятнашек является доступным для анализа, но всё же достаточно большим, чтобы представлять интерес и использовать и сравнивать разнообразные эвристики[68];
  2. не известен ни один алгоритм, находящий кратчайшее решение для обобщённых пятнашек n × n за разумное время[39];
  3. сама задача поиска кратчайшего решения для пятнашек проста для понимания и программного манипулирования[55][39]; головоломка поддаётся описанию с помощью небольшого и чётко определённого набора простых правил[69][39];
  4. для моделирования головоломки не требуется передачи семантических тонкостей, присущих более сложным предметным областям[70];
  5. задачи с пятнашками — удачные представители класса проблем, в которых требуется найти кратчайший путь между двумя заданными вершинами неориентированного конечного графа[39];
  6. размер графа поиска зависит от размера головоломки n экспоненциально, хотя любое состояние можно описать с затратой O(n2) памяти[39];
  7. одна и та же эвристическая функция может применяться ко всем состояниям, так как все состояния описываются одинаково; в реальных применениях разные состояния могут иметь разные описания, что требует введения нескольких эвристик[71];
  8. использование в исследованиях игр и головоломок не порождает финансовых или этических проблем[70].

Эвристический поиск[править | править код]

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

Головоломка 3 × 3 легко решается любым алгоритмом поиска. Произвольные конфигурации пятнашек 4 × 4 решаются с помощью современных алгоритмов поиска за несколько миллисекунд[56]. Для оптимального решения головоломки 5 × 5 требуются больши́е затраты ресурсов даже с применением современных компьютеров и алгоритмов[56][63]; процесс поиска может длиться несколько недель и генерировать триллионы узлов[64][65]. Оптимальное решение произвольных конфигураций головоломки 6 × 6 до сих пор находится за пределами возможностей[65], в связи с чем в исследованиях делаются лишь попытки предсказать относительную производительность алгоритма IDA* с разными эвристическими функциями[65].

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

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

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

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

Для быстрого поиска оптимального решения головоломки 4 × 4, а также для возможности находить оптимальное решение головоломки 5 × 5 в разумные сроки, разработаны эвристики, основанные на базах данных образцов (pattern databases)[62][63][58]. Подобные эвристики являются по сути заранее вычисленными и хранящимися в оперативной памяти таблицами, в которых закодированы оптимальные решения для подзадач; каждая из подзадач сводится к перемещению в целевые позиции определённой группы плиток[62]. Эти эвристики также могут быть применены к кубику Рубика и другим головоломкам[63].

  1. ↑ В столбце указано, считается ли за один ход одновременное перемещение нескольких плиток, образующих сплошной вертикальный или горизонтальный ряд.
  2. ↑ «Антиподы» — конфигурации головоломки, требующие наибольшего числа ходов для решения
  1. ↑ Математические досуги, 1972, с. 401.
  2. 1 2 Занимательные задачи и опыты, 1972, с. 365.
  3. ↑ Искусственный интеллект: стратегии и методы решения сложных проблем, 2003, с. 43, 114, 163, 166, 168, 181-182.
  4. 1 2 Название "Пятнашки" (неопр.). TwistyPuzzles.RU.
  5. Владимир Белов. Головоломки из близкой дали. Часть 2 (неопр.). Компьютерра (18 января 2000). Архивировано 28 ноября 2015 года.
  6. Cyclopedia of Puzzles, p. 235
  7. 1 2 3 Jaap Scherphuis. 14-15 puzzle / Boss puzzle (неопр.). Jaap's Puzzle Page.
  8. ↑ The 15 Puzzle, 2006.
  9. 1 2 3 Review of The 15 Puzzle by Aaron Archer, p. 1.
  10. ↑ Puzzles for Pleasure, 1994, p. 10—12.
  11. ↑ The 15 Puzzle, 2006, p. 76.
  12. ↑ Puzzles for Pleasure, 1994, p. 11.
  13. 1 2 3 4 The 15 Puzzle, 2006, p. 109.
  14. ↑ Review of The 15 Puzzle by Aaron Archer, p. 1, 3.
  15. ↑ The 15 Puzzle, 2006, p. 98—99.
  16. ↑ The 15 Puzzle, 2006, p. 103—104, 109.
  17. ↑ The 15 Puzzle, 2006, p. 11, 109.
  18. 1 2 Review of The 15 Puzzle by Aaron Archer, p. 2.
  19. 1 2 Jerry Slocum: Sam Loyd’s Most Successful Hoax (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)
  20. ↑ The 15 Puzzle, 2006, p. 100—101.
  21. ↑ The 15 Puzzle, 2006, p. 101.
  22. ↑ E. U. Kinsey. Puzzle-Blocks. No. 207124. Patented Aug. 20, 1878 (неопр.).
  23. ↑ The 15 Puzzle, 2006, p. 102.
  24. ↑ Review of The 15 Puzzle by Aaron Archer, p. 3.
  25. ↑ The 15 Puzzle, 2006, p. 14—15.
  26. ↑ The 15 Puzzle, 2006, p. 15—16.
  27. 1 2 The 15 Puzzle, 2006, p. 12.
  28. ↑ The 15 Puzzle, 2006, p. 20.
  29. ↑ The 15 Puzzle, 2006, p. 21.
  30. ↑ The 15 Puzzle, 2006, p. 24, 98.
  31. ↑ The 15 Puzzle, 2006, p. 59.
  32. ↑ The 15 Puzzle, 2006, p. 60.
  33. ↑ The 15 Puzzle, 2006, p. 63.
  34. ↑ Занимательные задачи и опыты, 1972, с. 370.
  35. ↑ Занимательные задачи и опыты, 1972, с. 371.
  36. ↑ Sam Loyd; Martin Gardner: Mathematical puzzles of Sam Loyd. Dover Pubs., New York 1959, pp. 19 und 20. Google books
  37. 1 2 3 4 5 Herbert Kociemba. Fifteen Puzzle Optimal Solver (неопр.). Архивировано 2 октября 2015 года.
  38. Slocum J., Weisstein E. W. 15 Puzzle (англ.) на сайте Wolfram MathWorld.
  39. 1 2 3 4 5 6 7 Ratner D., Warmuth M. K. Finding a Shortest Solution for the N × N Extension of the 15-PUZZLE Is Intractable // National Conference on Artificial Intelligence, 1986.
  40. Ratner D., Warmuth M. The (n2−1)-puzzle and related relocation problems // Journal of Symbolic Computation. — 1990. — Т. 10, № 2. — С. 111–137. — doi:10.1016/S0747-7171(08)80001-6.
  41. ↑ A. Brüngger, A. Marzetta, K. Fukuda and J. Nievergelt, The parallel search bench ZRAM and its applications, Annals of Operations Research 90 (1999), pp. 45-63.
  42. 1 2 3 4 5 Richard E. Korf, Peter Schultze. Large-Scale Parallel Breadth-First Search. — 2005.
  43. 1 2 3 4 5 6 7 Последовательность A087725 в OEIS: наибольшее число ходов, которое может потребоваться для обобщения n × n головоломки «пятнашки»
  44. 1 2 3 4 Bruce Norskog. The Fifteen Puzzle can be solved in 43 "moves" (неопр.). Domain of the Cube Forum (8 декабря 2010).
  45. 1 2 Последовательность A089484 в OEIS: число конфигураций пятнашек, оптимальное решение которых содержит n ходов
  46. Ralph Udo Gasser. Harnessing Computational Resources for Efficient Exhaustive Search. — 1995.
  47. 1 2 Richard E. Korf, Larry A. Taylor. Finding Optimal Solutions to the Twenty-Four Puzzle. — 1996.
  48. 1 2 3 4 5 6 7 8 9 10 11 Filip R. W. Karlemo and Patric R. J. Östergård On Sliding Block Puzzles, Journal of Combinatorial Mathematics and Combinatorial Computing 34 (2000), 97-107
  49. 1 2 3 4 5 6 7 8 9 10 11 Последовательность A151944 в OEIS: наибольшее число ходов, которое может потребоваться для обобщения m × n головоломки «пятнашки»
  50. 1 2 Последовательность A090036 в OEIS
  51. 1 2 Последовательность A090167 в OEIS
  52. 1 2 Последовательность A151943 в OEIS
  53. ↑ Последовательность A089473 в OEIS
  54. 1 2 3 Richard E. Korf. Breadth-first frontier search with delayed duplicate detection. — 2004.
  55. 1 2 Искусственный интеллект: стратегии и методы решения сложных проблем, 2003, с. 114.
  56. 1 2 3 Искусственный интеллект: современный подход, 2006, с. 118.
  57. 1 2 Generating Admissible Heuristics by Criticizing Solutions to Relaxed Models, 1985.
  58. 1 2 F. Yang, J. Culberson, R. Holte, U. Zahavi and A. Felner A General Theory of Additive State Space Abstractions Архивная копия от 8 декабря 2015 на Wayback Machine, Volume 32 (2008), pages 631-662
  59. Alexander Reinefeld. Complete Solution of the Eight-Puzzle and the Benefit of Node Ordering in IDA*. — 1993.
  60. Daniel R. Kunkle. Solving the 8 Puzzle in a Minimum Number of Moves: An Application of the A* Algorithm. — 2001.
  61. Richard E. Korf. Depth-first Iterative-Deepening: An Optimal Admissible Tree Search. — 1985.
  62. 1 2 3 Joseph C. Culberson, Jonathan Schaeffer. Pattern Databases. — 1998.
  63. 1 2 3 4 Richard E. Korf. Recent Progress in the Design and Analysis of Admissible Heuristic Functions. — 2000.
  64. 1 2 Richard E. Korf, Ariel Felner. Disjoint Pattern Database Heuristics. — 2002.
  65. 1 2 3 4 Ariel Felner, Richard E. Korf, Sarit Hanan. Additive Pattern Database Heuristics. — 2004.
  66. ↑ Искусственный интеллект: стратегии и методы решения сложных проблем, 2003, с. 43, 114, 163.
  67. ↑ Generating Admissible Heuristics by Criticizing Solutions to Relaxed Models, 1985, p. 3.
  68. ↑ Искусственный интеллект: стратегии и методы решения сложных проблем, 2003, с. 114, 163.
  69. ↑ Искусственный интеллект: стратегии и методы решения сложных проблем, 2003, с. 43, 163.
  70. 1 2 Искусственный интеллект: стратегии и методы решения сложных проблем, 2003, с. 43.
  71. ↑ Искусственный интеллект: стратегии и методы решения сложных проблем, 2003, с. 163.
  72. Borowski B. S. Optimal 8/15-Puzzle Solver (неопр.). // Brian's Project Gallery. Дата обращения 29 июля 2013. Архивировано 17 августа 2013 года.
  73. ↑ Искусственный интеллект: стратегии и методы решения сложных проблем, 2003, с. 156.
  74. ↑ Занимательное программирование: Самоучитель, 2005, с. 171.
  75. 1 2 Generating Admissible Heuristics by Criticizing Solutions to Relaxed Models, 1985, p. 4—5.
  76. ↑ Искусственный интеллект: стратегии и методы решения сложных проблем, 2003, с. 157.
  77. ↑ Занимательное программирование: Самоучитель, 2005, с. 173.
Книги

Пятнашки - Как собрать пятнашки

Как собрать пятнашки. Часть 1

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

Если вдруг вы не знаете, как собрать пятнашки или столкнулись с трудными задачами или просто нет времени на долгий поиск решения, то в этих статьях вы сможете прочитать некоторые решения и изучить способы сборки.

Сразу скажу, что здесь мы не ставим целью поиск наиболее быстрого и оптимального способа (все равно пятнашки легко собираются меньше чем за минуту).

Сначала несколько вступлений. Чтобы описывать последовательность действий в виде текста, усвоим такие понятия как «позиция» и «ход». Позиция представляет собой расположение 15 фишек и пустой клетки на поле для игры. Ее можно описывать в виде таблицы:

 

Все предельно понятно

 

Ходы мы будем обозначать как фишку с номером, которая передвигается на пустое место. С другой стороны (с точки зрения математики) ход можно описать как «движение пустой клетки». Последовательность ходов будем писать через запятую, через тире либо с нумерацией ходов. Фишка с номером обозначается как «фишка…» либо по обозначению ее числа в разговорной форме (однерка, семерка, одиннадцатая, …), а позиция на доске обозначается как ее номер в собранном расположении (последнее пустое место – позиция 16).

Например, на рисунке пустая клетка находится в нижнем ряду второе место (место [4 , 2]). Если на нее передвинуть фишку с номером «6», то мы так и запишем ход: «6». Если потом на освободившееся место сдвинуть единичку, а затем сдвинуть фишку семь, то такую последовательность ходов можно записать как «6-1-7» либо «1. 6  2. 1  3. 7  ». Чтобы не путать обозначения номера хода и фишки, можно придумать некое понятное обозначение последовательности ходов (если номера ходов важны) вроде «1-6  2-1  3-7  » или «1. 6/ 2. 1/3. 7/  ».

И небольшая заметка: если вы освоите сборку пятнашек одним методом, то вам будет легко освоить и другие способы, ведь закономерности движения фишек вам уже будут знакомы.

ДАЛЕЕ

Игра Пятнашки прохождение / 15 Puzzle

Для просмотра онлайн кликните на видео ⤵

Как собрать Пятнашки? Скоростная сборка 15-Puzzle! Подробнее

Как собрать пятнашки ? Самый простой метод Подробнее

Обзор магнитных пятнашек - 15-Puzzle для сборки на скорость! Подробнее

Как собрать пятнашки. Подробнее

АСМР видео. Научу играть в пятнашки. Подробнее

Уроки по Scratch. Делаем игру Пятнашки (Пазл 15) на Скретч Подробнее

C# Микроигры Игра Пятнашки, вторая часть Подробнее

Обзор игры-головоломки 12 замков:Пластилиновая комната.комната . Прошёл за одну серию. Подробнее

Как собрать пятнашки вслепую методом 3C8 (15-puzzle bld tutorial rus) Подробнее

Как собрать пятнашки, самый простой метод / Обучение Подробнее

Советская игра 15 она же пятнашки Подробнее

КАК Открыть ЭТУ ДВЕРЬ? МИЛАНА И ПАПА Ищут КЛЮЧИ в КВАРТИРЕ! Видео игра от FFGTV Подробнее

Математика для всех. Алексей Савватеев. Лекция 1.8. Решение пятнашек - 2 Подробнее

СКОРОСТНЫЕ ПЯТНАШКИ СВОИМИ РУКАМИ Подробнее

Как ЗАМАГНИТИТЬ Пятнашки | Как тебе такое, Кирюша? Подробнее

C# Игра 15 - Урок 1 - Интерфейс игры Подробнее

Игрушка головоломка из СССР Подробнее

быстро собирает пятнашки Подробнее

Фиксики Игра - Пятнашки | Fixiki Game - Spots | FixiPlay Подробнее

Нестандартные пятнашки

Кроме перечисленных в других разделах пятнашек, в СССР производилось ещё 7 типов подобных головоломок:

1. "Логические кубики".
2.1. "Самый короткий путь".
2.2. "Упрямый осёл" (Рыжий осёл).
2.3. "Забей шайбу".
3. "Смекалка".
4. "4 по 4".
5. "Радуга".
6. "Тигры в клетке".
7. "Вятка-Киров".

1. "Логические кубики".
При первом взгляде на "Логические кубики" их можно отнести к выпадающим, классическим пятнашкам.
Однако, стоит присмотреться повнимательней. Благодаря хитрой конструкции фишек, позволяющей менять изображение на них, вместо одной игры мы можем получить 10!

В моей коллекции два варианта этой головоломки, всего же их было выпущено 8 (по крайней мере так написано в инструкции):

1.1 Логические кубики-"Б". Инструкция в формате PDF

1.2 Логические кубики-"2". Инструкция в формате PDF

2. Самый короткий путь, Упрямый осёл, Забей шайбу.
Эти головоломки гораздо сложнее обычных пятнашек. Их главное отличие от всех вышеперечисленных пятнашек, в разной форме фишек.
Вот оригинальная инструкция с правилами игры:

В СССР эта головоломка выпускалась разными производителями с разными названиями:

2.1. "Самый короткий путь". Варианты

2.2. "Упрямый осёл" (Рыжий осёл). Варианты

2.3. "Забей шайбу".

3. "Смекалка". Варианты
"Смекалка" похожа на предыдущую головоломку, но у неё другой набор фишек.

4. "4 по 4".
Несложная головоломка, целью которой было упорядочить цветные фишки. Выпускалась, так же как и пятнашки, разными производителями под множеством названий.
Кроме стандартной версии головоломки, существовали ещё два усложнённых варианта, с перегородкой и с нумерацией фишек.

4.1. "Стандартные" 4 по 4. Варианты

4.2. "4 по 4" с перегородками. Варианты

4.3. "4 по 4" с нумерацией. Варианты

5. "Радуга".
По сути, это те же пятнашки, только на поле 5 на 5.

6. "Тигры в клетке".
То же пятнашки 5 на 5, но с интересно поставленными задачами.

7. "Вятка-Киров". Варианты


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