Sokoban

Template:Short description Template:Use mdy dates Template:Infobox video game series Template:Nihongo foot is a series of puzzle video games in which the player pushes boxes around in a warehouse, trying to get them to storage locations. Hiroyuki Imabayashi created the first Sokoban game in 1981 as a hobby, and the following year, his company Thinking Rabbit published an enhanced commercial version in Japan for the NEC PC-8801 computer. Over the years, new titles were released for various platforms, developed by Thinking Rabbit or other companies under license. The game became popular in Japan and internationally, and the official series has remained active, with its most recent title released in 2021. Sokoban has inspired unofficial versions, thousands of custom puzzles, similar games, and artificial intelligence research.

File:Sokoban ani.gif

A Sokoban puzzle being solved

History

In 1981, Hiroyuki Imabayashi created the first Sokoban game as a hobby for the NEC PC-8001 computer. The game used text-based graphics and featured five levels designed by him. For the core mechanic, he was inspired by a part of the gameplay in Hudson Soft's 1980 action game, Aldebaran #1, for the MZ-80K,<ref>Template:Cite magazine</ref> where the player pushed luggage to act as a wall to prevent radiation.<ref name="mr-hiroyuki-imabayashi-interview-inspiration">Template:Cite web</ref> Imabayashi conceptualized that in the warehouse, the boxes had to be organized, but they themselves also became obstacles in the process. He worked on designing levels that provided a real challenge, and friends he invited to his home to play the game struggled to solve them. At that time, his wife's parents owned a record store with a small computer section. By chance, a salesman saw the game and suggested that it would sell. Imabayashi used a NEC PC-8801 computer in the store's computer section to port the game, enhancing the graphics and expanding the levels to twenty. In 1982, he founded his company, Thinking Rabbit, based in Takarazuka, Japan, and released this PC-8801 version as the first commercial Sokoban game in December.<ref>Template:Cite web</ref><ref>Template:Cite magazine</ref>

In August 1983, the Japanese magazine PC Magazine published Sokoban Extra Edition as a type-in program featuring ten new puzzles. This game was developed by Thinking Rabbit under request.<ref>Template:Cite magazine</ref>

In 1984, Thinking Rabbit published Sokoban 2, featuring a puzzle editor.<ref>Template:Cite magazine</ref>

Throughout the rest of the 1980s, new titles appeared on a variety of Japanese platforms, including home computers such as the MSX and PC-9801, and video game consoles such as the Famicom, Sega SG-1000, Sega Mega Drive, and Game Boy.<ref name="sokoban-book-table-history"/> These releases were developed either by Thinking Rabbit or by other companies under license.<ref>Template:Cite web</ref><ref>Template:Cite web</ref>

In 1987, Spectrum HoloByte, under license from ASCII, ported and adapted the MSX version of Sokoban to IBM PC, Apple II, and Commodore 64, adding features for the U.S. market. The game was released in the United States early in 1988 as Soko-Ban.<ref name="sokoban-japan-america">Template:Cite magazine</ref><ref>Template:Cite book</ref>

In Japan, further titles followed in the 1990s for the Super Famicom, Windows, Macintosh, and PlayStation.<ref name="sokoban-beep-history">Template:Cite web</ref>

Around 2000, Thinking Rabbit became inactive but remained a legal entity.<ref name="mr-hiroyuki-imabayashi-interview-thinking-rabbit">Template:Cite web</ref> In 2001, the Japanese software company Falcon acquired the copyright to the official Sokoban games and the trademarks for Sokoban and Thinking Rabbit,<ref>Template:Cite web</ref> becoming the official developer and licensor of the series. From 2004 to 2007, Falcon developed several titles for Japanese mobile phones.<ref>Template:Cite web</ref><ref>Template:Cite web</ref> Starting in 2015, it also developed several Sokoban titles for Windows and later the smartphone game Sokoban Touch, all published under the Thinking Rabbit brand.<ref name="sokoban-beep-history"/>

Critical reception

PC-8801 versions

• Template:Nihongo
  • A December 1983 issue of MICOMGAMES wrote that the puzzle's concept is simple but requires thinking comparable to Go or Shogi, and that "once you start playing, it is hard to stop" (translated from Japanese). The game's originality was rated 90 out of 100.<ref>Template:Cite magazine</ref>
  • In the PC Game Ranking Book, the game received a score of 94 out of 100 points.<ref name="review-pc-game-ranking-book-sokoban">Template:Cite magazine</ref>

    Total Point	94
    Item	Difficulty	Addictiveness	Story	Originality	Value for money
    Stars (maximum 5)	4	5	5	5	5

IBM PC, Commodore 64, Apple II versions

• Soko-Ban
  • In 1988, Soko-Ban received a positive review from Computer Gaming World for its IBM PC and Commodore 64 versions, which described the game as simple yet mentally challenging, and noted its addictive nature.<ref name="CGW1988">Template:Cite magazine</ref>
  • The German magazine Happy Computer in its January 1988 issue gave the IBM PC version a rating of 87 out of 100, and called it "a brilliant, relaxed logic puzzle that keeps you thinking without pressure" (translated from German).<ref name="review-happy-computer-soko-ban">Template:Cite magazine</ref>

    Item	Graphics	Sound and Music	Happy (magazine) Rating
    Score	78	16	87

  • In Dragon magazine's mini-reviews, Hartley, Patricia, and Kirk Lesser rated the IBM PC version 4.5 out of five stars.<ref name="review-dragon-soko-ban">Template:Cite magazine</ref>
  • In the Computer Entertainer newsletter, the Apple II version was recommended and received 3.5 out of four stars for graphics, with the same rating for gameplay and entertainment.<ref>Template:Cite magazine</ref>

Famicom Disk System versions

• Template:Nihongo
  • In the Japanese Family Computer magazine's All Catalog supplement, it was called "a pioneering puzzle game" (translated from Japanese) and received 13.45 out of 25 points.<ref name="review-family-computer-all-catalog-fd-namida-no-sokoban-supesharu">Template:Cite journal</ref>

    Item	Characters	Music	Controls	Addictiveness	Originality	Overall
    Score	3.79	2.51	2.53	2.05	2.57	13.45

Game Boy versions

• Boxxle
  • In the June 1990 issue of Game Player's magazine, Tom R. Halfhill reviewed Boxxle, stating that it also required careful planning or plenty of trial and error (usually both). He noted that the game's 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.<ref name="boxxle-review">Template:Cite magazine</ref>
• Template:Nihongo
  • Computer and Video Games magazine rated the game 88% overall, indicating it as one of the "simple but effective puzzle games" for Game Boy. It compared the game's addictiveness with Tetris, stating the game "is an infuriatingly addictive little title; not quite on a par with Tetris, but not far off."<ref name="review-computer-and-video-games-sokoban">Template:Cite magazine</ref>

    Item	Graphics	Sound	Value	Playability	Overall
    Score	82%	76%	81%	88%	88%

  • Famitsu gave it a score of 25 out of 40.<ref name="review-famitsu-gb-sokoban">Template:Cite web</ref>
  • In the Japanese Family Computer magazine's All Catalog supplement, the game was described as having simple gameplay that made it great. The game received 18.78 out of 30 points.<ref name="review-family-computer-all-catalog-gb-sokoban">Template:Cite journal</ref>

    Item	Characters	Music	Controls	Addictiveness	Value for money	Originality	Overall
    Score	3.02	2.99	3.31	3.26	3.10	3.10	18.78

• Template:Nihongo
  • In the Japanese Family Computer magazine's All Catalog supplement, it was noted that this second installment was significantly more difficult. It received 17.65 out of 30 points.<ref name="review-family-computer-all-catalog-gb-sokoban2">Template:Cite journal</ref>

    Item	Characters	Music	Controls	Addictiveness	Value for money	Originality	Overall
    Score	2.81	2.86	3.01	3.14	2.91	2.92	17.65

Sega Genesis versions

• Shove It!
  • In the June 1990 issue of Game Player's magazine, Tom R. Halfhill reviewed Shove It!, noting it was a challenging game that required players to plan their moves carefully and that its unhurried pace was a refreshing respite from frenzied action games. However, all 160 puzzles were essentially the same.<ref name="shove-it-review">Template:Cite magazine</ref>
• Template:Nihongo
  • In the March 1990 issue of the Japanese magazine BEEP! Mega Drive, the game received a total score of 25 out of 40. Three of the four reviewers recommended it for puzzle enthusiasts. One reviewer questioned the release of Sokoban on the Mega Drive, wondering whether people would buy the console specifically to play a puzzle game; another appreciated the user-friendly gameplay but noted its dated feel; and one commented that he did not find the game's main selling points—enhanced art and its 250 levels that could take months to complete—particularly appealing.<ref name="review-beep-mega-drive-shijou-saidai-no-sokoban">Template:Cite magazine</ref>

    Item	Reviewer 1	Reviewer 2	Reviewer 3	Reviewer 4	Overall
    Score	5	6	8	6	25

  • Famitsu gave it a score of 23 out of 40.<ref name="review-famitsu-sg-shijo-saidai-no-sokoban">Template:Cite web</ref>

Game Gear versions

• Template:Nihongo
  • Famitsu gave it a score of 25 out of 40.<ref name="review-famitsu-gg-sokoban">Template:Cite web</ref>

TurboGrafx-16 versions

• Boxyboy
  • In the December 1990 issue of Game Player's magazine, Tom R. Halfhill 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.<ref name="boxyboy-review">Template:Cite magazine</ref>
• Template:Nihongo
  • Famitsu gave it a score of 27 out of 40.<ref name="review-famitsu-tg16-sokoban-world">Template:Cite web</ref>

PlayStation versions

• Template:Nihongo
  • Famitsu gave it a score of 25 out of 40.<ref name="review-famitsu-ps-ultimate-sokoban">Template:Cite web</ref>
• Template:Nihongo
  • Famitsu gave it a score of 22 out of 40.<ref name="review-famitsu-ps-sokoban-basic">Template:Cite web</ref>
• Template:Nihongo
  • Famitsu gave it a score of 22 out of 40.<ref name="review-famitsu-ps-sokoban-nanmon-shinan">Template:Cite web</ref>

Games

Since its debut in 1982, Sokoban has been released on various platforms, primarily in Japan but also in other regions. Most titles are independent, though a few are sequels.

Titles in the Sokoban series<ref name="sokoban-page-history">Template:Cite web</ref><ref name="sokoban-book-table-history">Template:Cite book</ref>

Region	Title	Release	Platform	Developer	Publisher
Japan	Template:Nihongo	1982-1983	NEC PC-8801 NEC PC-6001mkII Sharp MZ-2000 Sharp X1	Thinking Rabbit	Thinking Rabbit
	Template:Nihongo	1983	NEC PC-8801		Template:Ill
	Template:Nihongo	1984	NEC PC-8801 NEC PC-8001mkII Fujitsu FM-7 Sharp X1		Thinking Rabbit
	Template:Nihongo	1984	MSX	ASCII	ASCII
	Template:Nihongo	1984	MSX
	Template:Nihongo	1985	Game Pocket Computer	Epoch	Epoch
	Template:Nihongo	1985	SG-1000	Sega	Sega
	Template:Nihongo	1986	Famicom Disk System	ASCII	ASCII
	Template:Nihongo	1989	NEC PC-9801 Sharp X68000 Sharp X1 MSX2 FM Towns	Thinking Rabbit	Thinking Rabbit
	Template:Nihongo	1989	Game Boy	Atelier Double	Pony Canyon
	Template:Nihongo	1990	Game Boy
	Template:Nihongo	1990	Namco System 1	Namco	Namco
	Template:Nihongo	1990	Sega Genesis	Template:Ill	Masaya
	Template:Nihongo	1990	Game Gear	Thinking Rabbit	Riverhill Soft
	Template:Nihongo	1990	TurboGrafx-16	Media Rings	Media Rings
	Template:Nihongo	1991	NEC PC-9801	Thinking Rabbit	Thinking Rabbit
	Template:Nihongo	1993	Super Famicom	Thinking Rabbit	Pack-In-Video
	Template:Nihongo	1995	Windows	Thinking Rabbit	Itochu
	Template:Nihongo	1996	Macintosh
	Template:Nihongo	1996	PlayStation
	Template:Nihongo	1997	Windows Macintosh
	Template:Nihongo	1997	PlayStation
	Template:Nihongo	1998	PlayStation
	Template:Nihongo	1998	Windows
	Template:Nihongo	1998	Windows
	Template:Nihongo	1998	Windows	Thinking Rabbit	Template:Ill
	Template:Nihongo	1999	Game Boy	J Wing	Template:Ill
	Template:Nihongo	1999	Super Famicom	Atelier Double	Nintendo
	Template:Nihongo	1999 2000	PlayStation Windows	Unbalance	Unbalance
	Template:Nihongo	2000	Windows	Unbalance	Unbalance
	Template:Nihongo	2004	EZweb i-mode	Falcon	Square Enix Dwango
	Template:Nihongo (1/2/3)	2004	EZweb		Square Enix
	Template:Nihongo (1-1/1-2/1-3/2-1/2-2/2-3/3-1/3-2/3-3)	2004-2005	i-mode		Dwango
	Template:Nihongo	2007	i-mode	Konami	Konami
	Template:Nihongo	2015	Windows	Falcon	Thinking Rabbit
	Template:Nihongo	2015	Windows
	Template:Nihongo	2016	Windows
	Template:Nihongo	2016	Windows
	Template:Nihongo	2018	Windows
North America	Soko-Ban	1988	IBM PC Commodore 64 Apple II	Spectrum HoloByte	Spectrum HoloByte
	Shove It! The Warehouse Game	1990	Sega Genesis	Template:Ill	DreamWorks
	Boxyboy	1990	TurboGrafx-16	Media Rings	NEC
	Boxxle	1990	Game Boy	Atelier Double	FCI
	Boxxle II	1992	Game Boy
Worldwide	Sokoban Touch	2016	Android iOS	Falcon	Thinking Rabbit
	The Sokoban	2021	Nintendo Switch PlayStation 4	Template:Ill	Unbalance

Name genericization

The name Sokoban is a registered trademark for video game titles. However, the core mechanic of pushing boxes to storage locations on a grid is not protected by intellectual property rights. This has enabled others to create many unofficial versions.<ref>Template:Cite book</ref> Consequently, the term has become genericized, making it synonymous with the box-pushing puzzle genre established by the Sokoban titles by Thinking Rabbit and later adopted in games by others using the same core mechanic.<ref name="block-dude-puzzles">Template:Cite conference</ref>

Cultural impact

The active fan community has created thousands of custom puzzles spanning a wide range of difficulty,<ref name="community-puzzles">Template:Cite journal</ref> as well as software tools, including puzzle editors, solvers,<ref name="non-academic-solvers">Several efficient Sokoban solvers aim to find short, but not necessarily optimal, solutions, including JSoko, YASS, and Takaken. Template:Cite conference</ref> and solution optimizers.<ref name="block-dude-puzzles-software-tools">Template:Cite conference</ref>

Derivatives and variants

Official titles

A few official Sokoban games introduced modifications to the core mechanic of pushing boxes to storage locations in a warehouse.

• Template:Nihongo – includes a mode where you can use tools such as ropes.<ref name="review-family-computer-all-catalog-fd-namida-no-sokoban-supesharu"/>

• Template:Nihongo – features themed stages with either time limits, underwater boxes that can float up, disappearing boxes, or boxes with electrical wiring.<ref>Template:Cite web</ref>

• Template:Nihongo – offers a story mode in which the player must push enemies into holes and push puppets onto magic circles.<ref>Template:Cite web</ref>

• Template:Nihongo – an action-puzzle game in which the player shoot orbs and fill holes with rocks.<ref>Template:Cite web</ref>

Similar games

Several games are based on Sokoban, introducing new mechanics or objectives. Examples include:

• Picoban – the goal is to reach a teleport stone, pushing orbs onto buttons or collecting keys.<ref name="picoban">Template:Cite web</ref>

• Beanstalk – different items must be pushed into a target square in a fixed sequence.<ref name=beanstalk>Template:Cite journal</ref>

• Pukoban – the character can pull boxes.<ref name=pukoban>Template:Cite conference</ref>

• Sokoboxes Duo – two pushers must collaborate to solve the puzzle.<ref name="sokoboxes-duo">Template:Cite web</ref>

Variants

• Hexoban – uses a hexagonal grid instead of a square grid, allowing movements in six directions instead of four.<ref name="hexoban">Template:Cite web</ref>

• Multiban – the puzzle contains more than one pusher.<ref name="multiban">Template:Cite web</ref>

Program features

Some unofficial Sokoban programs feature 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.<ref>Template:Cite web</ref>

Gameplay

The game of Sokoban takes place in a warehouse, viewed from above, composed of walls and floor squares. A floor square may be empty, occupied by the player, or occupied by a box. Some floor squares are marked as storage locations. The number of storage locations equals the number of boxes. The objective of the puzzle is to push all boxes onto storage locations.<ref name=sokoban-pricai-96/>

The player can move one square at a time, either horizontally or vertically, onto an empty floor square.<ref>Template:Cite magazine</ref> 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. Pulling boxes is not possible.<ref name="sokoban-rules">Template:Cite web</ref>

Playing Sokoban requires thinking several steps ahead and visualizing all possible outcomes.<ref>Template:Cite magazine</ref> Players should think carefully and thoroughly before pushing a box to prevent it getting trapped against a wall or other boxes.<ref>Template:Cite magazine</ref> A bad move can cause a deadlock from which the puzzle cannot be solved, regardless of subsequent moves.<ref>Template:Cite conference</ref>

Deadlocks

Common deadlocks are:<ref name="deadlocks-types">Template:Cite magazine</ref><ref name="sokoban-book-deadlocks">Template:Cite book</ref>

File:Sokoban deadlocks.png

Two boxes are placed together along a wall. Each box blocks the other from being moved. 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.

Computer science 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.<ref>Template:Cite journal</ref><ref>Template:Cite journal</ref> Further work proved it is also PSPACE-complete.<ref>Template:Cite journal</ref><ref>Template:Cite thesis</ref>

Solving non-trivial Sokoban puzzles is difficult for computers because of the high branching factor (many legal pushes at each turn) and the considerable search depth (many pushes needed to reach a solution).<ref>Template:Cite journal</ref><ref>Template:Cite web</ref> Even small puzzles can require lengthy solutions.<ref>Template:Cite web</ref>

The Sokoban game provides a challenging testbed for developing and evaluating planning techniques.<ref>Template:Cite thesis</ref> 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.<ref>Template:Cite thesis</ref><ref>Template:Cite journal</ref> A later solver, Festival, introduced the FESS search algorithm and became the first automatic system to solve all ninety puzzles in the widely used XSokoban test suite.<ref>Template:Cite conference</ref><ref>Template:Cite web</ref> Despite these advances, even the most sophisticated solvers cannot solve many complex puzzles that humans can solve with time and effort, using their ability to plan, recognize patterns, and reason about long-term consequences.<ref name="computers-and-humans-solving">Template:Cite journal</ref><ref name="lets-logic-statistics">Template:Cite web</ref><ref>Template:Cite web</ref>

Commercial success

The first Sokoban title was a commercial success in Japan, selling over 25,000 copies by July 1984.<ref name="sales-1984-07">Template:Cite magazine</ref><ref name="sales-1984-06">Template:Cite magazine</ref><ref name="sales-1985-03">Template:Cite magazine</ref>

Early Sokoban titles released for numerous Japanese home computer systems such as the NEC PC-9801 and Sharp X1 were a hit, selling over 100,000 copies in total.<ref name="sales-japanese-pc-platforms">Template:Cite magazine</ref>

Spectrum Holobyte acknowledged that before 1988, over 400,000 copies of the game were sold in Japan, considering it a commercial success. This figure referred to the Japanese Sokoban title for MSX published by ASCII in 1984. The U.S. Soko-Ban title, sold over 50,000 units by mid-September of 1988.<ref name="Incider1988">Template:Cite magazine</ref><ref name="sokoban-japan-america"/>

See also

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

External links

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