GoKawiilSokoban ("warehouse keeper") is a 1980s puzzle: push every box onto a goal. In this variant the keeper must also finish on a goal.
Moves: 0 Optimal: –
▲ ◀ ▶ ▼
Keeper (you) Box Goal Box on goal Wall
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.
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.
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.
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.
... continue reading