Play yourself: arrows or WASD H: human G: greedy shortest-path (BFS) C: Hamiltonian cycle V: Hamiltonian cycle with safe shortcuts Z X: slower / faster (1 to 16 steps per frame) T: show or hide the tour R: restart the current driver The HUD keeps the best length each driver has reached this session, which is the comparison the project exists to make.
Three drivers for the same snake, on the same 12x12 board, so you can watch greedy die and the Hamiltonian cycle fill the board every single time. THE INTERESTING BIT Greedy is optimal per move and fatal overall. It runs a breadth-first search from the head to the food and takes the first step of the shortest path. That question — "what is the quickest way to the food" — says nothing about whether the snake can still reach its own tail afterwards, so it walks into pockets and seals itself in. Watch the yellow path: it swings across the board and never once considers the body it is laying down behind it. **The Hamiltonian cycle cannot trap itself, and that is a proof, not a heuristic.** A Hamiltonian cycle is a closed tour visiting all 144 cells exactly once. Follow it and the snake's body is always a contiguous arc of the tour, and the cell in front of the head is always the next tour cell, which is always outside that arc. So a collision is impossible — the snake cannot fail. Press T to see the tour it is following. A grid graph has a Hamiltonian cycle only when at least one side is even, which is why the board is 12x12 and not 11x11. The tour is the boustrophedon one: the top row left to right, a serpentine down through columns 2–12, then straight back up column 1. tools/verify.py checks it as a graph object — a permutation of all 144 cells whose consecutive entries (including last→first) are orthogonally adjacent — because a tour with one bad step still looks exactly like a snake following a line. The shortcut driver keeps the guarantee and drops the tedium. Pure cycle following is safe and glacial: the food sits an average of 72 cells ahead. The V driver may jump forward along the tour to any free neighbour, provided the jump does not overtake the tail's position on the tour (which would break the arc) and does not overshoot the food (which would mean lapping the board). Same proof, fewer steps. [Measured, in the compiled .sb3 under the headless scratch-vm harness] | driver | outcome | length | steps | |---|---|---|---| | greedy | trapped | 37 | 338 | | Hamiltonian | board full | 144 | 4,807 | | Hamiltonian + shortcuts | board full | 144 | 2,880 | And over 8 games each in the Python transcription (tools/verify.py): | driver | best | median | worst | outcome | |---|---|---|---|---| | greedy | 49 | 34 | 28 | trapped, 8 times out of 8 | | Hamiltonian | 144 | 144 | 144 | board full, 8/8 | | Hamiltonian + shortcuts | 144 | 144 | 144 | board full, 8/8 | The shortcut driver saves about 40% of the steps, not the 5x I expected — because it stops taking shortcuts once the snake is longer than 55% of the board, and that second half is where most of the steps are. Being conservative there is what preserves the guarantee, so the honest headline is "40% faster and still never dies" rather than a bigger number that sometimes loses. HONEST LIMITATIONS - The shortcut margin (3 cells of clearance behind the tail, and no shortcuts past 55% occupancy) is conservative rather than tight. A tighter bound exists; a tighter bound that is still provably safe takes more care than a fixed margin, and getting it wrong turns a guaranteed win into a rare mysterious death. - There is no "perfect" driver. All original - code, art and sound. See Inside is open.
