Sokoban ('warehouse keeper') is a type of puzzle video game, in which the player pushes crates or boxes around in a warehouse, trying to get them to storage locations.Sokoban was created in 1981 by Hiroyuki Imabayashi, and published in December 1982 by Thinking Rabbit, a software house based in Takarazuka, Japan.
The game is played on a board of squares, where each square is a floor or a wall. Some floor squares contain boxes, and some floor squares are marked as storage locations.The player is confined to the board, and may move horizontally or vertically onto empty squares (never through walls or boxes). The player can also move into a box, which pushes it into the square beyond. Boxes may not be pushed into other boxes or walls, and they cannot be pulled. The number of boxes is equal to the number of storage locations. The puzzle is solved when all boxes are at storage locations.
Sokoban can be studied using the theory of computational complexity. The problem of solving Sokoban puzzles has been proven to be NP-hard. Further work showed that it was significantly more difficult than NP problems; it is PSPACE-complete. This is also interesting for artificial intelligence researchers, because solving Sokoban can be compared to the automated planning that needs to be done by a robot that moves boxes in a warehouse.Sokoban is difficult not only due to its branching factor (which is comparable to chess), but also its enormous search tree depth; some levels can be extended indefinitely, with each iteration requiring an exponentially growing number of moves and pushes. Skilled human players rely mostly on heuristics; they are usually able to quickly discard futile or redundant lines of play, and recognize patterns and subgoals, drastically cutting down on the amount of search.Some Sokoban puzzles can be solved automatically by using a single-agent search algorithm, such as IDA, enhanced by several techniques which make use of domain-specific knowledge. This is the method used by Rolling Stone, a Sokoban solver developed by the University of Alberta GAMES Group. The more complex Sokoban levels are, however, out of reach even for the best automated solvers.