is a

puzzle video game Puzzle video games make up a broad genre of video games that emphasize puzzle solving. The types of puzzles can test problem-solving skills, including logic, pattern recognition, sequence solving, spatial recognition, and word completion. H ...

in which the player pushes boxes around in a

warehouse A warehouse is a building for storing goods. Warehouses are used by manufacturers, importers, exporters, wholesalers, transport businesses, customs, etc. They are usually large plain buildings in industrial parks on the outskirts of cities ...

, trying to get them to storage locations. The game was designed in 1981 by Hiroyuki Imabayashi, and first published in December 1982.

Gameplay

The game is played on a board of

squares In Euclidean geometry, a square is a regular quadrilateral, which means that it has four equal sides and four equal angles (90- degree angles, π/2 radian angles, or right angles). It can also be defined as a rectangle with two equal-length a ...

, 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 move a box by walking up to it and push it to the square beyond. Boxes cannot be pulled, and they cannot be pushed to squares with walls or other boxes. The number of boxes equals the number of storage locations. The puzzle is solved when all boxes are placed at storage locations.

Selected official releases

Development

''Sokoban'' was created in 1981 by Hiroyuki Imabayashi. The first commercial game was published in December 1982 by Thinking Rabbit, a

software house A software company is a company whose primary products are various forms of software, software technology, distribution, and software product development. They make up the software industry. Types There are a number of different types of softw ...

based in Takarazuka,

Japan Japan ( ja, 日本, or , and formally , ''Nihonkoku'') is an island country in East Asia. It is situated in the northwest Pacific Ocean, and is bordered on the west by the Sea of Japan, while extending from the Sea of Okhotsk in the north ...

. In 1988 ''Sokoban'' was published in US by Spectrum HoloByte for the

Commodore 64 The Commodore 64, also known as the C64, is an 8-bit home computer introduced in January 1982 by Commodore International (first shown at the Consumer Electronics Show, January 7–10, 1982, in Las Vegas). It has been listed in the Guinness ...

IBM-PC The IBM Personal Computer (model 5150, commonly known as the IBM PC) is the first microcomputer released in the IBM PC model line and the basis for the IBM PC compatible de facto standard. Released on August 12, 1981, it was created by a team ...

Unix Unix (; trademarked as UNIX) is a family of multitasking, multiuser computer operating systems that derive from the original AT&T Unix, whose development started in 1969 at the Bell Labs research center by Ken Thompson, Dennis Ritchie, and ot ...

Commodore Amiga Amiga is a family of personal computers introduced by Commodore in 1985. The original model is one of a number of mid-1980s computers with 16- or 32-bit processors, 256 KB or more of RAM, mouse-based GUIs, and significantly improved graphi ...

and Apple II series as '' Soko-Ban''. ''Sokoban'' was a hit in Japan where it had sold more than 400,000 copies by the time Spectrum HoloByte imported it to the United States.

Implementations

Implementations of ''Sokoban'' have been written for numerous

computer platforms A computing platform or digital platform is an environment in which a piece of software is executed. It may be the hardware or the operating system (OS), even a web browser and associated application programming interfaces, or other underlying so ...

, including almost all home computer and

personal computer A personal computer (PC) is a multi-purpose microcomputer whose size, capabilities, and price make it feasible for individual use. Personal computers are intended to be operated directly by an end user, rather than by a computer expert or tec ...

systems. Different versions also exist for

video game console A video game console is an electronic device that outputs a video signal or image to display a video game that can be played with a game controller. These may be home consoles, which are generally placed in a permanent location connected to ...

s, mobile phones,

graphic calculators A graphing calculator (also graphics calculator or graphic display calculator) is a handheld computer that is capable of plotting graphs, solving simultaneous equations, and performing other tasks with variables. Most popular graphing calcul ...

digital camera A digital camera is a camera that captures photographs in digital memory. Most cameras produced today are digital, largely replacing those that capture images on photographic film. Digital cameras are now widely incorporated into mobile devices ...

s and

electronic organizer An electronic organizer (or electric organizer) is a small calculator-sized computer, often with an built-in diary application and other functions such as an address book and calendar, replacing paper-based personal organizers. It normally ha ...

Scientific research

''Sokoban'' can be studied using the theory of computational complexity. The problem of solving ''Sokoban'' puzzles was first proved to be

NP-hard In computational complexity theory, NP-hardness ( non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard pr ...

. Further work showed that it was significantly more difficult than NP problems; it is

PSPACE-complete In computational complexity theory, a decision problem is PSPACE-complete if it can be solved using an amount of memory that is polynomial in the input length (polynomial space) and if every other problem that can be solved in polynomial space can b ...

. This is of interest for

artificial intelligence Artificial intelligence (AI) is intelligence—perceiving, synthesizing, and inferring information—demonstrated by machines, as opposed to intelligence displayed by animals and humans. Example tasks in which this is done include speech re ...

(AI) research because solving ''Sokoban'' can be compared to the

automated planning Automation describes a wide range of technologies that reduce human intervention in processes, namely by predetermining decision criteria, subprocess relationships, and related actions, as well as embodying those predeterminations in machines ...

required by some

autonomous robot An autonomous robot is a robot that acts without recourse to human control. The first autonomous robots environment were known as Elmer and Elsie, which were constructed in the late 1940s by W. Grey Walter. They were the first robots in history ...

s. ''Sokoban'' is difficult not only because of its large

branching factor In computing, tree data structures, and game theory, the branching factor is the number of children at each node, the outdegree. If this value is not uniform, an ''average branching factor'' can be calculated. For example, in chess, if a "no ...

, but also because of its large

search tree In computer science, a search tree is a tree data structure used for locating specific keys from within a set. In order for a tree to function as a search tree, the key for each node must be greater than any keys in subtrees on the left, and less ...

depth. Some level types can even be extended indefinitely, with each

iteration Iteration is the repetition of a process in order to generate a (possibly unbounded) sequence of outcomes. Each repetition of the process is a single iteration, and the outcome of each iteration is then the starting point of the next iteration. ...

requiring an exponentially growing number of moves and pushes. Skilled human players rely mostly on

heuristics A heuristic (; ), or heuristic technique, is any approach to problem solving or self-discovery that employs a practical method that is not guaranteed to be optimal, perfect, or rational, but is nevertheless sufficient for reaching an immediate, ...

and are usually able to quickly discard a great many futile or redundant lines of play by recognizing patterns and subgoals, thereby drastically reducing the search effort. Some ''Sokoban'' puzzles can be solved automatically by using a single-agent search algorithm, such as

IDA* Iterative deepening A* (IDA*) is a graph traversal and path search algorithm that can find the shortest path between a designated start node and any member of a set of goal nodes in a weighted graph. It is a variant of iterative deepening depth ...

; enhanced by several techniques that make use of domain-specific knowledge. This is the method used by ''Rolling Stone'', a ''Sokoban'' solver developed by the

University of Alberta The University of Alberta, also known as U of A or UAlberta, is a Public university, public research university located in Edmonton, Alberta, Canada. It was founded in 1908 by Alexander Cameron Rutherford,"A Gentleman of Strathcona – Alexande ...

GAMES Group. ''Festival'' was the first automatic solver to solve all 90 levels in the standard benchmark test suite. However, the more complex ''Sokoban'' levels are out of reach even for the best automated solvers.

Variants

Several puzzles can be considered variants of the original ''Sokoban'' game in the sense that they all make use of a controllable character pushing boxes around in a maze. * Alternative tilings: In the standard game, the mazes are laid out on a

square grid In geometry, the square tiling, square tessellation or square grid is a regular tiling of the Euclidean plane. It has Schläfli symbol of meaning it has 4 squares around every vertex. Conway called it a quadrille. The internal angle of th ...

. Several variants apply the rules of ''Sokoban'' to mazes laid out on other tilings. ''Hexoban'' uses regular hexagons, and ''Trioban'' uses equilateral triangles. * Multiple pushers: In the variants ''Multiban'' and ''Interlock'', the player can control multiple characters. * Alternative goals: Several variants adjust the requirements for completing a level. For example, in ''Block-o-Mania'' the boxes have different colours, and the goal is to push them onto squares with matching colours. ''Sokomind Plus'' implements a similar idea, with boxes and target squares uniquely numbered. In ''Interlock'' and ''Sokolor'', the boxes also have different colours, but the goal is to move them so that similarly coloured boxes are adjacent. In ''CyberBox'', each level has a designated exit square, and the goal is to reach that exit. In a variant called ''Beanstalk'', the elements of the level must be pushed onto a target square in a fixed sequence. * Additional game elements: ''Push Crate'', ''Sokonex'', ''Xsok'', ''Cyberbox'' and ''Block-o-Mania'' all add new elements to the basic puzzle. Examples include holes, teleports, moving blocks and one-way passages. The 1982 ''Sokoban'' ( NEC PC-8801) game featured levels with destructible walls. * Character actions: In ''Pukoban'', the character can pull boxes in addition to pushing them. * Reverse mode: The player solves the puzzle backwards, from the end to the initial position by pulling instead of pushing boxes. Standard ''Sokoban'' puzzles can be played in reverse mode, and the reverse-mode solutions can be converted to solutions for the standard-mode puzzles. Therefore, reverse-mode

gameplay Gameplay is the specific way in which players interact with a game, and in particular with video games. Gameplay is the pattern defined through the game rules, connection between player and the game, challenges and overcoming them, plot and pl ...

can also be instrumental in solving standard ''Sokoban'' puzzles.

External links

Official Sokoban site
(in Japanese)
The University of Alberta Sokoban page
*

References

{{DEFAULTSORT:Sokoban 1982 video games Cancelled Atari Jaguar games Commodore 64 games DOS games FM-7 games GP2X games Japanese inventions Linux games Logic puzzles MacOS games MSX games NEC PC-6001 games NEC PC-8001 games NEC PC-8801 games NEC PC-9801 games PSPACE-complete problems Puzzle video games SG-1000 games Sharp MZ games Sharp X1 games Sharp X68000 games Single-player video games Video games developed in Japan Windows games Windows Mobile Professional games ZX Spectrum games