Sokoban Solver Statistics - XSokoban

Solved puzzles, percent

The XSokoban test suite consists of the classic 90 XSokoban puzzles, which have served as the de facto standard benchmark in academic research on Sokoban solver programming for many years.

This chart presents the results of leading Sokoban solvers on these puzzles.

Over the years, several solvers have been published that could not solve all XSokoban puzzles. One of the early notable programs was Rolling Stone (1997–2001) by Andreas Junghanns and Jonathan Schaeffer, which solved 57 of the puzzles. Festival (2020) by Yaron Shoham was the first published solver to successfully handle all 90 puzzles.

Today, four published solvers can solve all 90 puzzles. YASS solves 89 of them—an impressive result, though not on par with the top solvers.

The solvers were tested using their default settings with a 10-minute time limit, except for Curry, which was given a 24-hour limit to demonstrate that it, too, can solve all 90 puzzles.

This extended time limit for Curry highlights that this is not a 10-minute competition but rather a showcase of what these solvers can achieve.

All XSokoban puzzles feature goals clustered in a corner or a single room on the board. This arrangement is a popular theme in Sokoban puzzle design, and solvers often use specialized algorithms tailored to it.

To mitigate this theme bias, a more comprehensive evaluation should include a wider range of puzzles with diverse structures and sizes. With such a test set, no solver can solve all puzzles. Despite advances in computing power and algorithms, the Sokoban game remains far from being “solved.” Large puzzles—and even many medium-sized ones—are still beyond the reach of existing solvers.

Solved puzzles per minute, accumulated

Festival, Sokolution, and Takaken solve each puzzle within 2 minutes, demonstrating that time-efficient algorithms are available.

Curry, based on curriculum learning, requires more time. After 10 minutes, Curry has solved 54 of the puzzles.

Solved puzzles per minute, after the first minute

This chart excludes puzzles solved within the first minute to provide a clearer view of solver performance beyond that point.

The leading solvers find most of their remaining solutions within two minutes. Curry takes more than 10 minutes to solve about a third of the puzzles.

These results suggest that the XSokoban test suite is no longer a suitable benchmark for Sokoban solvers. The top solvers are not competing to solve the puzzles but merely to solve them as quickly as possible.

Average solution time for puzzles solved by all solvers, seconds

All solvers, except Curry, have very low average solution times. Many puzzles are solved within seconds—far faster than human capabilities.

Curry is based on curriculum learning and can solve all 90 puzzles, but this approach requires more time than the algorithms used by the other solvers.

Average solution length for puzzles solved by all solvers, moves

On average, Takaken finds solutions with about 100 fewer moves than those produced by Festival, Curry, and YASS.

Sokolution generates the longest solutions, with roughly 200 more moves than those of the other solvers.

Despite using a more time-consuming algorithm, Curry produces solutions of similar length to the other solvers.

For comparison, the chart also includes the average number of moves in the best-known solutions found online. While solver programs focus on solving puzzles, they do not necessarily aim for the shortest solutions. The chart shows a significant difference between the solver results and the best-known solutions.

Average solution length for puzzles solved by all solvers, pushes

Like humans, computers cannot rely on brute-force search to find solutions. For medium-sized and large puzzles, the search space is simply too large. Optimal or near-optimal solutions can only be found for very small puzzles.

Solved puzzles versus boxes, percent

The number of boxes is a simple, quantifiable characteristic that can indicate puzzle difficulty. However, since all XSokoban puzzles have been solved, it is not a relevant factor in this context.

Solved puzzles versus floors, percent

Puzzle size is another basic characteristic that can indicate difficulty. Rather than measuring it as width × height, a more refined approach is to count the number of squares the player can reach after removing all boxes. In the solver statistics, this metric is referred to as "floor squares" or simply "floors."

Since the four leading solvers have solved all puzzles, the chart displays a straight line for them.

Puzzle sizes, boxes

This chart displays the distribution of puzzles in the test suite based on the number of boxes.

Since all puzzles have been solved, it simply illustrates how many puzzles exist for each box count.

Puzzle sizes, floors

This chart displays the number of puzzles, solved and unsolved, for each floor square count.

The XSokoban puzzle set varies significantly in size, with the smallest puzzle having 49 floor squares and the largest 181.

Puzzle boxes versus floors

This bubble chart displays the puzzles arranged by their box counts and floor counts.

The chart offers a snapshot of the diversity and "shape" of the test suite:

• How large are the puzzles?


• Are there any outliers, or are the puzzles uniformly shaped?


• Are there disproportionately many or few boxes compared to the number of floor squares?

The chart shows that larger puzzles tend to have more boxes, which was expected. Having wide open areas for maneuvering generally makes a Sokoban puzzle easier for the player. The balance between box count and floor count is an important parameter in a puzzle author's toolkit.

Small unsolved puzzles, counting boxes

	Solver	Puzzle Set	Puzzle	Floors	Boxes	Lower Bound	BP	BT
1	YASS	XSokoban	90	181	25	442	460	1

Small unsolved puzzles, counting floors

	Solver	Puzzle Set	Puzzle	Floors	Boxes	Lower Bound	BP	BT
1	YASS	XSokoban	90	181	25	442	460	1

Small unsolved puzzles solved by all other solvers, counting boxes

	Solver	Puzzle Set	Puzzle	Floors	Boxes	Lower Bound	BP	BT
1	YASS	XSokoban	90	181	25	442	460	1

Small unsolved puzzles solved by all other solvers, counting floors

	Solver	Puzzle Set	Puzzle	Floors	Boxes	Lower Bound	BP	BT
1	YASS	XSokoban	90	181	25	442	460	1

Large solved puzzles, counting boxes

	Solver	Puzzle Set	Puzzle	Floors	Boxes	Lower Bound	BP	BT
1	Festival	XSokoban	48	94	34	200	200	0
2	Sokolution	XSokoban	48	94	34	200	200	0
3	Takaken	XSokoban	48	94	34	200	200	0
4	Curry	XSokoban	48	94	34	200	200	0
5	YASS	XSokoban	48	94	34	200	200	0
6	[All solvers]	XSokoban	48	94	34	200	200

Large solved puzzles, counting floors

	Solver	Puzzle Set	Puzzle	Floors	Boxes	Lower Bound	BP	BT
1	Festival	XSokoban	90	181	25	442	460	1
2	Sokolution	XSokoban	90	181	25	442	460	1
3	Takaken	XSokoban	90	181	25	442	460	1
4	Curry	XSokoban	90	181	25	442	460	1
5	YASS	XSokoban	10	172	32	506	512	1
6	[All solvers]	XSokoban	10	172	32	506	512

Large puzzles solved by only one solver, counting boxes

	Solver	Puzzle Set	Puzzle	Floors	Boxes	Lower Bound	BP	BT

Large puzzles solved by only one solver, counting floors

	Solver	Puzzle Set	Puzzle	Floors	Boxes	Lower Bound	BP	BT