Introduction

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.

Try It: Push the Box

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">You are the worker (☻). Use the arrows to move. Walking into the box (▦) <b>pushes</b> it — but only if the square behind is free. Get the box onto the target (◎). One push into a corner and it is stuck forever.</p>
<div id="board" class="board"></div>
<div class="status" id="status">Push the box onto the target.</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">Auto-solve</button>
  <button id="reset" type="button" class="ghost">Reset level</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Sokoban: push the box (you can only PUSH, never pull). Checking a final
// position is trivial — box on target? — but deciding whether a level is
// solvable is PSPACE-complete (Culberson, 1997). Every push is irreversible,
//
// Level grid: # wall, ' ' floor, . target, $ box, @ worker
const LEVEL = [
  "#######",
  "#  .  #",
  "#     #",
  "# $@  #",
  "#     #",
  "#######",
];
const H = LEVEL.length, W = LEVEL[0].length;
const wall = [], target = [];
let START_BOX, START_WORKER;
for (let r=0;r<H;r++){ wall[r]=[]; for(let c=0;c<W;c++){
  const ch = LEVEL[r][c];
  wall[r][c] = (ch === '#');
  if (ch === '.') target.push([r,c]);
  if (ch === '


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.

) START_BOX = [r,c];
  if (ch === '@') START_WORKER = [r,c];
}}
const T = target[0]; // single target
let box, worker, won=false, dead=false;
const key = (r,c)=> r+','+c;
const isWall = (r,c)=> r<0||r>=H||c<0||c>=W||wall[r][c];
const isTarget = (r,c)=> r===T[0] && c===T[1];

// A box on a non-target square that has walls on two perpendicular sides (a corner) can never be moved again -> deadlock.
function isDeadlock(b){
  if (isTarget(b[0],b[1])) return false;
  const up=isWall(b[0]-1,b[1]), dn=isWall(b[0]+1,b[1]);
  const lf=isWall(b[0],b[1]-1), rt=isWall(b[0],b[1]+1);
  return (up||dn) && (lf||rt);
}

const DIRS = { up:[-1,0], down:[1,0], left:[0,-1], right:[0,1] };
// Apply a move to a state; returns new {worker,box} or null if illegal. Pure.
function step(state, d){
  const [dr,dc] = DIRS[d];
  const nr = state.worker[0]+dr, nc = state.worker[1]+dc;
  if (isWall(nr,nc)) return null;
  if (nr===state.box[0] && nc===state.box[1]){
    const br = nr+dr, bc = nc+dc;
    if (isWall(br,bc)) return null;            // wall behind the box -> can't push
    return { worker:[nr,nc], box:[br,bc] };
  }
  return { worker:[nr,nc], box:[state.box[0],state.box[1]] };
}

function reset(){
  box=[...START_BOX]; worker=[...START_WORKER]; won=false; dead=false;
  setStatus('Push the box onto the target.',''); render(); syncButtons();
}
function move(d){
  if (won||dead) return;
  const ns = step({worker,box}, d);
  if (!ns) return;
  worker=ns.worker; box=ns.box;
  if (isTarget(box[0],box[1])){ won=true; setStatus('✓ Solved! Box is on the target.','ok'); }
  else if (isDeadlock(box)){ dead=true; setStatus('✗ Deadlock! The box is wedged in a corner — unsolvable now. Reset.','bad'); }
  else setStatus('Keep pushing — only forward, never back.','');
  render(); syncButtons();
}
function syncButtons(){
  const off = won||dead;
  ['up','down','left','right'].forEach(id=>{ document.getElementById(id).disabled = off; });
}

// BFS over (worker,box) states from the start: the exploding state space.
function solve(){
  const start={worker:[...START_BOX].length?[...START_WORKER]:null, box:[...START_BOX]};
  const s0={worker:[...START_WORKER], box:[...START_BOX]};
  const skey = st => key(st.worker[0],st.worker[1])+'|'+key(st.box[0],st.box[1]);
  const seen=new Set([skey(s0)]); const q=[s0]; let explored=0; let goal=null;
  while(q.length){
    const cur=q.shift(); explored++;
    if (isTarget(cur.box[0],cur.box[1])){ goal=cur; break; }
    for (const d in DIRS){
      const ns=step(cur,d); if(!ns) continue;
      if (isDeadlock(ns.box)) continue;        // prune permanently-stuck states
      const k=skey(ns); if(seen.has(k)) continue;
      seen.add(k); q.push(ns);
    }
  }
  if (goal){ box=[...goal.box]; worker=[...goal.worker]; won=true; dead=false;
    setStatus(fmt('Auto-solved. BFS explored %explored% states of the (worker,box) space.', { explored: explored }),'ok');
    console.log('Solved; states explored =', explored); }
  else { setStatus('No solution exists from here (the level is deadlocked).','bad'); }
  render(); syncButtons();
}

function setStatus(t,cls){ const s=document.getElementById('status'); s.textContent=t; s.className='status '+cls; }
function render(){
  const b=document.getElementById('board'); b.style.gridTemplateColumns='repeat('+W+',42px)'; b.innerHTML='';
  for(let r=0;r<H;r++)for(let c=0;c<W;c++){
    const d=document.createElement('div');
    if (wall[r][c]){ d.className='cell wall'; }
    else if (worker[0]===r&&worker[1]===c){ d.className='cell '+(isTarget(r,c)?'target':'floor')+' worker'; d.textContent='☻'; }
    else if (box[0]===r&&box[1]===c){ d.className='cell box'+(isTarget(r,c)?' on':''); d.textContent='▦'; }
    else if (isTarget(r,c)){ d.className='cell target'; d.textContent='◎'; }
    else { d.className='cell floor'; }
    b.appendChild(d);
  }
}
document.getElementById('up').addEventListener('click',()=>move('up'));
document.getElementById('down').addEventListener('click',()=>move('down'));
document.getElementById('left').addEventListener('click',()=>move('left'));
document.getElementById('right').addEventListener('click',()=>move('right'));
document.getElementById('solve').addEventListener('click',solve);
document.getElementById('reset').addEventListener('click',reset);
reset();
Result
Console

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.

The Real Complexity

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.

Where It Matters

"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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/sokoban/Content licensed under CC BY-NC 4.0.