А* для нахождения решения «пятнашек»
Задача
Наша задача на сегодня состоит в нахождении решения игры «пятнашки». И не любое, а за наименьшее количество ходов. Надо же удивить ребенка тем, что вы умеете ее собирать за 10 ходов!
Правила гласят:
Пятна́шки — популярная головоломка, придуманная в 1878 году Ноем Чепмэном. Представляет собой набор одинаковых квадратных костяшек с нанесёнными числами, заключённых в квадратную коробку. Длина стороны коробки в четыре раза больше длины стороны костяшек для набора из 15 элементов (и в три раза больше для набора в 8 элементов), соответственно в коробке остаётся незаполненным одно квадратное поле. Цель игры — перемещая костяшки по коробке добиться упорядочивания их по номерам, желательно сделав как можно меньше перемещений.* Википедия
Описанное здесь решение этой задачи — это реализация одного из Programming Assignments из курса по алгоритмам на coursera.org. Этот курс закончился неделю назад, так что думаю что решение можно публиковать.
Решение
