🇮🇷 Iran Proxy | https://www.wikipedia.org/wiki/Sokoban
Jump to content

Sokoban

From Wikipedia, the free encyclopedia

Sokoban
Sokoban official fan kit banner
GenrePuzzle
DevelopersThinking Rabbit
ASCII
Itochu
Unbalance [ja]
Falcon
Other
PublishersThinking Rabbit
ASCII
Itochu
Unbalance [ja]
Other
CreatorHiroyuki Imabayashi
Platforms
Various
First releaseSokoban
1982
Latest releaseThe Sokoban
2021

Sokoban[a] is a series of puzzle video games in which the player pushes boxes around in a warehouse. The aim of the game is to get the boxes onto 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.

Gameplay

[edit]
The puzzles in Sokoban require the player to push boxes to designated spots (shown as red dots in the animation) in the game world.

Sokoban takes place in a warehouse viewed from above and 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.[1]

The player can move one square at a time, either horizontally or vertically, onto an empty floor square.[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. Pulling boxes is not possible.[3]

Playing Sokoban requires thinking several steps ahead and visualizing all possible outcomes.[4] Players must think carefully and thoroughly before pushing a box to prevent it from being permanently trapped against a wall or other boxes,[5] or in a dead end.[6] These are deadlocks from which the puzzle cannot be solved, regardless of subsequent moves.[7]

History

[edit]

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,[8] where the player pushed luggage to act as a wall to prevent radiation.[9] Imabayashi conceptualized that in the warehouse, the boxes had to be organized, but that they themselves would hinder the organizing process. He worked to design 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.[10][11]

In 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.[12] In 1984, Thinking Rabbit published Sokoban 2, featuring a puzzle editor.[13] 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.[14] These releases were developed either by Thinking Rabbit or by other companies under license agreements.[15] In 1987, Spectrum HoloByte, based in California, U.S., acquired a license from Japan's ASCII, and ported and adapted the MSX version of Sokoban to IBM PC, Apple II, and Commodore 64, adding features for the U.S. market, and released it as Soko-Ban in the United States early in 1988.[16][17] In the 1990s, the official series continued in Japan with further titles for the Super Famicom, Windows, Macintosh, and PlayStation.[18]

Around 2000, Thinking Rabbit became inactive but remained a legal entity.[9] In 2001, the Japanese software company Falcon acquired the copyright to the official Sokoban games and the trademarks for Sokoban and Thinking Rabbit,[19] becoming the official developer and licensor of the series. From 2004 to 2007, Falcon developed several titles for Japanese mobile phones.[20][21] Starting in 2015, it also developed several Sokoban titles for Windows and, in 2016, the smartphone game Sokoban Touch, all published under the Thinking Rabbit brand.[18] In 2018, Falcon also developed three Sokoban titles for Japanese digital terrestrial television broadcasters.[18]

Games

[edit]

Since its debut in 1982, over 40 official Sokoban games have been released on various platforms, primarily in Japan but also in other regions. Most titles are standalone, though a few are sequels. The core mechanic of pushing boxes to storage locations has remained consistent in almost all official titles, with few exceptions:

  • One title includes stages with different core mechanics:
    • Ultimate Sokoban (究極の倉庫番) – features four themed stages with either strict move limits, boxes that float unless regularly touched or stored, a box that is a ghost, or boxes that, when stored, must complete an electrical circuit.[22]
  • Two titles include variant game modes:
    • Sokoban Special of Tears (涙の倉庫番スペシャル) – features a mode where the player can use tools such as ropes.[23]
    • Sokoban Legend: Land of Light and Darkness (倉庫番伝説 光と闇の国) – offers a story mode in which the player must push enemies into holes and push puppets onto magic circles.[24]
  • One title departs entirely from Sokoban:
    • Power Sokoban (Power倉庫番) – is an action-puzzle game that deviates from the warehouse keeper mechanic; the player shoots orbs and fills holes with rocks.[25]
Titles in the Sokoban series[18][14]
Title Release Platform Developer Publisher Region
Sokoban (倉庫番) 1982-1983 NEC PC-8801
NEC PC-6001mkII
Sharp MZ-2000
Sharp X1 		Thinking Rabbit Thinking Rabbit Japan
Sokoban Extra Edition (倉庫番[番外編]) 1983 NEC PC-8801 PC Magazine [ja] Japan
Sokoban 2 (倉庫番2) 1984 NEC PC-8801
NEC PC-8001mkII
Fujitsu FM-7
Sharp X1 		Thinking Rabbit Japan
Sokoban ROM Pack (倉庫番 ROM Pack) 1984 MSX ASCII ASCII Japan
Sokoban Tape Pack (倉庫番 Tape Pack) 1984 MSX
Sokoban (倉庫番) 1985 Game Pocket Computer Epoch Epoch Japan
Sokoban (倉庫番) 1985 SG-1000 Sega Sega Japan
Sokoban Special of Tears (涙の倉庫番スペシャル) 1986 Famicom Disk System ASCII ASCII Japan
Soko-Ban 1988 IBM PC
Commodore 64
Apple II 		Spectrum HoloByte[16] Spectrum HoloByte North America
Sokoban Perfect (倉庫番Perfect) 1989 NEC PC-9801
Sharp X68000
FM Towns 		Thinking Rabbit Thinking Rabbit Japan
MSX2 Microcabin [ja] Microcabin
Sokoban (倉庫番)
BoxxleNA 		1989 Game Boy Pony Canyon Pony CanyonJP
FCINA 		Japan, North America
1991NA
Sokoban 2 (倉庫番2)
Boxxle IINA 		1990 Game Boy
1992NA
Sokoban Deluxe (倉庫番Deluxe) 1990 Namco System 1 Namco Namco Japan
The Greatest Sokoban in History (史上最大の倉庫番)
Shove It! The Warehouse GameNA 		1990 Sega Genesis NCS [ja][26] Masaya [ja]JP
DreamWorksNA 		Japan, North America
Sokoban (倉庫番) 1990 Game Gear Riverhill Soft Riverhill Soft Japan
Sokoban World (倉庫番World)
BoxyboyNA 		1990
1991 		TurboGrafx-16 Media Rings Media RingsJP
NECNA 		Japan, North America
Sokoban Revenge (倉庫番Revenge) 1991 NEC PC-9801 Thinking Rabbit Thinking Rabbit Japan
Super Sokoban (Super倉庫番) 1993 Super Famicom Pack-In-Video Pack-In-Video Japan
Sokoban for Windows (倉庫番 for Windows) 1995 Windows Itochu Itochu Japan
Sokoban for Macintosh (倉庫番 for Macintosh) 1996 Macintosh
Ultimate Sokoban (究極の倉庫番) 1996 PlayStation
Sokoban Basic (倉庫番ベーシック) 1997 PlayStation
Sokoban Selection (倉庫番セレクション) 1997 Windows
Macintosh
Sokoban Special 102 (倉庫番スペシャル102) 1998 Windows Fujitsu Parex Japan
Ultimate Sokoban (究極の倉庫番) 1998 Windows Itochu Japan
Sokoban Basic 2 (倉庫番ベーシック2) 1998 PlayStation
Sokoban Basic (倉庫番ベーシック) 1998 Windows Unbalance [ja] Unbalance Japan
Power Sokoban (Power倉庫番) 1999 Super Famicom Nintendo Nintendo Japan
Sokoban: Guide to Difficult Puzzles (倉庫番 難問指南) 1999 PlayStation Unbalance Unbalance Japan
Sokoban Legend: Land of Light and Darkness (倉庫番伝説 光と闇の国) 1999 Game Boy J Wing J Wing [ja] Japan
Sokoban (倉庫番) 2000 Windows Unbalance Unbalance Japan
Sokoban: Guide to Difficult Puzzles (倉庫番 難問指南) 2000 Windows
Sokoban First Step (倉庫番ファーストステップ) 2004 EZweb
i-mode 		Falcon[20][21] Square Enix
Dwango 		Japan
Sokoban Perfect (倉庫番パーフェクト)
(1/2/3) 		2004 EZweb Square Enix Japan
Sokoban Perfect (倉庫番パーフェクト)
(1-1/1-2/1-3/2-1/2-2/2-3/3-1/3-2/3-3) 		2004-2005 i-mode Dwango Japan
Konami Wai Wai Sokoban (コナミワイワイ倉庫番) 2007 i-mode Konami[27] Konami Japan
Sokoban Perfect Plus A-side (倉庫番パーフェクト プラス A面) 2015 Windows Falcon Thinking Rabbit Japan
Sokoban Perfect Plus B-side (倉庫番パーフェクト プラス B面) 2015 Windows
Sokoban First Step Plus (倉庫番ファーストステップ プラス) 2016 Windows
Sokoban Revenge Reprint (倉庫番リベンジ 復刻版) 2016 Windows
Sokoban Touch 2016 Android
iOS 		Worldwide
Sokoban Smart (倉庫番スマート) 2018 Windows Japan
Chukyo-kun's Sokoban (チュウキョ～くんの倉庫番) 2018 Digital terrestrial television Falcon Chukyo Television Japan
Dayon's Sokoban (だよんの倉庫番) 2018 Digital terrestrial television Miyagi Television
Kumo Jiro's Sokoban (くもジローの倉庫番) 2018 Digital terrestrial television Nippon Television
Minna no Sokoban (みんなの倉庫番)JP
The Sokoban 		2019JP Nintendo Switch
PlayStation 4 		Unbalance Unbalance Japan
2021 Worldwide

Reception

[edit]

The first Sokoban title was a best seller in Japan, selling over 25,000 copies by July 1984.[28][29][30] Early Sokoban titles released for several Japanese home computer systems, including the NEC PC-9801 and Sharp X1, were a hit, selling over 100,000 copies in total.[31] The Japanese Sokoban title for MSX published by ASCII sold over 400,000 copies and was considered a commercial success.[16][32] The U.S. version Soko-Ban sold over 50,000 copies by mid-September 1988.[16] In 2018, Chukyo Television Broadcasting reported that the series in total had sold over 4.1 million copies worldwide since its 1982 debut.[33]

The Sokoban series was noted by the Famicom Winning Book in 1990 as an established puzzle game classic that was still discussed for its difficulty and depth, ported to multiple platforms, and still being published.[34] Reviewers frequently highlighted the games' addictive quality. Reviewing the first Sokoban, Micomgames staff stated that players would find it difficult to stop playing.[35] In 1988, Roy Wagner of Computer Gaming World suggested that anyone trying the US version, Soko-Ban, would likely remain absorbed for a prolonged period.[36] Computer Entertainer newsletter stated that playing it was fascinating and almost impossible to stop.[37] Regarding console versions, Computer and Video Games magazine staff called Sokoban for Game Boy "an infuriatingly addictive little title" and compared its addictiveness to Tetris.[38]

Commentators often highlighted either the simplicity of the game or the strategic thinking required to solve its puzzles, and one review juxtaposed both. Micogames staff described the puzzles in the first Sokoban as simple but requiring thinking comparable to Go or Shogi.[35] Computer and Video Games magazine staff described Sokoban for Game Boy as one of the console's "simple but effective puzzle games."[38] Family Computer magazine's All Catalog supplement described it as great because of its simple gameplay.[39] Reviewers for the German magazine Happy Computer called it "a brilliant, relaxed logic puzzle that keeps you thinking without pressure" and recommended that players carefully observe a level before moving a box.[40] Wagner summarized Soko-Ban as "very playable and mentally challenging."[36] In Dragon magazine, Hartley, Patricia, and Kirk Lesser, considered Soko-Ban a strategy game.[41] In Game Player's magazine, Tom R. Halfhill reviewed Shove It! for Sega Genesis, noting it was challenging and would require players to plan their moves carefully.[42] Moreover, reviewing Boxxle for Game Boy, he stated that it required careful planning or plenty of trial and error (usually both).[43]

The lack of variety in the series became a point of criticism. Tom R. Halfhill considered all puzzles in Shove It! essentially the same.[42] He noted that Boxxle's gameplay could become repetitive because the only variations in the screens were the number and arrangement of crates and the shape of the rooms.[43] Additionally, reviewing Boxyboy for TurboGrafx-16, he noted that it was "virtually identical" to Shove It! and Boxxle.[44]

Legacy

[edit]

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.[45] Consequently, the term "Sokoban," which refers to the official Sokoban games, has become genericized and is also used to describe the genre of box-pushing puzzle games that adopt the same core mechanic.[46]

Several independently developed games are based on Sokoban, introducing new mechanics or objectives; for example, Sokomania 2: Cool Job features switches, conveyor belts, and boxes that continue moving after being pushed once.[47] Additionally, thousands of custom Sokoban puzzles,[48] spanning a wide range of difficulty, have been created and are freely available on the internet,[49] as well as software tools, including solvers,[50] and solution optimizers.[46]

Research

[edit]

The computational problem of solving Sokoban puzzles has been studied using computational complexity theory, and is known to be NP-hard[51][52] and PSPACE-complete.[53][54] 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).[55][56] Even small puzzles can require lengthy solutions.[57]

Sokoban puzzles provide a challenging testbed for developing and evaluating planning techniques.[58] 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.[59][60] 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.[61][62] 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.[63][64][65]

See also

[edit]

Notes

[edit]
  1. ^ Japanese: 倉庫番, Hepburn: Sōko-ban; lit. 'warehouse keeper'[1]

References

[edit]
  1. ^ a b Yoshio Murase; Hitoshi Matsubara; Yuzuru Hiraga (1996). Norman Foo; Randy Goebel (eds.). Automatic Making of Sokoban Problems. Springer Science & Business Media. p. 592. ISBN 978-3-540-61532-3.
  2. ^ 倉庫番 [Sokoban]. ログイン (雑誌) [ja] (in Japanese). August 1983. p. 125.
  3. ^ "ja:倉庫番とは" [What is Sokoban]. Sokoban.jp (in Japanese). Falcon Co., Ltd. Archived from the original on September 19, 2025. Retrieved September 19, 2025.
  4. ^ "Micomgames-magazine-dec-1983-sokoban" 倉庫番. MICOMGAMES (in Japanese). Vol. 1, no. 1. December 1983. p. 38.
  5. ^ 倉庫番 [Sokoban]. ログイン (雑誌) [ja] (in Japanese). August 1983. p. 125.
  6. ^ "ja:こうなるとアウトだよ" [If it gets to this, it's unsolvable]. ja:ファミコン通信 (in Japanese). July 1986. p. 30.
  7. ^ Jean-Noël Demaret; François Van Lishout; Pascal Gribomont (2008). Hierarchical Planning and Learning for Automatic Solving of Sokoban Problems (PDF). pp. 1, 2. Archived from the original (PDF) on June 4, 2025. Retrieved June 4, 2025.
  8. ^ "Aldebaran". 月刊マイコン [ja] (in Japanese). January 1980. pp. 22–28.
  9. ^ a b "My conversation with Mr Hiroyuki Imabayashi". Archived from the original on December 4, 2025. Retrieved November 17, 2025.
  10. ^ "ja:ごあいさつ" [Greetings]. Sokoban.jp (in Japanese). Falcon Co., Ltd. Archived from the original on August 25, 2025. Retrieved August 25, 2025.
  11. ^ 考えるウサギはパソコンの野を駆ける! [The thinking rabbit runs through the fields of the computer!]. LOGiN [ja] (in Japanese). December 1983. pp. 136–137.
  12. ^ 倉庫番[番外編] [Sokoban Extra Edition]. PCマガジン [ja] (in Japanese). August 1983. p. 52.
  13. ^ 倉庫番2. ログイン (雑誌) [ja] (in Japanese). July 1985. p. 76.
  14. ^ a b Tanaka, Junji; Himabayashi, Hiroyuki; Ishii, M. (1986). ja:THE 倉庫番 [The Sokoban] (in Japanese). SCALE. p. 112. ISBN 4-88239-606-8.
  15. ^ "ja:ごあいさつ" [Greetings]. Sokoban.jp (in Japanese). Falcon Co., Ltd. Archived from the original on August 25, 2025. Retrieved August 25, 2025.
  16. ^ a b c d Ellison, Carol (December 1988). "Special Report: Why Japan Can't Write Software". PC Computing. Vol. 1, no. 5. Ziff‑Davis. p. 113.
  17. ^ Soko‑Ban (Video game manual). Spectrum Holobyte. 1988. p. 2.
  18. ^ a b c d "倉庫番の歴史" [The History of Sokoban]. Sokoban.jp (in Japanese). Falcon Co., Ltd. Archived from the original on September 17, 2025. Retrieved September 17, 2025.
  19. ^ "Sokoban Official Site". Sokoban.jp (in Japanese). Falcon Co., Ltd. Archived from the original on November 17, 2025. Retrieved November 17, 2025.
  20. ^ a b "ja:伝説の名作パズル：倉庫番" [Legendary Puzzle Masterpiece: Sokoban] (in Japanese). Archived from the original on May 2, 2007.
  21. ^ a b "ja:スクウェア・エニックス ポケットパズル" [Square Enix Pocket Puzzle] (in Japanese). Archived from the original on December 14, 2005.
  22. ^ Ultimate Sokoban 3D Polygon Puzzle & Cinema Manual (Video game manual) (in Japanese). Itouchu. 1996. pp. 13–14. Retrieved November 26, 2025.
  23. ^ "ja:ファミコンディスクカード ゲームボーイ スーパーファミコン オールカタログ" [FamicomDiskCard Gameboy SuperFamicom All Catalog]. Family Computer [ja] (in Japanese). Tokuma Shoten [ja]: 98. May 24, 1991.
  24. ^ "ja:Puzzle GAMES! – 倉庫番伝説・光と闇の国" [Puzzle GAMES! – Sokoban Legend: Land of Light and Darkness] (in Japanese). Archived from the original on November 4, 2025. Retrieved November 4, 2025.
  25. ^ "ja:POWER 倉庫番" [Power Sokoban]. Nintendo (in Japanese). Archived from the original on November 3, 2025. Retrieved November 3, 2025.
  26. ^ "ja:BEメガ・ドッグレース" [BE Mega Dog Race]. BEEP! Mega Drive [ja] (in Japanese). Vol. 6, no. 2. March 1990. p. 108.
  27. ^ "ja:ゴエモン、詩織、ニャミが『倉庫番』に登場!" [Goemon, Shiori, and Nyami appear in "Sokoban"!] (in Japanese). Archived from the original on June 8, 2013.
  28. ^ 倉庫番トラの巻 [The Sokoban Strategy Guide]. POPCOM (in Japanese). July 1984. p. 101.
  29. ^ ソフトハウス訪問 [Visiting a Software Company]. POPCOM (in Japanese). June 1984. p. 131.
  30. ^ 作者が語る自信のニューソフト [The creator proudly presents their new software]. POPCOM (in Japanese). March 1985. p. 29.
  31. ^ "ja:ゲーム徹底解剖" [Game Analysis]. BEEP! Mega Drive [ja] (in Japanese). November 1989. p. 56.
  32. ^ Lafe Low (November 1988). "News Line; Made in Japan". inCider. p. 14.
  33. ^ "中京テレビ、累計410万本以上の実績を持つ名作ゲームとコラボ　新規ゲーム『チュウキョ～くんの倉庫番』が データ放送通信コンテンツ「チュウキョ～くんランド」に誕生!". ＠Press (in Japanese). Chukyo Television Broadcasting. July 10, 2018. Archived from the original on December 1, 2025. Retrieved December 1, 2025.
  34. ^ "MDC 新着情報" [MDC Latest News]. ファミコン必勝本 (in Japanese). No. 88. February 2, 1990. p. 87.
  35. ^ a b "PART 2 脳みそ を 酷使 する の で あ" [Part 2 Because your brain will be overused]. MICOMGAMES (in Japanese). Vol. 1, no. 1. December 1983. p. 38.
  36. ^ a b Wagner, Roy (May 1988). "Puzzling Encounters" (PDF). Computer Gaming World. No. 47. pp. 42–43. Archived from the original (PDF) on June 3, 2025.
  37. ^ "Computer Entertainer". Computer Entertainer. Vol. 7, no. 4. July 1988. p. 9.
  38. ^ a b "Soko Ban". Computer and Video Games. No. 96. EMAP Publishing. November 1989. p. 119.
  39. ^ "ja:ファミコンディスクカード ゲームボーイ スーパーファミコン オールカタログ" [FamicomDiskCard Gameboy SuperFamicom All Catalog]. Family Computer [ja] (in Japanese). Tokuma Shoten [ja]. May 24, 1991. p. 199.
  40. ^ "Soko-Ban". Happy Computer (in German). Markt&Technik. January 1988. p. 86.
  41. ^ Lesser, Hartley; Lesser, Patricia; Lesser, Kirk (April 1988). Roger E. Moore (ed.). "The Role of Computers" (PDF). Dragon. No. 132. p. 84.
  42. ^ a b Halfhill, Tom R. (June 1990). "Shove It!". Game Player's. Vol. 2, no. 6. pp. 45–46. Archived from the original on November 28, 2025.
  43. ^ a b Halfhill, Tom R. (June 1990). "Boxxle". Game Player's. Vol. 2, no. 6. p. 90. Archived from the original on November 28, 2025.
  44. ^ Halfhill, Tom R. (December 1990). "Boxy Boy". Game Player's. Vol. 2, no. 12. p. 90. Archived from the original on November 28, 2025.
  45. ^ Marçal Mora Cantallops (2023). Rompecabezas: Cinco décadas de videojuegos y puzles (in Spanish). Héroes De Papel. ISBN 978-84-947149-3-1.
  46. ^ a b Austin Barr; Calvin Chung; Aaron Williams (2021). Block Dude Puzzles are NP-Hard (and the Rugs Really Tie the Reductions Together) (PDF). CCCG (2021). p. 1. Archived from the original (PDF) on September 26, 2025. Retrieved September 26, 2025.
  47. ^ "Sokomania 2: Cool Job Review (DSiWare)". Nintendo Life. May 17, 2014. Archived from the original on November 25, 2025. Retrieved November 25, 2025.
  48. ^ Tony Mott (2011). Frank Ritter; Simon Ward; Terry Burrows; Tamsin Oxford (eds.). 1001 Video Games You Must Play Before You Die. Tristan de Lancey. p. 96. ISBN 978-1-84403-681-3.
  49. ^ Petr Jarusek; Radek Pelánek (2010). "Difficulty Rating of Sokoban Puzzle" (PDF). Frontiers in Artificial Intelligence and Applications. 222: 140–150. doi:10.3233/978-1-60750-676-8-140. Archived from the original (PDF) on August 30, 2025.
  50. ^ Several efficient Sokoban solvers aim to find short, but not necessarily optimal, solutions, including JSoko, YASS, and Takaken. Balyo, Tomáš; Froleyks, Nils (2022). "AI Assisted Design of Sokoban Puzzles Using Automated Planning". In Wölfel, Matthias; Bernhardt, Johannes; Thiel, Sonja (eds.). ArtsIT, Interactivity and Game Creation. Springer. pp. 429–430. doi:10.1007/978-3-030-95531-1_29. ISBN 978-3-030-95531-1.
  51. ^ Michael Fryers; Michael Greene (1995). "Sokoban" (PDF). Eureka (54): 25–32. Archived from the original (PDF) on September 5, 2024.
  52. ^ Dorit Dor; Uri Zwick (1999). "SOKOBAN and other motion planning problems". Computational Geometry. 13 (4): 215–228. doi:10.1016/S0925-7721(99)00017-6.
  53. ^ Joseph C. Culberson (1997). "Sokoban is PSPACE-complete" (PDF). Technical Report TR 97-02, Dept. Of Computing Science, University of Alberta. Archived from the original (PDF) on May 28, 2024.
  54. ^ Robert Aubrey Hearn (2006). Games, Puzzles, and Computation (PDF) (PhD thesis). Massachusetts Institute of Technology. pp. 98–100. Archived from the original (PDF) on October 11, 2025. Retrieved October 11, 2025.
  55. ^ Andreas Junghanns; Jonathan Schaeffer (2001). "Sokoban: Improving the Search with Relevance Cuts" (PDF). Theoretical Computer Science. 252 (1–2): 5. doi:10.1016/S0304-3975(00)00080-3. Archived from the original (PDF) on June 4, 2025. Retrieved June 4, 2025.
  56. ^ Yaron Shoham (2020). "FESS Draft" (PDF). p. 3. Archived from the original (PDF) on July 31, 2025. Retrieved July 31, 2025.
  57. ^ David Holland; Yaron Shoham. "Theoretical analysis on Picokosmos 17". Archived from the original on June 7, 2016.
  58. ^ Timo Virkkala (2011). Solving Sokoban (PDF) (MSc thesis). University of Helsinki. p. 1. Archived from the original (PDF) on November 18, 2025.
  59. ^ Andreas Junghanns (1999). Pushing the Limits: New Developments in Single-Agent Search (PhD thesis). University of Alberta. doi:10.7939/R3W95103S.
  60. ^ Andreas Junghanns; Jonathan Schaeffer (2001). "Sokoban: Enhancing general single-agent search methods using domain knowledge". Artificial Intelligence. 129 (1–2): 219–251. doi:10.1016/S0004-3702(01)00109-6.
  61. ^ Yaron Shoham; Jonathan Shaeffer (2020). The FESS Algorithm: A Feature Based Approach to Single-Agent Search (PDF). 2020 IEEE Conference on Games (CoG). Osaka, Japan: IEEE. doi:10.1109/CoG47356.2020.9231929. Archived from the original (PDF) on June 4, 2025. Retrieved June 4, 2025.
  62. ^ Yaron Shoham (2020). "FESS presentation at the CoG conference (17.5 minutes)" (video). archive.org.
  63. ^ Petr Jarusek; Radek Pelánek (2010). "Difficulty Rating of Sokoban Puzzle" (PDF). Frontiers in Artificial Intelligence and Applications. 222: 140–150. doi:10.3233/978-1-60750-676-8-140. Archived from the original (PDF) on August 30, 2025.
  64. ^ "Let's Logic Bots Statistics" (PDF). Retrieved October 6, 2024.
  65. ^ "Sokoban Solver Statistics - Large Test Suite". Retrieved April 14, 2024.
[edit]
Retrieved from "https://en.wikipedia.org/w/index.php?title=Sokoban&oldid=1325959831"