Introduction

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.

Try It

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">Guide the snake with the arrow buttons to eat the apple. Or press <b>Safe autopilot</b>: the snake follows a fixed <b>Hamiltonian cycle</b> — a single loop that visits every cell exactly once — so it can fill the whole board without ever trapping itself.</p>
<div id="board" class="board"></div>
<div class="status" id="status">Length: 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">Safe autopilot</button>
  <button id="cycle" type="button" class="ghost">Show safe loop</button>
  <button id="reset" type="button" class="ghost">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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Snake on a 6x6 grid. Filling the whole board = visiting every cell once = a Hamiltonian path. Finding such a path on an arbitrary graph is NP-complete, but on a grid with an even side a fixed "boustrophedon" Hamiltonian CYCLE always exists — the autopilot rides it and can never trap itself.
const N = 6, COUNT = N * N;
const idx = (r, c) => r * N + c;
const rc = (i) => [Math.floor(i / N), i % N];

// Build a Hamiltonian cycle (single loop touching every cell once, with each step grid-adjacent and the last cell adjacent to the first). order[k] = the cell visited at step k; pos[cell] = its step number along the loop.
function buildCycle() {
  const order = [];
  for (let c = 0; c < N; c++) order.push(idx(0, c));        // top row, left -> right
  for (let c = N - 1; c >= 1; c--) {                        // serpentine the block below
    if ((N - 1 - c) % 2 === 0) { for (let r = 1; r < N; r++) order.push(idx(r, c)); }      // down
    else { for (let r = N - 1; r >= 1; r--) order.push(idx(r, c)); }                       // up
  }
  for (let r = N - 1; r >= 1; r--) order.push(idx(r, 0));   // back up the left column
  const pos = new Array(COUNT);
  order.forEach((cell, k) => { pos[cell] = k; });
  return { order, pos };
}
const { order, pos } = buildCycle();
const next = (cell) => order[(pos[cell] + 1) % COUNT]; // step along the cycle

let snake, food, dir, alive, showPath, timer;

function reset() {
  snake = [idx(0, 0)];               // start top-left, on the cycle
  dir = [0, 1];                       // moving right
  placeFood();
  alive = true; showPath = false;
  stopAuto();
  render(); setStatus(fmt('Length: 1 / %COUNT%', { COUNT: COUNT }), '');
}
function placeFood() {
  const body = new Set(snake);
  const free = []; for (let i = 0; i < COUNT; i++) if (!body.has(i)) free.push(i);
  food = free.length ? free[Math.floor(Math.random() * free.length)] : -1;
}
function setStatus(t, cls) { const s = document.getElementById('status'); s.textContent = t; s.className = 'status ' + cls; }

function step(d) {
  if (!alive) return;
  const head = snake[snake.length - 1];
  const [hr, hc] = rc(head);
  const nr = hr + d[0], nc = hc + d[1];
  if (nr < 0 || nr >= N || nc < 0 || nc >= N) { die('Hit a wall.'); return; }
  const target = idx(nr, nc);
  const willGrow = target === food;
  const body = new Set(willGrow ? snake : snake.slice(1)); // tail moves unless we grow
  if (body.has(target)) { die('Ran into itself.'); return; }
  snake.push(target);
  if (willGrow) {
    if (snake.length === COUNT) { render(); setStatus('Board full! 36 / 36 — perfect game.', 'win'); alive = false; stopAuto(); return; }
    placeFood();
  } else { snake.shift(); }
  dir = d; render();
  if (alive) setStatus(fmt('Length: %length% / %COUNT%', { length: snake.length, COUNT: COUNT }), '');
}
function die(msg) { alive = false; stopAuto(); render(); setStatus(fmt('💥 %msg% Length %length%. Reset to try again.', { msg: msg, length: snake.length }), 'dead'); }

function render() {
  const b = document.getElementById('board'); b.innerHTML = '';
  const body = new Set(snake); const head = snake[snake.length - 1];
  for (let i = 0; i < COUNT; i++) {
    const d = document.createElement('div'); let cls = 'cell';
    if (showPath) cls += ' path';
    if (i === food) cls += ' food';
    if (body.has(i)) cls += (i === head ? ' head' : ' snake');
    d.className = cls;
    if (showPath && !body.has(i)) { const n = document.createElement('span'); n.className = 'num'; n.textContent = pos[i]; d.appendChild(n); }
    b.appendChild(d);
  }
}

function stopAuto() { if (timer) { clearInterval(timer); timer = null; } }
function autoStep() {
  if (!alive) { stopAuto(); return; }
  const head = snake[snake.length - 1];
  const nextCell = next(head);               // always the next cell on the cycle
  const [hr, hc] = rc(head), [tr, tc] = rc(nextCell);
  step([tr - hr, tc - hc]);
}
document.getElementById('auto').addEventListener('click', () => {
  if (timer) { stopAuto(); return; }
  if (!alive) reset();
  showPath = true; render();
  timer = setInterval(autoStep, 130);
});
document.getElementById('cycle').addEventListener('click', () => { showPath = !showPath; render(); });
document.getElementById('reset').addEventListener('click', reset);
document.getElementById('up').addEventListener('click', () => { stopAuto(); step([-1, 0]); });
document.getElementById('down').addEventListener('click', () => { stopAuto(); step([1, 0]); });
document.getElementById('left').addEventListener('click', () => { stopAuto(); step([0, -1]); });
document.getElementById('right').addEventListener('click', () => { stopAuto(); step([0, 1]); });
reset();
Result
Console

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.

The Real Complexity

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.

Where It Matters

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

Conclusion

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.

Share this article

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

Comments

Loading comments...

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