Snake Hamiltonian Cycle: How the Perfect Snake AI Works

The "perfect" Snake AI follows a Hamiltonian cycle: one fixed loop that visits every square of the board exactly once. Its body always trails behind its head along that loop, so it can never crash. To finish faster, it takes shortcuts that skip ahead along the loop but never past its own tail or the apple, and it stops taking them once the snake fills about half the board.

We built that AI for Poozee's Snake, in several versions, and played each one on the game's own code. Every version that kept the tail rule filled the 18x18 board in all 100 test games. The fastest averaged 13,601 steps, 48% fewer than plain loop-following. This guide shows how to build one, why the safety rule works, and what each design choice costs, measured.

How we measured

The bots play the real game: the same rules, the same 18x18 board and the same random apple placement, with a fixed random seed for each game so every result can be checked. All bots played the same 100 games (seeds 1 to 100). A step is one square of movement. Our how to win the snake game guide uses the same setup for 500 games of the simplest bots; this one goes deeper into how the AI is built.

The step counts cover only the games that filled the board. The sections below explain each row.

Step 1: Build the loop

Why an odd-by-odd board has no loop

Color the board like a checkerboard. Every move goes to a neighboring square, and a neighbor is always the other color, so any route alternates colors. A loop has to end on the color it started on, which takes an even number of moves. A loop through every square makes one move per square, so the board needs an even number of squares. A 5x5 board has 25, so no loop can exist, and no Snake AI can follow one.

We checked this with an exhaustive search that counts every loop on small boards (each loop counted once, whichever way you walk it):

The opposite also holds: if one side is even (and both are at least 2), the lawnmower loop below works, which we confirmed on every board from 2x2 to 12x12. Poozee's 18x18 board has 324 squares, so loops exist there too.

Two ways to build one

The lawnmower. Run down the left column, then sweep the other 17 columns row by row from the bottom up, turning at each wall, and finish along the top row. Our how to win the snake game guide has the full 18x18 arrow diagram. It's the loop to use by hand: following it took 2,885 turns per game, against 11,374 for a maze loop.

The maze method. John Tapsell's write-up of his Nokia 6110 Snake AI builds a random loop from a maze half the width and half the height of the board. Each maze cell stands for a 2x2 block of squares, and each block is a tiny 4-square ring. Wherever the maze has a passage between two blocks, cut both rings open on the shared side and join them. A maze has no loops of its own, so the rings merge into a single loop through every square. Because every block is 2x2, this method needs both sides of the board to be even; the lawnmower only needs one. Here is a 4x4 maze (o is a block, - and | are passages) and the 8x8 loop it makes:

o - o - o - o
|   |
o   o - o - o
|       |   |
o - o   o   o
|   |
o   o - o - o

→ → → → → → → ↓
↑ ↓ ← ↓ ← ← ← ←
↑ ↓ ↑ → → → → ↓
↑ ↓ ↑ ← ← ↓ ← ↓
↑ → → ↓ ↑ ↓ ↑ ↓
↑ ↓ ← ↓ ↑ ← ↑ ←
↑ ↓ ↑ → → → → ↓
↑ ← ↑ ← ← ← ← ←

Our maze bot builds a new 9x9 maze for every game with Prim's algorithm (the one Tapsell suggests). One detail matters on Poozee: your snake starts on the 10th row from the top, on squares 5 to 7, heading right, and the loop has to run through those squares in that order. The lawnmower already does. For mazes, we fix two passages before growing the rest, which guarantees it.

Step 2: Follow it (the shape doesn't matter yet)

While the bot only follows the loop, its body always fills the squares just behind its head. Every empty square is somewhere ahead, so the apple is equally likely to be 1, 2, and so on up to all of the empty squares away. That makes the average wait half a lap of the empty part, whatever the loop looks like. Adding it up over all 321 apples gives exactly 26,001 steps for any loop. The measured averages agree: 25,968 on the lawnmower and 26,017 on random mazes.

Step 3: Shortcuts that can never crash you

Think of the loop as a numbered track from 0 to 323. Following it, the snake lies in order along the track: tail, body, head. Tapsell's insight is that as long as you keep that order, you can't crash, because every square from the head forward to the tail is empty.

So a shortcut is any move to a neighboring square further ahead on the track, as long as it doesn't skip past the tail or the apple. Here is the whole rule, with squares numbered 0 to 323:

const N = 324; // squares in all
// order[s]: s's place on the loop
// loop[i]: the square in place i
const ahead = (a, b) =>
  (order[b] - order[a] + N) % N;

// h, t, f: head, tail, food
// nb: the squares next to the head
function nextSquare(h, t, f, nb) {
  // Never skip past tail or food.
  const max = Math.min(
    ahead(h, t), ahead(h, f));
  // By default, follow the loop.
  const i = (order[h] + 1) % N;
  let best = loop[i];
  for (const n of nb) {
    const jump = ahead(h, n);
    if (jump > ahead(h, best) &&
        jump <= max) best = n;
  }
  return best;
}

The bot takes the neighbor that skips the most, so it moves toward the apple in big jumps. Moving onto the tail's square is fine: the tail leaves it on the same step (it only stays put when the snake eats, and an apple never sits on the tail). Our guide test runs this exact snippet next to the bot through three full games and checks that they choose the same square on every step.

Tapsell's code also keeps a margin of 3 squares to the tail and allows for the growth still to come, which matters when one apple adds several squares. On Poozee each apple adds one square and the rule is checked again every step, so no margin is needed. On the lawnmower with shortcuts until half full, a 3-square margin made almost no difference: 13,853 steps instead of 13,837.

What happens if you drop the tail rule

The tempting shortcut rule is "jump ahead toward the apple as long as the square you land on is empty". We tested exactly that, and it crashed in all 100 games, after a median of 50 apples (103 at best).

The failure is slow, which is what makes it sneaky. The body first fell out of loop order at a median length of 29 squares, then the snake survived a median of 671 more steps before it crashed. Once part of the body sits ahead of the head on the loop, "the next square of the loop" may be full of snake, and eventually there is nowhere left to go.

Step 4: Stop taking shortcuts at half the board

Shortcuts all game barely help: 24,787 steps against 25,968 on the lawnmower. The reason is the squares the snake skips. They stay empty, behind the head, and apples keep appearing in them. The head can't double back, so it has to come all the way around.

We tracked every apple in those 100 games, with shortcuts all game on the lawnmower:

Early on, a skipped square is cheap: the short tail soon moves past it, and the head can shortcut its way back around. Late in the game nearly every apple lands in a skipped square and costs well over 100 steps. Once you follow the loop square by square, the tail moves past the gaps, the head walks through them, and soon no apple can appear behind you.

So when should you stop? We tried five cutoffs:

Half was the best of these on both loops, which matches Tapsell's choice of turning shortcuts off at 50% of the board. We also tried a smarter-sounding rule that caps the skipped squares at 20% of the empty ones instead of using a fixed length. It averaged 21,472 steps on the lawnmower, far worse than simply stopping at half.

Step 5: Take the shortest shortcut, not the biggest jump

Tapsell notes that a shortest-path search could find better shortcuts than his greedy "skip the most" choice. We tried it: our "shortest" bot finds the shortest route to the apple that only ever moves forward along the loop and stays within the safe stretch, working through the squares in loop order, and takes its first step.

It was faster on both loops: 13,699 steps instead of 13,837 on the lawnmower, and 13,601 instead of 13,981 on mazes. The greedy rule loses more on the twisty maze loops (380 steps a game, against 138 on the lawnmower), so with the better route the random maze loop edges out the lawnmower.

The no-loop alternative: shortest path plus a safety check

The other classic design skips the loop entirely. Our version finds the shortest path to the apple around its own body, then imagines a copy of itself eating along that path. If that copy could still reach its own tail, it goes. If not, it moves to the neighboring square from which its tail is farthest away while still reachable, to buy time.

It's fast for most of the game: in the 99 games where it got that far, it reached 300 apples in 13,438 steps on average, against 13,713 for the lawnmower with shortcuts until half full. But it filled the board in only 14 of 100 games. In the other 86 it ended up circling the same route forever without eating, with between 2 and 36 squares still empty. A loop is what guarantees the last few apples.

Build your own perfect Snake AI

1. Check the board. At least one side must be even, or no loop exists.
2. Build a loop that passes through the snake's starting squares in its direction of travel: a lawnmower, or a maze loop with the right passages fixed.
3. Number the loop and keep each square's position in an array, so the distance between two squares along the loop is a single subtraction.
4. Each step, move to the neighbor furthest ahead that doesn't skip past the tail or the apple (the snippet above).
5. Stop shortcuts at half the board and follow the loop square by square from there.
6. Optional: pick the shortest forward route to the apple instead of the biggest jump, for a few percent more speed.

Pro tip: Playing by hand, you don't need to number anything. On the lawnmower, a shortcut is safe whenever every square you'd skip is empty: that is the tail rule in plain words. Our Snake high score tips cover the habits that keep a long snake alive when you play without a loop.

Keep playing

Watch the ideas work in a real game of Snake: start on Chill and follow the lawnmower loop for a few laps. For the human plan, with score targets for when to stop taking shortcuts, read how to win the snake game. If you'd rather start from an empty file, how to code Snake in JavaScript builds the whole game step by step and ends with the plain loop bot, ready for the shortcut rule above. And if you like seeing games settled by exhaustive search, is Mahjong Solitaire always winnable solves 10,000 deals exactly.