A simple Snake solver in 60 lines
Here is a simple Snake game, where the snake is controlled by the computer. Click to add bits of food for the snake.
JS and SVG support required.
How does it work?
Thanks to two simple tricks.
The first trick stemmed from a simple heuristic: a good snake, one who never traps itself, usually slithers in alternating directions on consecutive rows or columns. If it went left on the last row, it would go right on this row; and if it went up on the last column, it would go down on this column.
We built our snake to strictly follow this rule: on even-numbered columns (starting from zero), it will always go down; whereas on odd-numbered columns, always goes up. A similar rule follows for rows. To the snake, the field looks like this, where each segment is walkable in only one direction:
JS and SVG support required.
Note that each corner has exactly one incoming edge and one outgoing edge.
On a field with even width and height, it is provable that such a snake never goes into a dead end, where all paths ahead are walls or its own body.
The second trick is about knowing the future. When the snake is plotting its path, it carries out a breadth-first search on the directed graph shown above, stopping the search when food is found. When the search runs into a piece of the snake's body, the algorithm checks whether this piece would still be there when the head arrives — because sometimes this part of the snake moves away when that time comes.
Here you can see the snake's search tree (select “All”) and the path it determined (select “Shortest”):
JS and SVG support required.
Combining the two tricks, we have a snake who will devour any bits of food available, filling the field so that no more food can be dropped.
The solver, 60 lines of JavaScript determining the snake's moves, is available at js/snake.js § lines 89–148.