쇼우 HN: 소코반 AI 솔버

Sokoban Sokoban ("warehouse keeper") is a 1980s puzzle: push every box onto a goal. In this variant the keeper must also finish on a goal. Board: Reset Undo Solve with AI AI speed: Slow Normal Fast Next → Moves: 0 Optimal: – ▲ ◀ ▶ ▼ Keeper (you) Box Goal Box on goal Wall How to play & the rules The warehouse is a grid. On each step the keeper moves one square up, down, left or right. The keeper cannot walk into a wall or a box. It can push a single box if the square just beyond the box (in the push direction) is empty floor or a goal. Only one box moves per step, and a box can be pushed out of a goal again to make room. Controls: arrow keys or W A S D , or the on-screen pad. Undo steps back. Reset restores the board. Goal: the puzzle is won when every movable entity. Every box and the keeper. Is sitting on a goal. That is why each board has one more goal than it has boxes: the last goal is for the keeper. Objective: reach that state in as few moves as possible. For several boards the optimal move count is known and shown above. The AI (with an admissible heuristic) returns an optimal solution on the boards it can search exhaustively. How the AI solver works Sokoban is an A* search problem, but a naive version that explores one keeper step at a time explodes on crowded boards. What runs here is a plain-JavaScript port of a native C++ optimal solver I wrote. It returns the provably fewest-moves solution, not just some solution: Move-optimal macro-push A*. Each search edge is a whole box push costed as (the keeper's shortest walk to the push spot) + 1, so the total is the true minimum number of keeper moves , while the search skips over the individual walking steps. Compact bitmask states. The boxes are packed into a 32-bit integer over the board's reachable "live" cells and the keeper into one more number, so a whole state is a single ~8-byte key instead of a ~1 KB object. Millions of states fit in tens of MB. Dial bucket queue + open-addressed hash. The A* frontier is a bucket queue keyed by cost, and the visited set (with the solution's parent links) lives in a flat typed-array hash. Allocation-free and cache-friendly. Deadlock pruning. A static dead-square table (reverse-reachability from the goals) plus a freeze check discard provably-unsolvable positions, guided by a wall-aware push-distance lower bound that keeps A* admissible (hence optimal). Boards 1–14 are solved live to the proven optimum in milliseconds (the move counts shown as "Optimal" above are exactly what this solver returns). Board 15. The 8-box maze. Is the exception: its optimal search explores ~49 million states and needs >1 GB , which would take far too long to run inside a browser tab. So its optimum ( 184 moves ) was computed offline by the native C++ build of this exact algorithm (a parallel A* search, ~5 s across 24 cores) and verified by replay, and the page simply plays that precomputed solution back . That is why board 15's answer is hardcoded rather than searched here. Built from my Sokoban solver . About Sokoban →