Как устроены алгоритмы решения головоломок в жанре Sokoban?

Алгоритмы решения головоломок в жанре Sokoban основаны на поиске пути в графе конфигураций от начальной конфигурации до выигрышной. 3

Некоторые подходы:

• Обход графа конфигураций в ширину (Breadth-First Search, BFS). 3 В зависимости от уровня граф может иметь разную структуру, поэтому нужен алгоритм поиска пути, который работает для любых графов. 3
• Поиск оптимального пути с помощью алгоритма A*. 35 Этот алгоритм минимизирует общую стоимость пути и в нужных условиях обеспечивает лучшее решение за оптимальное время. 5 Он находит расстояние самого быстрого маршрута от начальной точки до объекта назначения, удаляя ненужные шаги. 5
• Метод, который начинается с конечного состояния головоломки и идёт обратно к начальному. 4 Этот подход позволяет избежать долгой проверки большой части нежелательных тупиковых ситуаций. 4

При решении головоломок в Sokoban приходится сталкиваться с большим количеством вариантов и глубоким деревом поиска. 14