Snake looks nothing like a mathematics problem. But underneath its simple surface lies some genuinely deep mathematical structure — the kind that researchers and computer scientists have spent decades studying.
The Grid as a Graph
In graph theory, the game grid is a lattice graph — a network where every cell is a node and every adjacency is an edge. The snake's movement is a path through this graph. The question "can I fill the entire grid without dying?" is the question "does this graph have a Hamiltonian path?"
What Is a Hamiltonian Path?
A Hamiltonian path visits every node in a graph exactly once. In Snake terms: a route through every cell on the grid, eating every piece of food, without ever backtracking or crossing yourself. Finding Hamiltonian paths in arbitrary graphs is an NP-complete problem — one of the most famous unsolved questions in computer science.
For a rectangular grid, however, Hamiltonian paths are easy to find — they're essentially snake-like spirals or zigzag patterns. The challenge in Snake is not finding the path, but following it while the food spawns in unpredictable positions.
The Collision Problem
Self-collision detection in Snake is a membership query: "Is this coordinate in the set of occupied cells?" For short snakes, a simple array scan works. For very long snakes on large grids, a hash set provides O(1) lookup, reducing a potential bottleneck significantly. Even in a simple game, data structure choice matters.
Probability and Food Spawning
As the snake grows, the number of available cells for food decreases. The probability that randomly spawned food lands in a position reachable by the snake — without requiring it to cross itself dangerously — decreases non-linearly as the grid fills. This is why the last 20% of a perfect game is disproportionately harder than the first 80%.