Алгоритм сборки пятнашек
Для тех, кто всё таки не смог понять как собирать эту головоломку, вот достаточно простой алгоритм сборки пятнашек. Этот способ будет работать на любом размере головоломки.
Кстати купить пятнашки можно на my-shop.ru.
Стадия 1: сборка верхней строки.
В итоге вы соберёте строку слева на право.
Найдите следующую часть, которую вы хотите поместить в верхнюю строку.
Если это не последняя цифра строки, достаточно просто правильно её разместить, просто держите в уме следующие заметки:
- Никогда не трогайте части собранные ранее.
- Чтобы сдвинуть цифру в определённом направлении, двигайте другие части по кругу, пока пропуск не окажется перед вашей цифрой на стороне, в которую вы хотите его сдвинуть. Далее вы можете сдвинуть цифру.
Если последняя часть строки уже не на месте, переместите её на позицию прямо под её правильным местом, с пробелом сразу под ней. Далее двигайте части в следующих направлениях:
Вниз, вниз, право, вверх, лево, вверх,право, вниз, лево, вверх. Это должно поместить часть на место. Заметим, что это временно нарушает последовательность частей, собранных ранее.
Стадия 2: Сборка остальных частей.
Используйте технику, описанную в стадии 1, чтобы последовательно собрать каждую строку, кроме двух последних.
Поверните головоломку на четверть поворота вправо. Левая колонка из двух строк теперь стала верхней строкой.
Используйте технику из стадии 1, чтобы последовательно собрать каждую строку, пока их не останется две. Это значит, что осталось собрать квадрат 2 на 2.
Двигайте части оставшегося квадрата по кругу, пока одна из частей не встанет на своё место, и пробел не окажется на правильном месте. Две другие части так же должны автоматически выстроиться на свои места.
Если осталось две части которые нужно поменять местами, то головоломку нельзя собрать пока две другие части так же не будут обменены местами. Если где-то в головоломке есть ещё две части, которые нужно поменять, то вам придётся собирать головоломку сначала.
Если вы хотите собрать головоломку так, чтобы пробел остался в месте отличном от нижнего правого угла, то вы можете использовать тот же метод. Когда окажется. что не собранная строка должна будет иметь пропуск, переверните головоломку вверх ногами и начните её собирать с другого конца. В конце концов не собранная область опять сократится до квадрата 2 на 2, но в этом случае он не будет лежать в нижнем правом углу.
Существуют более быстрые пути сборки последних двух частей строки. Один хороший способ заключается в том, чтобы разместить последнюю часть в предпоследнюю позицию строки и затем поставить предпоследнюю часть строки на место (которая сместит последнюю часть на своё законное место).
Игра в 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] :
В феврале 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] :
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] :
В этой версии задача оказывалась неразрешимой ровно в половине случаев.
Головоломка 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> . Будем считать n i = k <displaystyle n_=k> , то есть если после костяшки с i <displaystyle i> -м числом нет чисел, меньших i <displaystyle i> , то k = 0 <displaystyle k=0> . Также введем число e <displaystyle e> — номер ряда пустой клетки (считая с 1). Если сумма
является нечётной, то решения головоломки не существует [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] .
Текущие результаты [ править | править код ]
В таблице сведены данные для ряда обобщений «пятнашек». Когда точный результат неизвестен, приводятся лучшие известные оценки снизу и сверху в форме lb — ub .
| Размер | Целевая конфигурация | Число решаемых конфигураций | «Длинные» ходы [К 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⋅10 24 | нет | 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] :
- пространство состояний классических пятнашек является доступным для анализа, но всё же достаточно большим, чтобы представлять интерес и использовать и сравнивать разнообразные эвристики [68] ;
- не известен ни один алгоритм, находящий кратчайшее решение для обобщённых пятнашек n × n за разумное время [39] ;
- сама задача поиска кратчайшего решения для пятнашек проста для понимания и программного манипулирования [55][39] ; головоломка поддаётся описанию с помощью небольшого и чётко определённого набора простых правил [69][39] ;
- для моделирования головоломки не требуется передачи семантических тонкостей, присущих более сложным предметным областям [70] ;
- задачи с пятнашками — удачные представители класса проблем, в которых требуется найти кратчайший путь между двумя заданными вершинами неориентированного конечного графа [39] ;
- размер графа поиска зависит от размера головоломки n экспоненциально, хотя любое состояние можно описать с затратой O ( n 2 ) памяти [39] ;
- одна и та же эвристическая функция может применяться ко всем состояниям, так как все состояния описываются одинаково; в реальных применениях разные состояния могут иметь разные описания, что требует введения нескольких эвристик [71] ;
- использование в исследованиях игр и головоломок не порождает финансовых или этических проблем [70] .
Эвристический поиск [ править | править код ]
В качестве алгоритма поиска может использоваться алгоритм A*, >[72] , поиск в ширину.
Головоломка 3 × 3 легко решается любым алгоритмом поиска. Произвольные конфигурации пятнашек 4 × 4 решаются с помощью современных алгоритмов поиска за несколько миллисекунд [56] . Для оптимального решения головоломки 5 × 5 требуются больши́е затраты ресурсов даже с применением современных компьютеров и алгоритмов [56] [63] ; процесс поиска может длиться несколько недель и генерировать триллионы узлов [64] [65] . Оптимальное решение произвольных конфигураций головоломки 6 × 6 до сих пор находится за пределами возможностей [65] , в связи с чем в исследованиях делаются лишь попытки предсказать относительную производительность алгоритма >[65] .
Одна из самых простых эвристик для пятнашек может быть выражена следующим образом [73] [74] [75] :
Число ходов, требуемых для решения, не меньше, чем число плиток, находящихся не на своих местах.
Верность утверждения, то есть допустимость эвристической функции «число плиток, находящихся не на своих местах», следует из того, что за один ход может быть поставлена на место только одна плитка. Эта эвристика не использует всю имеющуюся информацию: например, она не принимает во внимание расстояния, на которые должны быть перемещены отдельные плитки.
Более «умная» эвристика сопоставляет каждому расположению плиток сумму расстояний от текущей позиции каждой плитки до её целевой позиции [76] . В литературе эта эвристика встречается под именем «манхэттенское расстояние» (Manhattan distance) [75] [77] . Допустимость функции следует из того, что за один ход перемещается только одна фишка, и расстояние между этой фишкой и её конечной позицией изменяется на 1. Тем не менее, эта эвристика также не использует всю имеющуюся информацию, из-за того, что в одной позиции не могут находиться одновременно две плитки. Существуют более информированные варианты «манхэттенского расстояния», такие, как Linear Conflict [57] .
Для быстрого поиска оптимального решения головоломки 4 × 4, а также для возможности находить оптимальное решение головоломки 5 × 5 в разумные сроки, разработаны эвристики, основанные на базах данных образцов (pattern databases) [62] [63] [58] . Подобные эвристики являются по сути заранее вычисленными и хранящимися в оперативной памяти таблицами, в которых закодированы оптимальные решения для подзадач; каждая из подзадач сводится к перемещению в целевые позиции определённой группы плиток [62] . Эти эвристики также могут быть применены к кубику Рубика и другим головоломкам [63] .
IT — это прекрасно!
Страницы
Интеллектуальные системы. Алгоритм A* и игра "Пятнашки"
Между тем, красота и волшебство программирования для многих (я уверен, что не одинок в этом) в полной мере раскрывается в решении сложных алгоритмических задач, так редко встречающихся в повседневной практике. И раз уж "гора не идет к Магомету", то Магомет придумает себе задачку самостоятельно!
В качестве задачки для разминки мозгов, я предлагаю попытаться научить компьютер собирать известную головоломку "Пятнашки".
Пятна́шки — популярная головоломка, придуманная в 1878 году Ноем Чепмэном. Представляет собой набор одинаковых квадратных костяшек с нанесёнными числами, заключённых в квадратную коробку. Длина стороны коробки в четыре раза больше длины стороны костяшек для набора из 15 элементов (и в три раза больше для набора в 8 элементов), соответственно в коробке остаётся незаполненным одно квадратное поле. Цель игры — перемещая костяшки по коробке добиться упорядочивания их по номерам, желательно сделав как можно меньше перемещений.
Ключом, к решению поставленной задачи, станет известный алгоритм поиска по первому наилучшему совпадению на графе А*. Чтобы несколько упростить изложение задачи, я буду рассматривать головоломку с полем размером 3 х 3.
Весь процесс поиска решения в "Пятнашках" можно представить как задачу поиска на графе. Вершинами такого графа будут состояния поля головоломки, полученные в результате перемещения костяшек:
Поиск решения можно свести к поиску терминального состояния игрового поля (обычно, в качестве терминальной, выбирается расстановка костяшек, упорядоченных по возрастанию слева направо, сверху вниз).
Для решения задачи поиска терминальной вершины на графе можно использовать алгоритмы полного перебора (поиск в глубину или ширину), но количество возможных решений(возможных перестановок) скорее всего окажется на столько велико, что результат полного перебора не удастся увидеть до пенсии.
Алгоритм A* позволяет существенно сократить количество состояний для перебора, путем применения некоторой дополнительной информации, эвристики. В качестве такой информации предлагается брать предполагаемое количество перестановок, необходимых для получения терминального состояния.
Чтобы разобраться, как именно A* позволяет выполнять поиск на графе, рекомендую прочитать статью Алгоритм A* для новичков. Материала на тему этого алгоритма написано так много, что у меня нет желания останавливаться на изложении деталей его реализации, но тем не менее, для дальнейшего понимания происходящего понимание алгоритма A* необходимо. Поэтому, вкратце, я все таки изложу последовательность действий, предпринимаемых алгоритмом, для поиска терминального состояния на примере решения выбранной головоломки.
Алгоритм A* предполагает наличие двух списков вершин графа: открытого и закрытого. В первом находятся вершины, еще не проверенные алгоритмом, а во втором те вершины, которые уже встречались в ходе поиска решения.
На каждом новом шаге, из списка открытых вершин выбирается вершина с наименьшим весом. Вес (F) каждой вершины вычисляется как сумма расстояния от начальной вершины до текущей (G) и эвристическое предположение о расстоянии от текущей вершины, до терминальной (H). F i = G i + H i , где i — текущая вершина (состояние игрового поля).
Для "Пятнашек" можно сделать предположение, что для достижения терминальной вершины, необходимо выполнить перемещений не меньше, чем количество костяшек, находящихся не на своих местах, а расстояние от начальной вершины до текущей рассчитывать как количество сделанных перестановок:
Далее, для выбранной вершины порождаются дочерние вершины(состояния, которые могут быть получены перемещением костяшек на пустую клетку). Каждая вершина имеет ссылку на родительскую, т.е. "помнит" из какого состояния в нее перешли.
Выполняется перебор дочерних вершин. Каждая дочерняя вершина проверяется на предмет наличия в списке закрытых. Если вершина не встречалась ранее, она перемещается в список открытых вершин. Для нее рассчитывается эвристическое расстояние до терминальной вершины и пересчитывается расстояние от начальной вершины, ведь есть вероятность, что текущий путь к этой вершине окажется короче, чем найденный ранее (текущая вершина могла уже находится в списке открытых). Если путь оказался короче, ссылка на родительскую вершину изменяется.
Последовательность действий повторяется, пока в списке открытых вершин есть хотя бы одна вершина или пока в ходе выполнения алгоритма не встретится терминальная вершина.
Решение на Java.
Алгоритм А* применим для решения большого числа задач. Мне бы не хотелось ограничивать его реализацию решением только "Пятнашек". Поэтому я предлагаю абстрагироваться от решаемой задачи с помощью интерфейсов, абстрактных классов и наследования.
В первую очередь, задачи, решаемые алгоритмом А*, отличаются определением вершин графа(или состояниями). Введем абстрактный класс, инкапсулирующий общее, для любых вершин, поведение:
Так же, задачи различаются правилами порождения дочерних вершин, алгоритмом расчета расстояния от начальной вершины и эвристической оценкой расстояния до терминальной вершины. Выделим эти особенности в интерфейс:
Данное решение несколько не оптимально. Наверняка вы заметили, что информация в списке закрытых вершин избыточна: нас никогда не интересуют детали вершин из этого списка, а только факт принадлежности некоторой вершины к нему. Для этого достаточно хранить не сами вершины, а значения их хеш функций.
Теперь, что касается реализации непосредственно пятнашек. Я не стану приводить здесь весь исходный код, его вы можете посмотреть в репозитории на bitbucket. Остановлюсь только на интересных, на мой взгляд, вещах.
Во первых, само игровое поле удобно представить одномерным массивом, это позволит избежать лишних вложенных циклов и в целом упростит решение. Алгоритм раскрытия вершины (получение ее потомков), в таком случае, получается достаточно прост. Вначале находится индекс пустой клетки, затем вычисляется индекс кости, которая будет перемещена на пустую клетку. Ее индекс вычисляется как сумма индекса пустой клетки и индекса одного из ее соседей. Индексы соседних клеток элементарны: для соседа слева это -1, для соседа справа +1, для соседа сверху -(размер поля), для соседа снизу +(размер поля):
UPD: По настоятельной просьбе анонимного читателя, я опишу второй, казалось бы очевидный, способ генерирования начального состояния.
Согласно формуле, приведенной на википедии, можно заранее проверить начальное состояние на возможность приведения его к терминальному виду:
Можно показать, что ровно половину из всех возможных 1 307 674 368 000 (=15!) начальных положений пятнашек невозможно привести к собранному виду: пусть квадратик с числом расположен до (если считать слева направо и сверху вниз) квадратиков с числами меньшими . Будем считать , то есть если после костяшки с -м числом нет чисел, меньших , то . Также введем число — номер ряда пустой клетки (считая с 1). Если сумма
является нечётной, то решения головоломки не существует.
И в случае, если решения не существует, повторно сгенерировать начальное состояние. Полагаться на волю случая мне не по душе, но выбирать тот или иной подход вам. В любом случае главное решение, а не начальное состояние 🙂
Процедура проверки начального состояния:
Чтож, остальные детали реализации не должны вызывать трудностей. Однако, хочу заметить, что предложенная эвристика далека от совершенства. Ее можно усовершенствовать, что позволит сократить количество раскрываемых алгоритмом вершин и, соответственно, ускорить его работу. Буду рад увидеть ваши предложения по развитию эвристической оценки в комментариях.
