Sokoban

Sokoban — Japanese for "warehouse keeper" — is the gentlest-looking puzzle imaginable. You are a little worker in a warehouse. There are boxes on the floor and matching target spots. Your only job: push every box onto a target. You can only push, never pull, and only one box at a time.

It sounds trivial, and the first levels are. But there is a trap built into the rules. Because you can only push, the moment you shove a box into a corner it is stuck forever — and one stuck box can make the entire level impossible, even if everything else looks fine.

So Sokoban is not really about moving boxes. It is about planning a whole sequence of irreversible moves so that you never paint yourself into a corner. That tiny twist turns out to push it past the famous NP problems into something we believe is even harder.

Here is a tiny Sokoban level. Move the worker with the arrow buttons. When you walk into the box, you push it — if there is a wall behind it, nothing moves. Get the box (▦) onto the target (◎).

<p class="hint">{{hint}}</p>
<div id="board" class="board"></div>
<div class="status" id="status">{{status_initial}}</div>
<div class="pad">
  <button id="up" type="button">▲</button>
  <div class="row">
    <button id="left" type="button">◀</button>
    <button id="down" type="button">▼</button>
    <button id="right" type="button">▶</button>
  </div>
</div>
<div class="btns">
  <button id="solve" type="button">{{btn_solve}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.board { display: grid; gap: 3px; margin: .4rem 0; width: max-content; }
.cell { width: 42px; height: 42px; display: flex; align-items: center; justify-content: center;
        font: 700 22px ui-monospace, monospace; border-radius: 6px; user-select: none; }
.floor { background: #eef2f6; color: #1d3557; }
.wall  { background: #43505e; }
.target { background: #d8ecdd; color: #0a7d33; }
.box   { background: #c98a3a; color: #fff; }
.box.on { background: #0a7d33; }
.worker { color: #1d3557; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.pad { display: flex; flex-direction: column; align-items: center; gap: 4px; margin: .3rem 0 .6rem; }
.pad .row { display: flex; gap: 4px; }
.pad button { width: 46px; height: 40px; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 15px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .45; cursor: not-allowed; }

// Code not found

Notice two things. First, checking a finished position is instant: is the box on the target? Done. Second, one careless push and the box lands in a corner where it can never come out — the panel will tell you the level is now a deadlock, unsolvable no matter what you do next. Press Auto-solve and the computer explores the space of (worker, box) positions; even on this matchbox level that space has hundreds of states, and it doubles with every box you add.

How hard is Sokoban, really? Not pushing one box — deciding whether a whole level can be solved.

• Checking a claimed solution is easy if you replay it move by move: just confirm each push is legal and that every box ends on a target.
• The catch: a solution can be astronomically long. Unlike a Sudoku answer you can write down in one line, a Sokoban plan may need an exponential number of moves, so you can't just hand someone a short certificate. That is exactly what separates it from NP.
• It's PSPACE-complete. In 1997, Joseph Culberson proved that deciding solvability of a Sokoban level is PSPACE-complete — the level can simulate the read/write tape and transitions of any computation that runs in polynomial memory. Boxes become tape symbols; pushing them encodes the machine's steps.
• What that means: PSPACE contains all of NP (and almost certainly more). So Sokoban is at least as hard as every NP-complete problem like SAT — and widely believed to be strictly harder.

The everyday reason is exactly the trap from the demo: every push is irreversible, so the puzzle is really about reasoning over long chains of one-way decisions. That is the signature of PSPACE-hard planning, and it's why no clever shortcut for Sokoban is expected — it would settle questions far bigger than this one game, much like P vs NP.

"Plan a long sequence of moves and never reach a dead end" is one of the deepest shapes a real problem can take, and Sokoban is its friendly face:

• Robot motion planning: a robot pushing or carrying objects through clutter faces the exact same corners-and-dead-ends reasoning.
• Automated planning (AI): Sokoban is a classic benchmark for planners precisely because short greedy moves fail and deep lookahead is required.
• Warehouse and logistics: moving pallets where space is tight is literally box-pushing under irreversible constraints.
• Teaching PSPACE: because anyone can play it, Sokoban is one of the clearest ways to feel why "needs lots of memory / very long plans" is its own kind of hard, above NP.

Understand why Sokoban is hard and you've met the world of hard planning — the same difficulty that lurks behind SAT solvers pushed to their limits and many scheduling problems.

Sokoban hides a beautiful secret: a warehouse worker who can only push crates can be wired into a full computer that uses polynomial memory. Checking a replayed solution stays simple; deciding whether a level is solvable at all is PSPACE-complete — provably at least as hard as every problem in NP.

So the next time a single box slides into a corner and your level dies, take comfort — you didn't just play badly. You ran straight into the wall of PSPACE, where every irreversible move counts and there may be no shortcut at all around the long, careful plan.