Головоломка пазл (пятнашки) Задание: Решить головоломку с помощью алгоритма А*. Вам предстоит управлять головоломками различных размеров (3, 4, 5, 17 и т.д.). Чем выше сможет подняться ваша программа, не умирая ужасной смертью, тем лучше. Стоимость, связанная с каждым переходом, всегда равна 1. Нужно реализовать по крайней мере 3 эвристических ф-ции (Эвристика на расстоянии Манхэттена обязательна). В конце поиска программа должна предоставить следующие значения:
- Общее количество состояний, когда-либо выбранных в "открытом" наборе (сложность по времени)
- Максимальное количество состояний, когда-либо представленных в памяти одновременно во время поиска (сложность по размеру)
- Количество ходов, необходимых для перехода из начального состояния в конечное
- Упорядоченная последовательность состояний, составляющих решение
- Головоломка может оказаться неразрешимой, и в этом случае вы должны сообщить об этом пользователю и выйти
Если размер головоломки нечетный (3х3, 5х5 и т.д.), то считаем количество инверсий (раскладываем нашу головоломку из спирали в линию и считаем для каждого числа какое количество чисел меньше данного числа, которые идут за данным числом, пустую фишку (ноль) не учитываем!) - Суммируем. Если число четное - головоломка решаема, иначе не решаема.
Если размер головоломки четный (4х4, 6х6 и т.д.), то считаем количество инверсий (раскладываем нашу головоломку из спирали в линию и считаем для каждого числа какое количество чисел меньше данного числа, которые идут за данным числом, пустую фишку (ноль) не учитываем!) - Суммируем. Далее прибавляем координаты нахождения пустой фишки к количеству инверсий. Если число получилось нечетное - то головоломка решаема, иначе не решаема.
На ютубе есть хороший разбор решения: https://www.youtube.com/watch?v=vFxWplSc1Nw&list=LL&index=3&t=3909s
Статья: https://www.gatevidyalay.com/tag/a-algorithm-for-8-puzzle-problem/
Онлайн генератор-сборщик пазла, можно выбрать алгоритм: https://tristanpenman.com/demos/n-puzzle/