Introduction

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.

Try It: Clear the Maze

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">Pac-Man starts at the yellow cell. Click adjacent cells to extend a route and eat every dot. You can't step on a wall or revisit a cell. <b>Walking</b> one route is easy — <b>finding</b> one that eats all dots is the hard part.</p>
<div id="grid" class="grid"></div>
<div class="status" id="status">Click a neighbor of Pac-Man to move.</div>
<div class="btns">
  <button id="undo" type="button" class="ghost">Undo</button>
  <button id="reset" type="button" class="ghost">Reset route</button>
  <button id="solve" type="button">Brute-force search</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Generalized Pac-Man is NP-hard (Viglietta, 2013, "Gaming is a hard job, but someone has to do it!").
// Eating every dot while never repeating a cell is a Hamiltonian-path-style problem: walking a given route is trivial to check, but finding one in general forces a search whose tree branches at every step.
const R = 5, C = 5;
// 0 = open floor, 1 = wall, 2 = dot to eat. Pac-Man starts at START.
const MAZE = [
  [2,0,2,0,2],
  [0,1,0,1,0],
  [2,0,2,0,2],
  [0,1,0,1,0],
  [2,0,2,0,2],
];
const START = [4,0];
const key = (r,c) => r + ',' + c;
const isWall = (r,c) => MAZE[r][c] === 1;
const dots = [];
for (let r=0;r<R;r++) for (let c=0;c<C;c++) if (MAZE[r][c]===2) dots.push(key(r,c));
const DOT_TOTAL = dots.length;

let route = [START.slice()]; // list of [r,c] cells visited in order

function neighbors(r,c){ const o=[]; const d=[[-1,0],[1,0],[0,-1],[0,1]];
  for(const [dr,dc] of d){ const nr=r+dr, nc=c+dc;
    if(nr>=0&&nr<R&&nc>=0&&nc<C&&!isWall(nr,nc)) o.push([nr,nc]); } return o; }
const inRoute = (r,c) => route.some(([a,b])=>a===r&&b===c);
function dotsEaten(path){ const s=new Set(path.map(([r,c])=>key(r,c)));
  return dots.filter(k=>s.has(k)).length; }

function render(){
  const g=document.getElementById('grid'); g.innerHTML='';
  const head=route[route.length-1];
  for(let r=0;r<R;r++)for(let c=0;c<C;c++){
    const el=document.createElement('div'); const k=key(r,c);
    const onRoute=inRoute(r,c), isHead=(r===head[0]&&c===head[1]);
    if(isWall(r,c)){ el.className='cell wall'; }
    else if(isHead){ el.className='cell pac'; }
    else if(onRoute){ el.className='cell path'+(MAZE[r][c]===2?' dot eaten':'');
      const o=document.createElement('span'); o.className='order';
      o.textContent=route.findIndex(([a,b])=>a===r&&b===c); el.appendChild(o); }
    else { el.className='cell open'+(MAZE[r][c]===2?' dot':'');
      el.addEventListener('click',()=>tryMove(r,c)); }
    g.appendChild(el);
  }
  const eaten=dotsEaten(route);
  document.getElementById('meter').textContent =
    fmt('Dots eaten: %eaten% / %DOT_TOTAL%   ·   Route length: %length%', { eaten: eaten, DOT_TOTAL: DOT_TOTAL, length: route.length });
}
function setStatus(t,cls){ const s=document.getElementById('status'); s.textContent=t; s.className='status '+(cls||''); }

function tryMove(r,c){
  const [hr,hc]=route[route.length-1];
  const adj=Math.abs(hr-r)+Math.abs(hc-c)===1;
  if(!adj){ setStatus('You can only move to an adjacent (non-diagonal) cell.','bad'); return; }
  if(inRoute(r,c)){ setStatus('Pac-Man cannot revisit a cell on his route.','bad'); return; }
  route.push([r,c]); render();
  if(dotsEaten(route)===DOT_TOTAL) setStatus(fmt('All dots eaten in %v% moves — valid route!', { v: route.length-1 }),'ok');
  else setStatus('Keep going — eat every dot without crossing your own path.','');
}

// Exhaustive self-avoiding search from START that must visit all dots.
// Returns {found, nodes}: nodes counts how many partial routes were explored.
function bruteForce(){
  let nodes=0, best=null;
  function dfs(r,c,visited,path){
    nodes++;
    if(dotsEaten(path)===DOT_TOTAL){ best=path.slice(); return true; }
    for(const [nr,nc] of neighbors(r,c)){
      const k=key(nr,nc);
      if(visited.has(k)) continue;
      visited.add(k); path.push([nr,nc]);
      if(dfs(nr,nc,visited,path)) return true;
      visited.delete(k); path.pop();
    }
    return false;
  }
  const v=new Set([key(START[0],START[1])]);
  const found=dfs(START[0],START[1],v,[START.slice()]);
  return {found, nodes, best};
}

function solve(){
  const {found,nodes,best}=bruteForce();
  if(found){ route=best; render();
    setStatus(fmt('Search found a full route eating all %DOT_TOTAL% dots.', { DOT_TOTAL: DOT_TOTAL }),'ok');
    document.getElementById('meter').textContent =
      fmt('Brute force explored %nodes% partial routes before finding one.', { nodes: nodes });
    console.log('Route:', best.map(([r,c])=>key(r,c)).join(' -> '), '| nodes', nodes);
  } else {
    setStatus('No self-avoiding route eats every dot.','bad');
    document.getElementById('meter').textContent=fmt('Brute force explored %nodes% partial routes — none worked.', { nodes: nodes });
  }
}

document.getElementById('undo').addEventListener('click',()=>{
  if(route.length>1){ route.pop(); render(); setStatus('Move undone.',''); } });
document.getElementById('reset').addEventListener('click',()=>{
  route=[START.slice()]; render(); setStatus('Click a neighbor of Pac-Man to move.',''); });
document.getElementById('solve').addEventListener('click',solve);
render();
Result
Console

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.

The Real Complexity

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.

Where It Matters

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

Conclusion

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.

Share this article

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

Comments

Loading comments...

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