Sokobán №344933

Вот выдержка из статьи на Хабре
https://habr.com/ru/post/597857/

Сокобан — игра логическая, стоит в одном ряду с кубиком Рубика, шашками и даже шахматами. Простые, можно даже сказать, элегантные правила — вершина айсберга. В глубине — сложная математическая теория. Задача решения этой головоломки относится к так называемым NP-трудным задачам, как часть более общего класса задач планирования движения .

Трудность прохождения сокобана заключается не только в уровне ветвления дерева вариантов ходов (многие исследователи сравнивают эту игру по сложности с шахматами), но и в огромной глубине поиска по этому дереву. Для того, чтобы найти верное решение, требуется перебрать очень много вариантов. Необходимое количество «правильных» ходов, ведущих к выигрышу, на некоторых уровнях может достигать тысячи. Однако опытные игроки, вооружённые эвристикой, могут быстро отсеять в мозгу заведомо тупиковые варианты, тем самым существенно сузив область поиска.
Кроме главной задачи головоломки — расставить ящики по своим местам — существует ещё две задачи для игрока: минимизировать перемещения ящиков по лабиринту и число движений кладовщика. Решение этих задач уже схоже с решением шахматных этюдов — правила те же, но игра обрастает дополнительными условиями.