Snake

On Nokia phones and in every browser since, Snake has been the same tiny ritual: a line grows one square each time it eats, and the only way to lose is to crash into a wall or into yourself. Easy at first — but the longer you get, the less room there is to move.

The dream ending is a perfect game: keep eating until the snake's body fills every single square. To do that, the snake must trace a route that passes through each cell of the grid exactly once. That route has a name in mathematics — a Hamiltonian path — and it is far less innocent than it looks.

That gap between "just steer toward the food" and "thread a path through every cell without trapping yourself" is not a quirk of the game. It is the same line that separates the easy problems from the hardest ones in all of computer science.

Here is a small 6×6 board. Steer the snake with the arrows toward the apple — but watch how quickly your own body becomes the obstacle.

<p class="hint">{{hint}}</p>
<div id="board" class="board"></div>
<div class="status" id="status">{{length_label}}: 1 / 36</div>
<div class="pad">
  <button id="up" type="button" class="dir">▲</button>
  <div class="row">
    <button id="left" type="button" class="dir">◀</button>
    <button id="down" type="button" class="dir">▼</button>
    <button id="right" type="button" class="dir">▶</button>
  </div>
</div>
<div class="btns">
  <button id="auto" type="button">{{btn_auto}}</button>
  <button id="cycle" type="button" class="ghost">{{btn_cycle}}</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; }
.board { display: grid; grid-template-columns: repeat(6, 38px); gap: 2px;
         background: #cdd9e3; padding: 2px; border-radius: 8px; width: max-content; }
.cell { width: 38px; height: 38px; position: relative; background: #eef3f7;
        border-radius: 4px; display: flex; align-items: center; justify-content: center; }
.cell.path { background: #f3e9d2; }
.cell.snake { background: #1d3557; }
.cell.head { background: #2a4d7a; }
.cell.food::after { content: "🍎"; font-size: 20px; }
.cell .num { position: absolute; font: 700 10px ui-monospace, monospace; color: #9aa7b3; }
.status { font-size: 1rem; font-weight: 600; margin: .6rem 0; min-height: 1.4em; color: #1d3557; }
.status.win { color: #0a7d33; }
.status.dead { color: #c92f3c; }
.pad { display: flex; flex-direction: column; align-items: center; gap: 4px; margin: .3rem 0 .6rem; }
.pad .row { display: flex; gap: 4px; }
.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; }
button.dir { width: 46px; padding: .4rem 0; }

// Code not found

Now press Safe autopilot. The snake stops chasing the apple greedily and instead follows a single fixed loop — a Hamiltonian cycle that visits every cell exactly once and returns to its start. Because the loop never crosses itself, the snake can grow all the way to a full board without ever getting trapped. Press Show safe loop to see the order of cells the loop follows. The catch: this clean loop exists because the grid is small and even-sided. On a general board — or a general graph — finding such a route is the hard part.

How hard is Snake, really? Not the reflexes — the routing.

• Checking a finished route is trivial: walk along it and confirm it never repeats a cell and never steps off the grid.
• Brute force tries every possible path through the cells — the number of self-avoiding walks on a grid explodes super-exponentially, hopeless past a tiny board.
• It's NP-complete. Filling the board means finding a Hamiltonian path — a route visiting every vertex exactly once. Deciding whether such a path exists in a graph is one of Richard Karp's original 21 NP-complete problems (1972), as hard as any problem in NP.
• So optimal Snake is NP-hard. Once the board fills up, choosing a move that still leaves a route to swallow every remaining cell is exactly the Hamiltonian-path question — there is no known way to do it quickly in general.

That is the punchline: the moment the board gets crowded and "head toward the food" stops working, you are staring at a genuine instance of the same problem behind P vs NP. The safe loop in the demo is a lucky special case — grids have one; arbitrary graphs, like the ones behind the traveling salesman problem, do not hand you one for free.

"Visit every node exactly once" is one of the most common shapes a real problem can take, and Snake is its friendly face:

• Route and delivery planning: covering every street or stop without retracing is a Hamiltonian-style problem, the close cousin of the traveling salesman problem.
• DNA sequencing: reconstructing a genome from overlapping fragments can be cast as finding a path that uses each piece once.
• Circuit and chip testing: walking a probe through every component exactly once is the same visit-everything constraint.
• Teaching complexity: because everyone has played it, Snake is one of the clearest on-ramps to what a Hamiltonian path — and NP-hardness — even means.

Learn why Snake is hard and you've met Hamiltonian paths — the engine under route optimization, sequencing and the whole P vs NP story.

Snake hides a beautiful secret: winning it — filling every square — means tracing a Hamiltonian path, and deciding whether one exists is NP-complete, as hard as anything in computer science. Checking a route stays instant; finding one in general does not.

So the next time the board fills up and there is suddenly nowhere safe to turn, take comfort — you haven't played badly. You've simply run into P vs NP hiding behind a row of pixels, and there may be no clever shortcut around the squeeze at all.