Snake Path Planning Lab

Can a snake fill the whole board without ever crashing? Compare a Hamiltonian cycle (a loop through every square), shortcuts along it, breadth-first search and a greedy chaser.

Presets

Strategy

Board and speed

Seed: -

Display

Moves needed per apple

measured, by snake lengthcycle theory (N² - L + 1)/2

This run

The Hamiltonian cycle on an even-sized board is a closed path through all N² squares, so a snake that only follows it can never hit itself. The cost: apples are reached by the long way round, on average half the free squares away.

1 - Cycle: measured moves vs closed form

Following the cycle from length 3 until the board is full takes on average N²(N² - 3)/4 moves (N = board side). Many random apple sequences per size.

2 - Strategy shoot-out on the current board

Same apple sequences for every strategy; games are capped at 20 N² moves, so a strategy that only circles counts as a time-out.

3 - When should shortcuts stop?

Shortcuts are used only while the snake is shorter than a chosen fraction of the board, then it falls back to the plain cycle. Sweep that fraction on the current board.

The science

Hamiltonian cycle. A cycle that visits every cell of the grid exactly once and returns to its start. It exists on an N x N grid when N is even (go along the top row, weave through columns 1..N-1, come back up column 0). A snake whose head always moves to the next cell of the cycle only ever enters cells its own body has already left.

Expected cost. With the snake at length L, the free cells are the N² - L cells just ahead of the head on the cycle, and the apple is uniform among them, so the expected distance is (N² - L + 1)/2 moves. Summing from L = 3 to N² - 1 gives E[moves] = N²(N² - 3)/4, 976 on an 8 x 8 board. It grows like N⁴/4.

Safe shortcuts. The body is always a sub-sequence of the cycle. The head may jump to any neighbouring free cell whose cycle position is ahead of it, not beyond the apple and strictly before the tail. That keeps the body in cycle order, so the guarantee survives. A shortcut leaves skipped cells behind the head, though, so late in the game apples may spawn there and cost a full lap: shortcuts help early and hurt late (experiment 3).

BFS and greedy. Breadth-first search finds the shortest free path to the apple. Without a safety rule the snake eventually coils itself into a dead end. The safe variant simulates the move on a copy of the snake and only goes for the apple if the tail is still reachable afterwards; otherwise it chases its tail. Greedy only compares the distance to the apple and walks into traps early.

Simplifications. The snake starts with 3 segments along the cycle; the tail cell counts as free for the next step; no speed-up with length; apples are placed by a seeded generator so a run can be replayed exactly. Time-outs in experiment 2 are not crashes: the strategy was still alive when the move cap ended the game.