Sokoban

The warehouse is composed of walls and pathways. Pathways are connected floor squares. A floor square may be empty, occupied by the player, or occupied by a box. A number of floor squares, equal to the number of boxes, are marked as storage locations. The objective of the puzzle is to push all boxes onto storage locations.^[1]

The player can move one square at a time, either horizontally or vertically, onto empty floor squares.^[2] Boxes and walls block the player's movement, but the player can walk up to a box and push it to an empty square directly beyond it. If a box is pushed against a wall or another box, it does not move. Boxes cannot be pulled.^[3]

Playing Sokoban requires thinking several steps ahead and visualizing all possible outcomes.^[4] Players should think carefully and thoroughly before pushing a box to prevent it getting trapped against a wall or other boxes.^[5] A bad move can cause a deadlock, a situation from which the puzzle cannot be solved, regardless of subsequent moves.^[6]

Common deadlocks are:^[7]

Two boxes placed together along a wall. A box in a corridor alongside a wall, which can still be pushed, but permanently lacks access to any storage location. A box in a corner. A box in a dead end. Four boxes in a square formation. Three boxes forming an L-shape in a wall corner.

In 1981, Hiroyuki Imabayashi created the first Sokoban game as a personal project for the NEC PC-8001 computer. The game used text-based graphics and featured five challenging levels designed by him. For the core mechanic, he was inspired by one part of the gameplay of Hudson Soft's 1980 action game, Aldebaran #1, for the MZ-80K,^[8] where the player pushed luggage to act as a wall to prevent radiation. Imabayashi conceptualized that in the warehouse, the boxes had to be organized, but they themselves also became obstacles in the process. He enjoyed playing the game with friends at his home. During this time, his wife's family had owned a disc record store that had a small computer corner. By chance, a salesman saw the game and suggested that it would sell. Imabayashi ported the game to the more advanced NEC PC-8801 computer from the store's corner, enhancing the graphics and expanding the levels to 20. In 1982, he founded his company, Thinking Rabbit, based in Takarazuka, Japan, and in December released this PC-8801 version as the first commercial Sokoban game.^{[9][10][11][12]}

In subsequent years, ports and new titles for various home computers and video game consoles were released, developed by Thinking Rabbit or other companies under license.^[13][14]

In 1988, Spectrum HoloByte published Sokoban in the U.S. for the IBM PC, Commodore 64, and Apple II as Soko-Ban,^[15] licensed by ASCII.^[16]

In 1990, FCI released Boxxle for the Game Boy in both North America and Europe,^[17] followed by Boxxle II in 1992.^[18]

Between 1996 and 2000, several Sokoban games were released for Windows and PlayStation in Japan.^{[19] [20] [21]}

In 2001, the Japanese software company Falcon acquired the copyright to the official Sokoban games and the trademarks for Sokoban and Thinking Rabbit.^[22] Since then, Falcon has continued to develop and license official Sokoban games.

Between 2004 and 2007, several Sokoban titles for Japanese mobile phones were distributed through i-mode by Square Enix and Dwango.^[23][24]

Since its debut in 1982, Sokoban has been released on various platforms, primarily in Japan but also in other regions. Most titles are independent without a continuous narrative, though a few are direct sequels to a specific earlier release—for example, Sokoban 2 (1984) follows Sokoban (1982), and Sokoban Revenge (1991) is a sequel to Sokoban Perfect (1989). The following table lists a selection of official Sokoban titles.^[25]

In an October 1983 review, Pasocom Game Ranking Book scored Sokoban (1982) 94 out of 100 points.^[28] A December 1983 issue of MICOMGAMES described the game as highly addictive, noting that "once you start playing, it's hard to stop" (translated from Japanese). ^[29] By June 1984, the developer reported that the game had sold 22,000 copies in Japan,^[30] and by March 1985, it had reached 30,000 copies.^[31]

Spectrum Holobyte reported that Sokoban was a hit in Japan, selling over 400,000 copies there before the 1988 release of the title Soko-Ban in the United States.^[32]

In 1988, Soko-Ban received a positive review for its IBM PC and Commodore 64 versions from Computer Gaming World, which described the game as simple yet mentally challenging and noted its addictive nature.^[33] In Dragon magazine, reviewers rated the IBM PC version 4½ out of 5 stars.^[34] In Computer Entertainer newsletter, the Apple II version was recommended and received 3½ out of 4 stars for graphics and the same rating for gameplay and entertainment.^[35]

In 1990 issues of Game Player's magazine, Tom R. Halfhill reviewed several console Sokoban games. He reviewed Shove It!, noting it was a challenging game that required players to carefully plan their moves and that its unhurried pace was a refreshing respite from frenzied action games, although all 160 puzzles were essentially the same.^[36] He reviewed Boxxle, stating that it also required careful planning or plenty of trial and error (usually both), and that its gameplay could become repetitive because the only variations in the 108 screens were the number and arrangement of crates and the shape of the rooms.^[37] He reviewed Boxyboy, highlighting its logical, untimed puzzles and describing it as a welcome change from typical action games. He noted that it was "virtually identical" to Shove It! and Boxxle.^[38]

The name Sokoban is a registered trademark for video game titles. However, the core mechanic—pushing boxes to storage locations on a grid—is not protected by copyright or patent. This has allowed the widespread creation of numerous unofficial versions.^[39] Some feature only custom levels, while others include level designs that may be subject to copyright. As a result, the term Sokoban has become informally genericized and is commonly used to refer to any game with these mechanics, regardless of origin.^[40]

An active fan community has produced thousands of custom puzzles,^[41] and software tools, including puzzle editors, solvers,^[42] and solution optimizers.^[43]

Sokoban is considered the originator of a puzzle game subgenre featuring box-pushing mechanics, commonly referred to as "Sokoban-like" games.^[44][45]

In Picoban, the goal is to reach a green stone, often blocked by one or more doors that require collecting keys or placing boxes on all storage locations.^[46] In Beanstalk, the objective is to push four items—a shovel, a bean seed, fertilizer, and a watering can—into a target square in a fixed sequence.^[47] In Pukoban, the character can pull boxes in addition to pushing them.^[48] In Sokoboxes Duo, two pushers must collaborate to solve the puzzle.^[49]

Hexoban uses a hexagonal grid instead of a square grid, allowing movements in six directions instead of four.^[50] In Multiban, the puzzle contains more than one pusher.^[51]

In Sokoban Limit the puzzles must be solved within a very strict number of moves.^[52]

Some Sokoban programs also offer a "reverse mode" in which players play a puzzle backward. Starting with all boxes on storage locations, they pull the boxes to return to the initial puzzle state.^[53]

Sokoban has been studied using the theory of computational complexity. The computational problem of solving Sokoban puzzles was first shown to be NP-hard.^[54][55] Further work proved it is also PSPACE-complete.^[56][57]

Solving non-trivial Sokoban puzzles is difficult for computers because of the high branching factor (many legal pushes at each turn) and the large search depth (many pushes needed to reach a solution).^[58][59] Even small puzzles can require lengthy solutions.^[60]

The Sokoban game provides a challenging testbed for developing and evaluating planning techniques.^[61] The first documented automated solver, Rolling Stone, was developed at the University of Alberta. It employed a conventional search algorithm enhanced with domain-specific techniques such as deadlock detection.^[62][63] A later solver, Festival, introduced the FESS search algorithm and became the first automatic system to solve all 90 puzzles in the widely used XSokoban test suite.^[64][65] Despite these advances, even the most sophisticated solvers cannot solve many highly complex puzzles that humans can solve with time and effort, using their ability to plan ahead, recognize patterns, and reason about long-term consequences.^[66][67][68]

• Logic puzzle
• Sliding puzzle
• Transport puzzle
• Motion planning