I Built a Procedural Sokoban Generator in One Day. Here's Why It Kept Making Unsolvable Levels.

#claudecode #javascript #algorithms #ai

Sokoban level generation is a solved problem. Taylor & Parberry published the backward simulation algorithm in 2011. The idea is elegant: start from a solved configuration (all boxes on goals), apply legal reverse pushes, and you get a playable puzzle. You can't generate an invalid level because you start from a valid one.

Except you can. And we did. Repeatedly.

Here's what we found building Sokobot — a procedural Sokoban generator that runs in a single 522-line HTML file.

How Backward Generation Works

A standard Sokoban move pushes a box: player steps into the box's position, box moves one cell ahead. The reverse is a pull: box moves toward the player, player moves away. If you apply N random legal pulls starting from a solved state, you get a scrambled-but-solvable puzzle.

// Simplified backward step
function backwardStep(grid, playerPos, boxes, W, H, rng) {
  const dirs = [[0,-1],[0,1],[-1,0],[1,0]];
  shuffle(dirs, rng);

  for (const [dx, dy] of dirs) {
    for (const box of boxes) {
      // New box position: pull in direction
      const nbx = box.x + dx, nby = box.y + dy;
      // Player must be behind the box for this pull
      const ppx = box.x - dx, ppy = box.y - dy;

      if (isFloor(grid, nbx, nby) && isFloor(grid, ppx, ppy)
          && !hasBox(boxes, nbx, nby)) {
        // Apply the reverse move
        box.x = nbx; box.y = nby;
        playerPos.x = ppx; playerPos.y = ppy;
        // Mark cells as reachable floor
        grid[nby][nbx] = FLOOR;
        grid[ppy][ppx] = FLOOR;
        return;
      }
    }
  }
}

The math holds: every state you can reach by applying reverse pushes is solvable (just replay the moves forward in reverse order).

So why did Level 1 have a box stuck in the corner?

The Deadlock Case Backward Generation Misses

The algorithm guarantees the generated path is solvable. But it doesn't check whether the resulting grid allows the player to actually execute that path.

Specifically: if a box ends up in a position where it can't be pushed in any direction, the level is a deadlock — even if the backward simulation produced it.

Case 1: Corner deadlock

######
#X   #
#    #
######

The box at (col=1, row=1) has walls on its left and above. You can't push it right (player needs to be in the wall). You can't push it down (same problem). The box is immovable. Level unsolvable.

Case 2: Edge deadlock

#####
X   #
#   #
#####

The box is on the left boundary column. The only way to push it is right — but if there's no goal in that column, it can never reach a goal. Even if the box can be pushed, it can never satisfy the win condition.

Both cases can be generated by the backward algorithm because the pulls that created those positions were technically legal. The algorithm placed the box there via a valid reverse move. It just didn't check whether that placement would be a dead end.

Fix Part 1: In-Generation Deadlock Prevention

The simplest fix: during backward simulation, before accepting a new box position, check whether it's obviously deadlocked.

// After choosing new box position (nbx, nby):
const onGoal = goals.some(g => g.x === nbx && g.y === nby);
if (!onGoal) {
  const lW = grid[nby][nbx-1] === WALL;
  const rW = grid[nby][nbx+1] === WALL;
  const uW = grid[nby-1][nbx] === WALL;
  const dW = grid[nby+1][nbx] === WALL;

  // Corner deadlock: adjacent to walls on two perpendicular sides
  if ((lW || rW) && (uW || dW)) continue;

  // Edge deadlock: on boundary column with no goal in that column
  if ((lW || rW) && !goals.some(g => g.x === nbx)) continue;

  // Edge deadlock: on boundary row with no goal in that row
  if ((uW || dW) && !goals.some(g => g.y === nby)) continue;
}

Key detail: we only apply these checks when the box is not on a goal. A box on a goal is already in its final position — deadlock checks don't apply.

This eliminated the obvious cases. But Level 2 was still occasionally broken.

The Subtler Bug: BOXON as Obstacle

Multi-box levels have an interaction we initially missed. When some boxes are already placed on goals (BOXON state), they aren't just "solved" — they're obstacles for other boxes that need to reach the remaining goals.

Our first BFS validation had a bug:

// WRONG: only tracking BOX positions as obstacles
const others = boxes.filter(o => o !== b);

The fix: treat BOXON cells (boxes already on goals) as immovable obstacles when validating reachability for other boxes.

function isLikelySolvable(grid, W, H) {
  const boxes = [], goals = [], allBoxes = [];

  for (let y = 0; y < H; y++)
    for (let x = 0; x < W; x++) {
      const c = grid[y][x];
      if (c === BOX)   { boxes.push({x,y}); allBoxes.push({x,y}); }
      if (c === BOXON) allBoxes.push({x,y}); // obstacle for other boxes
      if (c === GOAL || c === BOXON || c === PLYRON) goals.push({x,y});
    }

  for (const b of boxes) {
    // All boxes EXCEPT the one we're checking are obstacles
    const obstacles = allBoxes.filter(o => !(o.x===b.x && o.y===b.y));
    const visited = new Set([`${b.x},${b.y}`]);
    const queue = [{x: b.x, y: b.y}];
    let canReachGoal = false;

    while (queue.length && !canReachGoal) {
      const {x, y} = queue.shift();

      // Can this position be a goal that isn't blocked by another box?
      if (goals.some(g=>g.x===x&&g.y===y)
          && !obstacles.some(o=>o.x===x&&o.y===y)) {
        canReachGoal = true; break;
      }

      // BFS: try pushing box in each direction
      for (const [dx, dy] of [[1,0],[-1,0],[0,1],[0,-1]]) {
        const nx = x+dx, ny = y+dy; // new box pos
        const fx = x-dx, fy = y-dy; // player must be here

        if (nx<1||nx>=W-1||ny<1||ny>=H-1) continue;
        if (grid[ny][nx] === WALL) continue;
        if (obstacles.some(o=>o.x===nx&&o.y===ny)) continue;
        if (fx<1||fx>=W-1||fy<1||fy>=H-1) continue;
        if (grid[fy][fx] === WALL) continue;

        const k = `${nx},${ny}`;
        if (!visited.has(k)) { visited.add(k); queue.push({x:nx, y:ny}); }
      }
    }

    if (!canReachGoal) return false;
  }
  return true;
}

Note the BFS checks push-reachability, not just flood-fill. For a box to move from (x,y) to (x+dx,y+dy), the player needs to be able to reach (x-dx,y-dy). We're not modeling full player pathfinding here — we're assuming the player can always reach the push position if the cell is floor. That's an approximation, but it's good enough for our grid sizes.

Fix Part 2: Retry with Different Seeds

If the BFS check fails, regenerate with a different seed. We bumped the retry limit from 5 to 15 attempts:

for (let attempt = 0; attempt < 15; attempt++) {
  const seed = levelNum * 12345 + 67890 + attempt * 999;
  const candidate = generateLevel(seed, w, h, boxCount, iters);
  const unplaced = countUnplacedBoxes(candidate);
  if (unplaced > 0 && isLikelySolvable(candidate, w, h)) {
    generated = candidate;
    break;
  }
}

In practice, the combination of in-generation checks + BFS validation means we rarely need more than 2-3 attempts. The 15-attempt limit is a safety net.

What "Solvable" Actually Means Here

The BFS check is an approximation. It verifies that each unplaced box can physically reach a goal (ignoring player pathfinding). It doesn't verify that the player can solve the puzzle in the correct sequence.

True Sokoban solvability is PSPACE-complete. A full solver would be correct but too slow for real-time level generation in the browser.

In practice, the approximation works well. The two-layer defense (deadlock prevention + push-reachability BFS) eliminated all deadlocked levels we observed in playtesting. The levels it generates range from trivially easy (Level 1) to genuinely tricky (Level 10+).

If you hit a level that seems impossible, there's a "New Level" button. The seed system means you can skip and come back.

The Full Game

Sokobot is live at https://yurukusa.github.io/sokobot/ — 522 lines of vanilla HTML+JS, no framework, no build step. Open the source and the generator is right there.

The whole thing was built by a Claude Code agent team in a single session as an entry for the AI Browser Game Jam (theme: "Ghost in the Machine"). The algorithm generating your levels is, quite literally, the ghost in the machine.

Part of the AI Browser Game Jam series: