"Every push closes a door. The puzzle is knowing which doors you can afford to close."

---

Prerequisites

Module	What You Used From It
Module 5 - Puzzle	Grid-based game state, tile-based movement, representing a discrete game world as a 2D array
Module 7 - Roguelike	Turn-based grid movement: the player occupies a grid cell and moves one step at a time in cardinal directions

---

Week 1: History & Design Theory

The Origin

Sokoban was created in 1981 by Hiroyuki Imabayashi, a college student in Japan, and published in 1982 by Thinking Rabbit. The name means "warehouse keeper," and the game is exactly that: you play a worker pushing crates onto marked storage locations in a warehouse. The rules fit on a napkin — move in four directions, push one crate at a time, cannot pull, cannot push two crates at once. Yet from these minimal rules emerges staggering complexity. Some Sokoban levels have been proven to require hundreds of moves to solve and are studied in computer science as examples of PSPACE-complete problems. Its genius is the gap between the simplicity of its rules and the depth of its challenges.

How the Genre Evolved

Sokoban (Hiroyuki Imabayashi, 1982): The original defined the entire genre with a ruleset so tight it has barely been modified in forty years. Player pushes boxes onto targets on a grid. Cannot pull. Cannot push more than one box. Its lasting influence comes from its purity.

Stephen's Sausage Roll (Increpare, 2016): Transformed the push puzzle into a three-dimensional spatial reasoning challenge. Instead of boxes, you push sausages that occupy two tiles and must be grilled on all sides. It demonstrated that the Sokoban framework could be extended in directions nobody had imagined.

Baba Is You (Arvi Teikari, 2019): Deconstructed the puzzle genre itself by making the rules of the game into pushable objects on the grid. "BABA IS YOU" is a sentence made of word-blocks; push "ROCK" into "IS" and "YOU" and suddenly you control the rocks instead. It proved that the Sokoban grid could be a platform for meta-game design.

What Makes It "Great"

A great push-block puzzle respects the player's intelligence. There are no reflexes to test, no time pressure, no random elements — just you and the grid and the consequences of your decisions. The satisfaction comes from the moment of insight: staring at a level for minutes, feeling stuck, and then suddenly seeing the one sequence of moves that threads every block to its target without trapping any of them. Every wall is there for a reason. Every empty space matters.

The Essential Mechanic

Spatial reasoning where objects only push, never pull — every move narrows your options.

---

Week 2: Build the MVP

What You're Building

A classic Sokoban game with 5-8 handcrafted levels of increasing difficulty. The player moves on a grid, pushes blocks onto target squares, and wins each level when all blocks are on targets. The game includes an undo system, dead-state detection, and a level serialization format.

Core Concepts (Must Implement)

1. Push Mechanics

The player can push a block by moving into it, but only if the space behind the block is empty. The player cannot pull blocks, and pushing two blocks at once is not allowed. These constraints are what make the puzzles work.

WALL = '#'
FLOOR = '.'
TARGET = 'x'
BLOCK = 'B'
PLAYER = 'P'
BLOCK_ON_TARGET = 'O'

function try_move(state, direction):
    player_pos = state.player_position
    dest = player_pos + direction
    behind = dest + direction

    tile_at_dest = state.grid[dest.y][dest.x]

    if tile_at_dest == WALL:
        return state    // cannot move into wall

    if tile_at_dest == BLOCK or tile_at_dest == BLOCK_ON_TARGET:
        tile_behind = state.grid[behind.y][behind.x]
        if tile_behind == WALL or tile_behind == BLOCK or tile_behind == BLOCK_ON_TARGET:
            return state    // cannot push into wall or another block
        new_state = state.clone()
        move_block(new_state, dest, behind)
        move_player(new_state, player_pos, dest)
        return new_state

    new_state = state.clone()
    move_player(new_state, player_pos, dest)
    return new_state

Why it matters: The push-only constraint is the entire game. If you could pull blocks, most Sokoban puzzles would become trivial. Once you push a block against a wall, it might be stuck there forever. This is what makes each move feel weighty.

2. Undo System

Every move pushes the entire game state onto a history stack. Pressing undo pops the most recent state and restores it. This is essential for puzzle games — without undo, a single mistake forces a full restart.

class UndoableGame:
    current_state: GameState
    history: Stack of GameState = []
    redo_stack: Stack of GameState = []

function make_move(game, direction):
    new_state = try_move(game.current_state, direction)
    if new_state != game.current_state:
        game.history.push(game.current_state)
        game.current_state = new_state
        game.redo_stack.clear()

function undo(game):
    if game.history.is_empty(): return
    game.redo_stack.push(game.current_state)
    game.current_state = game.history.pop()

function redo(game):
    if game.redo_stack.is_empty(): return
    game.history.push(game.current_state)
    game.current_state = game.redo_stack.pop()

Why it matters: Undo transforms puzzle games from frustrating trial-and-error into satisfying experimentation. The stack-based approach is clean: every state is an immutable snapshot, so undo is just swapping which snapshot is active. This is also a practical lesson in state management that applies far beyond games.

3. Puzzle State Validation

The game checks whether the current state is a win (all blocks on targets) after every move.

function is_level_complete(state):
    for target_pos in state.target_positions:
        if state.grid[target_pos.y][target_pos.x] != BLOCK_ON_TARGET:
            return false
    return true

function after_move(game):
    if is_level_complete(game.current_state):
        display_victory(moves=game.history.length)
        advance_to_next_level(game)

Why it matters: State validation is the feedback loop that makes the game satisfying. The instant the last block slides onto the last target, the player needs to know they won.

4. Level Design for Puzzles

Designing good Sokoban levels is a craft. Each level should have a unique solution path, a clear difficulty curve, and an "aha moment" where the player discovers the key insight.

level_design_principles = {
    "level_1": "Teach pushing: 1 block, 1 target, straight line",
    "level_2": "Teach turning: 1 block, 1 target, requires L-shaped push",
    "level_3": "Introduce order: 2 blocks, 2 targets, must push in correct order",
    "level_4": "Dead states: 2 blocks, wall corners, wrong push = stuck",
    "level_5": "Multi-step: 3 blocks, requires temporary parking of blocks",
    "level_6": "Bottleneck: narrow corridor forces precise sequencing",
    "level_7": "Full puzzle: 4+ blocks, all concepts combined"
}

Why it matters: A Sokoban engine without good levels is like a piano without music. The code is just the instrument; the levels are the composition.

5. Dead-State Detection

A dead state occurs when a block is in a position from which it can never reach any target. The simplest case: a block pushed into a corner with no target there.

function is_simple_deadlock(state, block_pos):
    if is_on_target(state, block_pos): return false
    blocked_horizontal = (is_wall(state, block_pos + LEFT) or
                          is_wall(state, block_pos + RIGHT))
    blocked_vertical =   (is_wall(state, block_pos + UP) or
                          is_wall(state, block_pos + DOWN))
    if blocked_horizontal AND blocked_vertical:
        return true    // stuck in a corner, no target here = dead
    return false

Why it matters: Dead-state detection is the difference between a frustrating puzzle game and a fair one. Without it, the player might spend ten minutes trying to solve a puzzle that became unsolvable on their third move.

6. Level Serialization

Levels are stored as compact text strings using the standard Sokoban format: # = wall, . = target, $ = block, @ = player, * = block on target, + = player on target, space = floor.

level_string = """
  #####
###   #
#.@$  #
### $.#
#.##$ #
# # . ##
#$ *$$.#
#   .  #
########
"""

function parse_level(level_string):
    state = GameState()
    rows = level_string.split('\n')
    for y, row in enumerate(rows):
        for x, char in enumerate(row):
            match char:
                '#': state.grid[y][x] = WALL
                '.': state.target_positions.add({x, y})
                '$': state.block_positions.add({x, y})
                '@': state.player_position = {x, y}
                '*': state.target_positions.add({x, y})
                     state.block_positions.add({x, y})
    return state

Why it matters: Level serialization makes your puzzle game extensible. With a text-based format, anyone can create new levels. The standard Sokoban format has been used for decades, and there are thousands of community-made levels available.

---

Stretch Goals

• Level editor: Let the player place walls, blocks, targets, and the player start position on an empty grid.
• Step counter and par score: Track the number of moves per level and display a par score.
• Animated transitions: Have the player and blocks slide smoothly between grid cells.
• Rules-as-objects mode: Implement a small set of Baba Is You-style rule tiles for bonus levels.

MVP Spec

Element	Scope
Grid	Variable size per level, up to 12x12
Tiles	Wall, floor, target, block, player
Movement	4-directional, one cell per move
Push rules	Push one block at a time, only into empty floor or target, no pulling
Undo	Full undo/redo stack, unlimited depth
Dead-state	Corner deadlock detection with visual warning
Levels	5-8 handcrafted levels with progressive difficulty
Win condition	All blocks on targets
HUD	Move counter, level number, undo/redo/restart buttons

Deliverable

A playable Sokoban game with 5-8 levels of increasing difficulty. The player pushes blocks onto target squares using four-directional movement. The game must include a working undo system, dead-state detection for corner deadlocks with a visual indicator, and levels loaded from a text-based serialization format.

---

Analogies by Background

For Backend Developers

Concept	Analogy
Push Mechanics	Like a message queue where you can only enqueue, never dequeue — once data is pushed through, you cannot pull it back.
Undo System	Like an event-sourced system — every state change is an event on a log, and "undo" means replaying all events except the last one.
State Validation	Like a health check after every deployment — a simple predicate confirms all services are in their expected positions.
Dead-State Detection	Like detecting circular dependencies or deadlocks in a locking system — certain configurations are provably unresolvable.
Level Serialization	Like infrastructure-as-code — the entire state is described in a declarative text format that can be version-controlled and shared.

For Frontend Developers

Concept	Analogy
Push Mechanics	Like DOM element positioning where you can only push elements in flow direction without pulling them back.
Undo System	Like the browser's history API — pushState adds to the stack, back pops it.
State Validation	Like form validation on every input change — a function tests whether all required fields have valid values.
Dead-State Detection	Like detecting impossible form states — a combination of selections that makes submit permanently unreachable.
Level Serialization	Like saving and loading component state as JSON — the entire UI configuration is a serializable string.

For Data / ML Engineers

Concept	Analogy
Push Mechanics	Like a write-once data pipeline — once data flows through a transformation, the original cannot be retrieved from the output.
Undo System	Like checkpointing in model training — each epoch's weights are saved, and "undo" means rolling back to a previous checkpoint.
State Validation	Like a convergence check — after each step, verify whether the loss has reached the target threshold.
Dead-State Detection	Like detecting vanished gradients — certain parameter configurations are provably unable to reach the optimum.
Level Design	Like curating a benchmark dataset — each example tests a specific capability with a measurable difficulty gradient.

---

Discussion Questions

1. The Undo Dilemma: Unlimited undo makes Sokoban less punishing but also reduces the weight of each decision. Where do you draw the line?
2. Designing for One Solution: The best Sokoban levels have exactly one solution. How do you verify this without exhaustive search?
3. The Dead-State UX Problem: When a puzzle becomes unsolvable, should the game tell the player immediately, wait for them to figure it out, or never say anything?
4. Physical Intuition vs. Abstract Rules: Classic Sokoban uses the physical metaphor of pushing crates. Baba Is You uses abstract word-tiles. Does the physical metaphor make the game easier to learn?