Pac-Man

In 1980 Pac-Man marched into arcades and turned a maze full of dots into a cultural icon. The goal is simple: steer Pac-Man through the corridors, eat every dot, and don't get cornered by the ghosts.

Most of the time you play on instinct and reflexes. But hidden underneath is a planning question: from where you stand, is there a route that sweeps up all the remaining dots — ideally without doubling back over ground you've already cleared?

That little question — "does a dot-collecting route even exist?" — is not just arcade trivia. Blow the maze up to any size and it becomes one of the hardest kinds of problem we know how to state in computer science.

Here is a tiny maze. Pac-Man starts on the yellow cell; click an adjacent corridor cell to extend his route. The rule that makes it interesting: he can never revisit a cell he has already walked. Your job is to eat every dot.

<p class="hint">{{hint}}</p>
<div id="grid" class="grid"></div>
<div class="status" id="status">{{click_to_move}}</div>
<div class="btns">
  <button id="undo" type="button" class="ghost">{{btn_undo}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
  <button id="solve" type="button">{{btn_solve}}</button>
</div>
<div class="meter" id="meter"></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; }
.grid { display: grid; grid-template-columns: repeat(5, 50px); gap: 4px; margin: .4rem 0; }
.cell { width: 50px; height: 50px; display: flex; align-items: center; justify-content: center;
        font-size: 24px; border-radius: 8px; user-select: none; position: relative; }
.open { background: #10131f; cursor: pointer; transition: background .1s; }
.open:hover { background: #1c2236; }
.wall { background: #2b6cb0; }
.path { background: #243b6b; }
.pac { background: #ffd400; }
.pac::after { content: "\1F642"; }
.dot::after { content: "\2022"; color: #ffd400; font-size: 30px; line-height: 0; }
.eaten::after { content: ""; }
.order { position: absolute; bottom: 2px; right: 4px; font: 700 10px monospace; color: #9fb2c8; }
.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; }
.meter { font: 600 .85rem ui-monospace, monospace; color: #444; margin-top: .5rem; min-height: 1.2em; }

// Code not found

Notice the asymmetry. Walking a finished route is effortless — follow the numbered steps and tick off each dot. Finding a route that eats them all without crossing itself is the hard part. Press Brute-force search and the computer tries to extend the path one cell at a time, backtracking whenever it gets stuck. At each junction the search branches, and on a bigger maze those branches multiply out of control.

How hard is Pac-Man, really? Not the dodging — the planning.

• Checking a proposed route is trivial: walk it and confirm every dot gets eaten and no cell is repeated.
• Brute force grows a self-avoiding path one cell at a time and backtracks on dead ends. Every fork in the maze is a branch in the search tree, so the work explodes as the maze grows.
• It's NP-hard. In 2013 Giovanni Viglietta, in the paper "Gaming is a hard job, but someone has to do it!", proved that the generalized version of Pac-Man is NP-hard. He did it with gadgets — small maze pieces wired together so that finding a winning route forces the game to solve a Hamiltonian-path-like problem, a classic NP-complete question about visiting every node of a graph exactly once.
• So deciding even is-there-a-clearing-route is at least as hard as the whole NP-complete family — and the status is NP-hard (the playing version, with ghosts and limited time, is harder still).

That is the punchline: the moment a maze is too tangled for quick local reasoning, you are staring at a genuine instance of the same difficulty behind P vs NP. The "perfect" Pac-Man route isn't just hard to play — it can be genuinely hard to find at all.

"Find a route that visits everything I need to visit" is one of the most common shapes a real problem can take, and Pac-Man is its friendly face:

• Delivery and logistics: planning a van's stops is the close cousin called the Traveling Salesman Problem — visit every address, keep the trip short.
• Robot coverage: a vacuum or a lawn mower that must sweep every patch of floor is solving a Pac-Man-style covering tour.
• Circuit and chip routing: wiring that must touch a set of pads while never crossing itself echoes the self-avoiding-path constraint exactly.
• Teaching complexity: because everyone has played it, Pac-Man is one of the clearest on-ramps to what "NP-hard" even means.

Learn why Pac-Man is hard and you've met routing and covering tours — the engine under the Traveling Salesman Problem, Hamiltonian paths and countless real delivery and coverage problems.

Pac-Man hides a beautiful secret: the same maze that ate your quarters can be wired into gadgets, and through them into a Hamiltonian-path-like search. Walking a route stays instant; deciding whether a clearing route even exists is NP-hard — as hard as anything in computer science.

So the next time you can't quite see how to clear a level in one clean sweep, take comfort — you haven't played badly. You've run into P vs NP hiding behind a hungry yellow circle, and there may be no clever shortcut to the perfect route at all.