
A 44-year-old Japanese puzzle game about shoving crates around a warehouse has a new computer champion. Developer Andrew Healey says his program, Soksolv, now solves more Sokoban levels than any published solver on the two standard test suites, including 24 levels that no program had ever cracked on its own.
The twist: Healey says he did not type a single line of the code himself. In his detailed write-up of the project, he describes running one long AI coding session for 14 days, backed by roughly 430 helper agents, with an API-equivalent bill of about $3,500 and 15,000 hours of cloud CPU time.
The scoreboard
According to the project’s GitHub repository, Soksolv and Festival 3.1, the previous leader, were run on identical hardware with 600 seconds per level, eight dedicated cores and 15 GB of memory. Soksolv solved 3,218 of the 3,272 levels in the Large Test Suite against Festival’s 3,208, and 9,620 of the 10,043 levels in the Open Test Suite against 9,602.
Those margins, 10 and 18 levels, are thin at the 10-minute mark. The bigger gap is speed. Healey reports a median of 0.05 seconds per solved board for Soksolv versus 1.00 second for Festival, and says his solver was faster on 8,809 of the 9,223 levels both programs solved. At a one-second limit, it led by 627 levels on the Large suite and 2,247 on the Open suite.
Put another way, Soksolv now leaves 54 Large Test Suite levels unsolved, down from Festival’s 64, a cut of about 16% in what remains out of reach.
Why a box-pushing game is so hard for computers
As Wikipedia’s history of Sokoban explains, Hiroyuki Imabayashi created the game in 1981 as a hobby project, and his company Thinking Rabbit released it commercially in Japan in 1982. The name means “warehouse keeper.” The rules fit in a sentence: push every box onto a storage square, one at a time, and never pull.
That simplicity hides a monster. Deciding whether a given Sokoban puzzle can be solved at all is PSPACE-complete, a class of problems believed to be harder than the famous NP-complete ones. One careless push into a corner can doom a level hundreds of moves later. Healey writes that boards have a branching factor of around 16 possible pushes per position, and up to about 176 on huge levels, so brute force collapses after only a handful of moves.
Computers took decades to catch up. A 1994 solver from Meiji University handled 25 of the 90 classic XSokoban levels. The Festival solver, built on a 2020 search method called FESS from Yaron Shoham and Jonathan Schaeffer, became the first program to clear all 90.
How Soksolv wins
Healey credits Shoham’s published work heavily, then describes the extra tricks his agents found. Soksolv runs many different searches, called lanes, in parallel on all eight cores; they share positions and known dead ends through common tables. Some lanes search backward from the solved board by “pulling” boxes, which has no corner traps, hoping to meet a forward search in the middle. On one benchmark level, Holland #68, he says no single lane finished within 10 seconds, but all of them together solved it in 3.8 seconds.
He also set ground rules for the agents: no machine learning, no hard-coded answers, and a separate verifier the agents could not edit that replayed every solution move by move. Across the project the system ran 792 experiments, and Healey says it took 388 messages from him to steer it.
Sokoban’s influence runs deep in mainstream games, too, with box-pushing puzzles turning up in Zelda titles, as Badiyaa noted in its look at every version of Ocarina of Time. For another programmer pushing AI-assisted software in a new direction, read about Pete Warden’s bet on local AI.
Sources
- Introducing the World’s Strongest Sokoban Solver, Andrew Healey (developer’s own blog), 2026
- soksolv repository and benchmark results, Andrew Healey on GitHub, 2026
- Sokoban, Wikipedia, 2026
Image: brownpau, CC BY 2.0 via Wikimedia Commons
This article was produced with AI assistance and reviewed by our Editorial Desk. How we work.


