Introduction

In 1991, Lemmings from DMA Design became one of the most loved puzzle games ever made. Tiny green-haired creatures march mindlessly off a trapdoor and walk straight ahead until something stops them. Your job is to get enough of them to the exit before time runs out — and they will happily stroll into lava, off cliffs, or into traps unless you intervene.

Your only tools are a fixed budget of skills you assign to individual lemmings: a digger tunnels down, a builder lays a staircase of bricks, a basher tunnels sideways, a blocker turns into a wall that reverses everyone who hits it, a floater survives long falls, and a few more. Each skill is in limited supply.

It feels like a gentle game of timing and intuition. But hidden inside is a precise question — can these skills, spent in some order, save the quota of lemmings at all? — and that question turns out to be as hard as the most stubborn problems in all of computer science.

Route the Lemming

Here is a tiny level. The lemming starts on the left and walks right, falling off ledges and dying in the pit unless you intervene. You have a small budget of skills — a builder (bridges a gap), a digger (tunnels straight down), and a blocker (turns a lemming around). Assign skills to the squares, then press Run to watch the lemming march.

<p class="hint">The lemming starts at the left and walks right. The middle is a <b>pit</b> — it will fall in and be lost unless you intervene. Click a brown ground tile to cycle a skill: <b>B</b>uilder (bridges the pit ahead), <b>D</b>igger (drops down), <b>K</b> blocker (turns it around). Use your budget to reach the green <b>exit</b>.</p>
<div id="level" class="level"></div>
<div class="budget" id="budget"></div>
<div class="status" id="status">Assign skills, then Run.</div>
<div class="btns">
  <button id="run" type="button">Run</button>
  <button id="solve" type="button">Auto-solve</button>
  <button id="reset" type="button" class="ghost">Clear</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; }
.level { display: grid; grid-template-columns: repeat(7, 44px); grid-auto-rows: 44px;
         gap: 3px; margin: .4rem 0; }
.tile { display: flex; align-items: center; justify-content: center;
        font: 700 15px ui-monospace, monospace; border-radius: 6px; user-select: none; }
.sky { background: #eef4fb; border: 1px solid #dde7f1; }
.ground { background: #b9926b; border: 1px solid #9c764f; color: #3a2a18; cursor: pointer; }
.ground:hover { filter: brightness(1.05); }
.ground.skill { background: #f4c542; border-color: #d9a91f; color: #4a3500; }
.bridge { background: #d9b98f; border: 1px dashed #9c764f; }
.exit { background: #2bbf6a; border: 1px solid #1f9e55; color: #fff; font-size: 11px; }
.lem { background: #1d3557; border: 1px solid #16263f; color: #fff; }
.lem::after { content: "L"; }
.budget { font-size: .9rem; color: #333; margin: .3rem 0; }
.budget b { color: #1d3557; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px 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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// A tiny Lemmings level. The lemming walks right; we simulate it deterministically.
// The player assigns a limited budget of skills to GROUND tiles. CHECKING a plan is
// a quick simulation; FINDING one (Auto-solve) is brute force over assignments —
// and in the full game, deciding winnability is NP-hard (Cormode, 2004).
const W = 7, H = 4;
// GROUND[r][c] === 1 means solid floor. Cols 3-4 on the bottom rows are a pit.
const GROUND = [
  [0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0],
  [1,1,1,0,0,1,1],
  [1,1,1,0,0,1,1],
];
const START = { c: 0, row: 2 };
const EXIT  = { c: 6, row: 2 };
const BUDGET = { B: 1, D: 0, K: 1 };   // 1 builder solves it; 1 blocker is a decoy
const SKILLS = ['', 'B', 'D', 'K'];

let assign = {};                       // "row,col" -> skill letter
const key = (r, c) => r + ',' + c;
const isGround = (r, c) => r >= 0 && r < H && c >= 0 && c < W && GROUND[r][c] === 1;

// Deterministic simulation. The lemming stands at (row,c) on the floor at (row+1,c).
// Returns true iff it reaches the exit. `trace` (optional) records each frame, and
// `bridgeOut` (optional Set) collects bridge tiles for rendering.
function simulate(a, trace, bridgeOut) {
  let c = START.c, row = START.row, dir = 1;
  const bridge = new Set();
  const standable = (r, cc) => isGround(r + 1, cc) || bridge.has(key(r, cc));
  for (let step = 0; step < 200; step++) {
    if (trace) trace.push({ row, c, bridge: new Set(bridge) });
    if (row === EXIT.row && c === EXIT.c) { if (bridgeOut) bridge.forEach(b => bridgeOut.add(b)); return true; }
    const sk = a[key(row, c)];
    if (sk === 'K') { dir = -dir; continue; }
    if (sk === 'B') {
      let bc = c;                       // lay bridge tiles across the pit at this row
      for (let n = 0; n < W; n++) {
        const nb = bc + dir;
        if (nb < 0 || nb >= W || isGround(row + 1, nb)) break;
        bridge.add(key(row, nb)); bc = nb;
      }
      const nc = c + dir;
      if (nc >= 0 && nc < W && standable(row, nc)) { c = nc; continue; }
    }
    if (sk === 'D') { if (row + 1 < H) { row++; continue; } return false; }
    const nc = c + dir;               // default walk
    if (nc < 0 || nc >= W) return false;
    if (standable(row, nc)) { c = nc; continue; }
    let fr = row;                     // nothing ahead -> fall straight down
    while (fr + 1 < H && !standable(fr, c)) fr++;
    if (fr === row || !standable(fr, c)) return false;
    row = fr;
  }
  return false;
}
function overBudget(a) {
  const u = { B:0, D:0, K:0 }; for (const k in a) u[a[k]]++;
  return u.B > BUDGET.B || u.D > BUDGET.D || u.K > BUDGET.K;
}

function render(lem) {
  const el = document.getElementById('level'); el.innerHTML = '';
  const br = lem && lem.bridge ? lem.bridge : new Set();
  for (let r = 0; r < H; r++) for (let c = 0; c < W; c++) {
    const d = document.createElement('div');
    const onExit = (r === EXIT.row && c === EXIT.c);
    if (lem && lem.row === r && lem.c === c) { d.className = 'tile lem'; }
    else if (onExit) { d.className = 'tile exit'; d.textContent = 'EXIT'; }
    else if (isGround(r, c)) {
      const sk = assign[key(r, c)] || '';
      d.className = 'tile ground' + (sk ? ' skill' : '');
      d.textContent = sk;
      d.addEventListener('click', () => {
        const cur = SKILLS.indexOf(assign[key(r, c)] || '');
        const nx = SKILLS[(cur + 1) % SKILLS.length];
        if (nx) assign[key(r, c)] = nx; else delete assign[key(r, c)];
        refresh(); setStatus('Assign skills, then Run.', '');
      });
    } else if (br.has(key(r, c))) { d.className = 'tile bridge'; }
    else { d.className = 'tile sky'; }
    el.appendChild(d);
  }
}
function used() { const u = { B:0, D:0, K:0 }; for (const k in assign) u[assign[k]]++; return u; }
function refresh() {
  render(null);
  const u = used();
  document.getElementById('budget').innerHTML =
    fmt('Budget — Builder <b>%v%</b>/%B%, Digger <b>%v2%</b>/%D%, Blocker <b>%v3%</b>/%K%', { v: BUDGET.B - u.B, B: BUDGET.B, v2: BUDGET.D - u.D, D: BUDGET.D, v3: BUDGET.K - u.K, K: BUDGET.K });
}
function setStatus(t, cls) { const s = document.getElementById('status'); s.textContent = t; s.className = 'status ' + cls; }

function run() {
  if (overBudget(assign)) { setStatus('Over budget — remove a skill.', 'bad'); return; }
  const trace = [];
  const win = simulate(assign, trace, null);
  let i = 0;
  const timer = setInterval(() => {
    if (i >= trace.length) {
      clearInterval(timer); render(null);
      setStatus(win ? 'Saved! The lemming reached the exit.' : 'Lost — the lemming did not make it.', win ? 'ok' : 'bad');
      return;
    }
    render(trace[i]); i++;
  }, 280);
}
function solve() {
  const tiles = [];
  for (let r = 0; r < H; r++) for (let c = 0; c < W; c++) if (isGround(r, c)) tiles.push(key(r, c));
  let best = null, tries = 0;
  function rec(i, a) {
    if (best) return;
    if (overBudget(a)) return;
    if (i === tiles.length) { tries++; if (simulate(a, null, null)) best = { ...a }; return; }
    for (const o of SKILLS) { const b = { ...a }; if (o) b[tiles[i]] = o; rec(i + 1, b); if (best) return; }
  }
  rec(0, {});
  if (best) {
    assign = best; refresh();
    setStatus(fmt('Auto-solve found a winning plan after searching %tries% assignments.', { tries: tries }), 'ok');
    console.log('Winning assignment:', JSON.stringify(best), '| simulations run:', tries);
  } else setStatus('No assignment within budget wins this level.', 'bad');
}
document.getElementById('run').addEventListener('click', run);
document.getElementById('solve').addEventListener('click', solve);
document.getElementById('reset').addEventListener('click', () => { assign = {}; refresh(); setStatus('Assign skills, then Run.', ''); });
refresh();
Result
Console

Notice the asymmetry. Checking a plan is effortless: just simulate the lemming step by step and see whether it reaches the exit. Finding a plan that works is the hard part — press Auto-solve and the computer simply tries every way to assign your skills to the squares. A handful of squares and three skills is already dozens of combinations; add more squares, more skills and more lemmings and the count explodes. That gap is the whole story. See also P vs NP.

The Real Complexity

How hard is Lemmings, really? Not the playing — the deciding whether a level is even winnable.

  • Checking a proposed solution is easy: run the deterministic simulation with your skill assignments and watch whether the quota reaches the exit. This is a quick, polynomial-time scan.
  • Brute force tries every way to assign each limited skill to a lemming at each moment — an exponential blow-up the instant the level grows beyond a toy.
  • It's NP-hard. In 2004 Graham Cormode proved that the decision problem "can at least k lemmings be saved with these skills?" is NP-hard, by building a level whose geometry encodes any 3-SAT formula: corridors act as variables, and only a satisfying truth assignment lets enough lemmings through.
  • Some variants are PSPACE-hard. Giovanni Viglietta later showed that with richer mechanics (where the game can store and recall state), Lemmings-style games become PSPACE-hard — harder still, on par with deciding who wins a generalized board game.

That is the punchline: the moment a level can't be cracked by quick local reasoning, you are staring at a genuine instance of the same wall behind P vs NP. The levels that leave you trying assignment after assignment aren't badly designed — they are intractability turned into a game.

Where It Matters

"Spend a limited set of actions, in the right order, so that agents reach their goals" is one of the most common shapes a real problem can take, and Lemmings is its playful face:

  • Robot motion planning: guiding agents through an environment while respecting walls and limited maneuvers is exactly the lemming's problem at industrial scale.
  • AI planning: classical planners search for a sequence of actions that transforms a start state into a goal — the same combinatorial explosion Lemmings makes visible.
  • Scheduling and resource allocation: assigning scarce, single-use resources (machines, crews, time slots) so every job finishes is "save enough lemmings" in a suit.
  • Teaching complexity: because the mechanics are so concrete, Lemmings is a vivid on-ramp to why proving hardness via reductions even works.

Learn why Lemmings is hard and you've met sequential planning under constraints — the engine under SAT reductions and countless real scheduling problems.

Conclusion

Lemmings hides a beautiful secret: the same skills that let you guide a crowd to safety can be wired into the logic of a 3-SAT formula, making the question "can enough be saved?" NP-hard — and PSPACE-hard in its richer forms. Checking a solution stays instant; deciding whether one exists is as hard as anything in computer science.

So the next time a level defeats you and you cycle through assignment after assignment, take comfort — you haven't played badly. You've simply run into P vs NP hiding behind a row of cheerful green-haired creatures, and there may be no clever shortcut to the answer at all.

Share this article

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

Comments

Loading comments...

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