Lemmings

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.

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">{{hint}}</p>
<div id="level" class="level"></div>
<div class="budget" id="budget"></div>
<div class="status" id="status">{{status_initial}}</div>
<div class="btns">
  <button id="run" type="button">{{btn_run}}</button>
  <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; }
.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; }

// Code not found

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.

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.

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

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.