Sokoban — головоломка из 80-х: толкай ящики на цели. В этой версии игрок тоже должен закончить на цели. Управление — стрелками или WASD, есть Undo и Reset. Победа — когда каждый ящик и сам игрок стоят на целях, поэтому целей на одну больше, чем ящиков. Задача — сделать минимальное число ходов.
Решатель — порт на JavaScript оптимального солвера на C++. Он использует move-optimal macro-push A: каждое ребро поиска — целый толчок ящика, а его стоимость — кратчайший путь игрока до точки толкания плюс один. Итог — точный минимум ходов, но без перебора отдельных шагов. Состояния упакованы в битовые маски (bitmask): ящики — в 32-битное целое по достижимым клеткам, игрок — отдельное число. Ключ состояния — около 8 байт вместо килобайтного объекта, поэтому миллионы состояний влезают в десятки мегабайт. Очередь A — dial bucket queue, посещённые состояния с родительскими ссылками — open-addressed hash на typed-array. Без аллокаций и дружелюбно к кэшу.
Тупики отсекаются (deadlock pruning): статическая таблица мёртвых клеток (обратная достижимость от целей) плюс проверка замёрзших ящиков. Нижняя оценка дистанции толкания с учётом стен сохраняет допустимость A*, а значит, оптимальность.
Доски 1–14 решаются в браузере до доказанного оптимума за миллисекунды. Доска 15 — лабиринт с восемью ящиками — исключение: её поиск перебирает около 49 миллионов состояний и требует больше гигабайта памяти. Для браузера это слишком тяжело, поэтому оптимум (184 хода) вычислили заранее на нативном C++ этим же алгоритмом: параллельный A* справился примерно за 5 секунд на 24 ядрах. Решение проверили воспроизведением, и страница просто проигрывает готовый вариант. Поэтому ответ для доски 15 захардкожен. Собрано на основе моего Sokoban solver.