An AI agent built the world's strongest Sokoban solver without writing a single line of code

The Strongest Sokoban Solver

Soksolv solves more levels than any published Sokoban solver on both standard benchmarks, including 24 world-first automated solves, and runs about 3.2x faster overall. The author directed one long Claude Code session with roughly 430 subagents, at an API-equivalent cost of about $3,500, plus 15,000 vCPU-hours of compute. The solver uses push-based search, deadlock pruning, PI-corral pruning, and bidirectional search, and was written in Go with a 15 GB memory cap.

As is common for this era, I did not handwrite a single line of code.
  1. healeycodes

    Author here. The owner of sokobano.de/wiki/index.php?title=Solver_Statistics is currently independently verifying the performance of my solver (and the early signs look good)!

  2. quibono

    FWIW there's a proof of Sokoban being NP-complete in a Cambridge University student publication called Eureka [0], edition 54.

    So, quite a lot more complex than one might think.

    [0] https://archim.org.uk/publications/

  3. vintermann

    Decades ago I built a Sokoban solver, then a more generic puzzle solver which could handle a wide range of similar games (such as Atomix). It's fun to see someone else finding all of these heuristics. Excluding dead squares and searching backwards to meet in the middle I definitively implemented, and I thought of many of these others too (though whether I got around to implementing them is another question!). This post is praiseworthy for showing how intuitive these tricks are once you know them.

More from this day

2026-11-20