Show HN: Sokoban AI Solver

TL;DR Highlight

An A* solver in plain JavaScript finds optimal Sokoban solutions in milliseconds inside the browser.

Who Should Read

A backend or frontend developer who wants to solve state-space problems efficiently with classic search like A* in the age of LLMs.

Core Mechanics

It's called AI, but it's A* search, not an LLM
- The optimal Sokoban solver is built as an A* search problem.
- A native C++ optimal solver was ported to plain JavaScript and runs in the browser.
One box push is one search step
- Edge cost is the keeper's shortest walk to the push spot plus 1.
- Walking steps are skipped in the search, yet the total move count is the true minimum.
States are packed into a few integers
- Boxes fit in a 32-bit integer over reachable cells, and the keeper is one more number.
- A state is a ~8-byte key instead of a ~1 KB object, so millions of states fit in tens of MB.
The queue and hash avoid allocations
- The A* frontier is a bucket queue keyed by cost.
- The visited set and parent links live in a flat typed-array hash.
Deadlock pruning keeps A* optimal

Community Reactions

A fan of the classic meaning of AI
- One commenter said old techniques like expert systems, A*, and SAT may feed into the next AI breakthrough.
- They also floated constraining LLM output with classic AI methods.
Suggestions that board 15 could run in-browser
- Commenters suggested WASM to speed it up.
- They suggested storing the keeper's whole reachable region in the state, or trying BFS.
- They also pointed to pruning techniques from state-of-the-art Sokoban solvers.
Criticism: behind SOTA solvers, easy examples
- One commenter said it lags several available SOTA Sokoban solvers and only handles small, simple levels.
- Another wanted harder examples with many trap dead states.
Hands-on experience and rule differences
- One player found that a first move they had ruled out on board 12 was the optimal one.
- They also saw the solver beat their own move count from their starting position.

How to Apply

Turn one of your search states into a bitmask key
- Pick one search state you currently keep as an object or JSON.
- Pack it into an integer key and compare Map memory and speed.
Use meaningful actions as edges instead of single steps
- In workflow or pathfinding code, collapse pointless intermediate steps into one edge.
- Sum the intermediate costs so optimality is preserved.
Add a classic search validator after LLM output
- Check an agent's plan for validity with A* or constraint checks.
- Precompute a dead-state table to prune.
Precompute heavy searches offline and replay them
- Solve cases that the browser can't handle offline and store the result.
- Make the client only replay the stored solution.

Try It

copy & run

# Paste into Claude or ChatGPT as-is (simplified version of the article's method)

You are a Python developer. Write a small optimal Sokoban solver in under 30 lines using this approach.
- Search unit: one box push (macro-push). Cost = BFS shortest walk of the keeper to the push spot + 1
- State: (frozenset of box positions, keeper position)
- Heuristic: sum of Manhattan distances from each box to its nearest goal (admissible)
- Deadlock: prune cells unreachable by reverse pulling from the goals
- Rules: win when every box and the keeper are on goals; goals = boxes + 1

Board:
{{paste the board using # wall, $ box, . goal, @ keeper}}

Next to try: compare the number of expanded states against step-by-step BFS on the same board.

Terminology

A*A search that expands the most promising path first, using cost so far plus an estimate of remaining distance. It's like a navigation app trying main roads first.

admissible heuristicAn estimate that never overstates the true remaining cost. This is what guarantees A* returns an optimal answer.

Bucket queueA queue with one slot per cost value that pops the lowest slot first. It mimics a priority queue without heap sorting.

DeadlockA state from which the puzzle can never be solved no matter what you do. A box stuck in a corner is the classic case.

macro-pushTreating several walking steps plus one box push as a single edge in the search.