Sokoban

Sokoban is a classic transport puzzle where the player controls a warehouse keeper who must push crates onto designated storage locations. The player can move in four directions and can push (never pull) one crate at a time. The challenge lies in planning moves carefully, as pushing a crate into a corner or against a wall can make the puzzle unsolvable. Sokoban is deceptively simple in concept but can be extraordinarily difficult, with some levels requiring hundreds of moves to solve.

Rules

1. The player character (the warehouse keeper) moves on a grid — up, down, left, or right.
2. The level contains crates (boxes) and target locations (marked with dots, diamonds, or darker floor tiles).
3. The player can push a crate by walking into it, provided the space behind the crate is empty (not a wall or another crate).
4. The player cannot pull crates, push two crates at once, or walk through walls or crates.
5. The level is solved when every crate is placed on a target location.
6. Some levels have the same number of crates and targets; others may have more targets than crates.

Strategies

• Avoid Corners: A crate pushed into a corner (where two walls meet) is permanently stuck unless that corner is a target location. Always think about whether a push could result in a dead state.
• Avoid Wall Hugging: A crate pushed flat against a long wall can only slide along that wall. If no target exists on that wall, the crate is effectively stuck.
• Work Backward: Visualize the final state (all crates on targets) and think about what the last few moves must be. Working backward from the solution can reveal the required approach.
• Solve the Hardest Part First: Identify the most constrained crate or target — the one with the fewest possible approach paths. Solve that one first, then work outward.
• Preserve Mobility: Keep open corridors free for maneuvering. Don't block your own movement paths by pushing crates into positions that cut off access.
• Use Undo Liberally: In digital versions, undo is essential. Push a crate tentatively, explore the consequences, and undo if it leads to a dead state.

Sokoban was created in 1981 by Hiroyuki Imabayashi, a student at a Japanese university, as a submission to a computer game competition. The name "Sokoban" means "warehouse keeper" in Japanese (倉庫番). The game was published in December 1982 by Thinking Rabbit, a Japanese software company, for various Japanese home computer systems including the NEC PC-8801 and Sharp MZ series.

The original game contained 90 levels of increasing difficulty, designed entirely by Imabayashi. The elegant simplicity of the rules — four-directional movement and pushing — combined with the extraordinary depth of the puzzles made Sokoban an instant classic. The game was ported to virtually every computer platform of the 1980s and 1990s, including DOS, Macintosh, Amiga, and numerous consoles.

Sokoban has had a profound influence on both puzzle game design and computer science. In 1997, researchers proved that Sokoban is PSPACE-complete, meaning it is among the most computationally difficult problems in its class. This means that there is no known efficient algorithm to solve arbitrary Sokoban levels — even computers must essentially use brute-force search with clever optimizations. Despite this theoretical difficulty, specialized Sokoban solvers have been developed, with programs like "Festival" and "YASS" capable of solving many complex levels.

The puzzle has inspired countless variations and spiritual successors. Notable examples include "Boxxle" for Game Boy (1989), "Kwirk" (1989), Stephen Lavelle's "Stephen's Sausage Roll" (2016), and "Baba Is You" (2019), which deconstructs the push-puzzle genre by making the rules themselves pushable objects. The International Sokoban community maintains extensive collections of player-designed levels — the most famous being the "Microban" and "Sasquatch" collections by David W. Skinner. Annual Sokoban competitions challenge designers to create increasingly ingenious levels, and the game remains one of the most studied and beloved puzzles in the history of computing.