Sokoban
Encyclopedia
is a type of transport puzzle
, in which the player pushes boxes
or crate
s around in a warehouse
, trying to get them to storage locations. The puzzle is usually implemented as a video game.
Sokoban was created in 1981 by Hiroyuki Imabayashi, and published in 1982 by Thinking Rabbit
, a software house
based in Takarazuka
, Japan
.
Although the first 10 puzzles of the original 1982 Sokoban game followed the rules described above, the remaining 10 puzzles could only be solved after transforming several walls into floors by pushing them from a particular side.
In 1988 Sokoban was published in US by Spectrum HoloByte
for the Commodore 64
, IBM-PC and Apple II series
as Soko-Ban. A 1988 review in Computer Gaming World
praised the game for being "pure and simple, very playable and mentally challenging", citing its addictive qualities.
It was also reviewed in 1988 in Dragon
#132 by Hartley, Patricia, and Kirk Lesser in "The Role of Computers" column. The reviewers gave the game 4 out of 5 stars.
, including almost all home computer
and personal computer
systems. Versions also exist for several hand held and video game console
s, mobile phones, graphic calculators, and Canon PowerShot digital cameras.
. The problem of solving Sokoban puzzles has been proven to be NP-hard
. This is also interesting for artificial intelligence
researchers, because solving Sokoban can be compared to designing a robot which moves boxes in a warehouse. Further work has shown that solving Sokoban problems is also PSPACE-complete
.
Sokoban is difficult not only due to its branching factor
(which is comparable to chess
), but also its enormous search tree
depth; some levels require more than 1000 "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.
Transport puzzle
Transport puzzles are logistical puzzles, which often represent real-life transport problems.-Description:In transport puzzles you move persons and/or objects through a given landscape. As in rearrangement puzzles, no piece is ever lost or added to the board...
, in which the player pushes boxes
Wooden box
A wooden box is a container made of wood for storage or as a shipping container.Construction may include several types of wood; lumber , plywood, engineered woods, etc...
or crate
Crate
A crate is a large shipping container, often made of wood, typically used to transport large, heavy or awkward items. A crate has a self-supporting structure, with or without sheathing. For a wooden container to be a crate, all six of its sides must be put in place to result in the rated strength...
s around in a warehouse
Warehouse
A warehouse is a commercial building for storage of goods. Warehouses are used by manufacturers, importers, exporters, wholesalers, transport businesses, customs, etc. They are usually large plain buildings in industrial areas of cities and towns. They usually have loading docks to load and unload...
, trying to get them to storage locations. The puzzle is usually implemented as a video game.
Sokoban was created in 1981 by Hiroyuki Imabayashi, and published in 1982 by Thinking Rabbit
Thinking Rabbit
Thinking Rabbit was a software house based in Takarazuka, Japan, and are the original publishers of Sokoban. The company joined the Disk Original Group in 1986.-External links:...
, a software house
Software house
A software house is a company whose primary products are software.- Types :There are a number of different types of software houses:*Large and well-known companies such as Microsoft, SAP AG, Oracle Corporation, HP, Adobe Systems, Apple Inc...
based in Takarazuka
Takarazuka, Hyogo
is a city located in Hyōgo Prefecture, Japan.- Geography :Takarazuka is nestled between the Rokko Range to the west and Nagao Range to the north with the Muko River running through the center of the city....
, Japan
Japan
Japan is an island nation in East Asia. Located in the Pacific Ocean, it lies to the east of the Sea of Japan, China, North Korea, South Korea and Russia, stretching from the Sea of Okhotsk in the north to the East China Sea and Taiwan in the south...
.
Rules
- Only one box can be pushed at a time.
- A box cannot be pulled.
- The player cannot walk through boxes or walls.
- The puzzle is solved when all boxes are located at storage locations.
Sokoban published by Thinking Rabbit
- Sokoban (1982) (FM-7FM-7FM-7 is a home computer released in 1982 in Japan.The Fujitsu FM-7 was Fujitsu's first entry into the Japanese home computer market, and for their debut computer, they chose to come out with a 6809-based personal computer very similar to Radio Shack's Color Computer.-Hardware:*Two MC 68B09 CPUs @...
) with 20 levels. - Sokoban 2 (1984) (NEC PC-8801NEC PC-8801The NEC PC-8801 was an early Zilog Z80-based computer exclusively released in Japan, where it became very popular, by NEC Corporation in 1981. It was informally called the "PC-88"....
) with 50 levels. - Sokoban Perfect (1989) (NEC PC-9801) with 306 levels.
- Sokoban Revenge (1991) (NEC PC-9801) with 306 levels.
Although the first 10 puzzles of the original 1982 Sokoban game followed the rules described above, the remaining 10 puzzles could only be solved after transforming several walls into floors by pushing them from a particular side.
Sokoban published by Spectrum Holobyte
- Soko-Ban (1988) (DOSDOSDOS, short for "Disk Operating System", is an acronym for several closely related operating systems that dominated the IBM PC compatible market between 1981 and 1995, or until about 2000 if one includes the partially DOS-based Microsoft Windows versions 95, 98, and Millennium Edition.Related...
) with 50 levels.
In 1988 Sokoban was published in US by Spectrum HoloByte
Spectrum HoloByte
Spectrum HoloByte, Inc. was a video game developer and publisher originally based in Alameda, California.The company was founded in 1983 and was most famous for its simulation games, notably the Falcon series of flight simulators and Vette!, a driving simulator from 1989...
for the Commodore 64
Commodore 64
The Commodore 64 is an 8-bit home computer introduced by Commodore International in January 1982.Volume production started in the spring of 1982, with machines being released on to the market in August at a price of US$595...
, IBM-PC and Apple II series
Apple II series
The Apple II series is a set of 8-bit home computers, one of the first highly successful mass-produced microcomputer products, designed primarily by Steve Wozniak, manufactured by Apple Computer and introduced in 1977 with the original Apple II...
as Soko-Ban. A 1988 review in Computer Gaming World
Computer Gaming World
Computer Gaming World was a computer game magazine founded in 1981 by Russell Sipe as a bimonthly publication. Early issues were typically 40-50 pages in length, written in a newsletter style, including submissions by game designers such as Joel Billings , Dan Bunten , and Chris Crawford...
praised the game for being "pure and simple, very playable and mentally challenging", citing its addictive qualities.
It was also reviewed in 1988 in Dragon
Dragon (magazine)
Dragon is one of the two official magazines for source material for the Dungeons & Dragons role-playing game and associated products, the other being Dungeon. TSR, Inc. originally launched the monthly printed magazine in 1976 to succeed the company's earlier publication, The Strategic Review. The...
#132 by Hartley, Patricia, and Kirk Lesser in "The Role of Computers" column. The reviewers gave the game 4 out of 5 stars.
Implementations of Sokoban
Implementations of Sokoban have been written for numerous computer platformsPlatform (computing)
A computing platform includes some sort of hardware architecture and a software framework , where the combination allows software, particularly application software, to run...
, including almost all home computer
Home computer
Home computers were a class of microcomputers entering the market in 1977, and becoming increasingly common during the 1980s. They were marketed to consumers as affordable and accessible computers that, for the first time, were intended for the use of a single nontechnical user...
and personal computer
Personal computer
A personal computer is any general-purpose computer whose size, capabilities, and original sales price make it useful for individuals, and which is intended to be operated directly by an end-user with no intervening computer operator...
systems. Versions also exist for several hand held and video game console
Video game console
A video game console is an interactive entertainment computer or customized computer system that produces a video display signal which can be used with a display device to display a video game...
s, mobile phones, graphic calculators, and Canon PowerShot digital cameras.
Scientific research on Sokoban
Sokoban can be studied using the theory of computational complexityComputational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
. The problem of solving Sokoban puzzles has been proven to be NP-hard
NP-hard
NP-hard , in computational complexity theory, is a class of problems that are, informally, "at least as hard as the hardest problems in NP". A problem H is NP-hard if and only if there is an NP-complete problem L that is polynomial time Turing-reducible to H...
. This is also interesting for artificial intelligence
Artificial intelligence
Artificial intelligence is the intelligence of machines and the branch of computer science that aims to create it. AI textbooks define the field as "the study and design of intelligent agents" where an intelligent agent is a system that perceives its environment and takes actions that maximize its...
researchers, because solving Sokoban can be compared to designing a robot which moves boxes in a warehouse. Further work has shown that solving Sokoban problems is also PSPACE-complete
PSPACE-complete
In complexity theory, a decision problem is PSPACE-complete if it is in the complexity class PSPACE, and every problem in PSPACE can be reduced to it in polynomial time...
.
Sokoban is difficult not only due to its branching factor
Branching factor
In computing, tree data structures, and game theory, the branching factor is the number of children at each node. If this value is not uniform, an average branching factor can be calculated....
(which is comparable to chess
Chess
Chess is a two-player board game played on a chessboard, a square-checkered board with 64 squares arranged in an eight-by-eight grid. It is one of the world's most popular games, played by millions of people worldwide at home, in clubs, online, by correspondence, and in tournaments.Each player...
), but also its enormous search tree
Search tree
In computer science, a search tree is a binary tree data structure in whose nodes data values are stored from some ordered set, in such a way that in-order traversal of the tree visits the nodes in ascending order of the stored values...
depth; some levels require more than 1000 "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
University of Alberta
The University of Alberta is a public research university located in Edmonton, Alberta, Canada. Founded in 1908 by Alexander Cameron Rutherford, the first premier of Alberta and Henry Marshall Tory, its first president, it is widely recognized as one of the best universities in Canada...
GAMES Group. The more complex Sokoban levels are, however, out of reach even for the best automated solvers.
See also
- Logic puzzleLogic puzzleA logic puzzle is a puzzle deriving from the mathematics field of deduction.-History:The logic puzzle was first produced by Charles Lutwidge Dodgson, who is better known under his pen name Lewis Carroll, the author of Alice's Adventures in Wonderland...
- Sliding puzzleSliding puzzleA sliding puzzle, sliding block puzzle, or sliding tile puzzle is a puzzle that challenges a player to slide usually flat pieces along certain routes to establish a certain end-configuration....
- Chip's ChallengeChip's ChallengeChip's Challenge is a tile-based, puzzle video game for several systems, including the hand-held Atari Lynx, Amiga, Commodore 64, ZX Spectrum, DOS, and Windows . It has also been ported to the TI-84+ calculator and the TI-89 Titanium...
- KwirkKwirkKwirk, known in Japan as , is an action/puzzle video game first developed and published by Atlus in Japan on November 24, for the original Game Boy. The same port was later published in North America in March 1990 by Acclaim Entertainment...
- LasertankLasertankLasertank is a computer puzzle game requiring logical thinking to solve a variety of levels. It is open source and careware and can be used for free. The player must be able to concentrate and think ahead as in playing chess or checkers. Contradicting its name, Lasertank is in no way an action game...