Scientific research

From Sokoban Wiki

Scientific research

Sokoban has been studied using the theory of computational complexity.

The computational problem of solving Sokoban puzzles was first shown to be NP-hard. Further work proved it is also PSPACE-complete.

Search for a solution to a Sokoban puzzle is difficult for computers due to the many possible legal pushes at each turn (branching factor) and the possibly long sequence of moves needed to reach a solution (search tree depth).

Even small puzzles can require hundreds of player moves to solve.

The Sokoban game provides a challenging testbed for developing and evaluating planning techniques.

The first documented automated solver was Rolling Stone, developed at the University of Alberta.

Its core principles laid the groundwork for many newer solvers. It employed a conventional search algorithm enhanced with domain-specific knowledge.

Festival, utilizing its FESS algorithm, was the first automatic solver to complete all 90 puzzles in the widely used XSokoban test suite (Festival results).

However, even the best automated solvers cannot solve many of the more challenging puzzles that humans can solve with time and effort.