University of Twente Student Theses
Playing Snake on a Graph
Graafsma, D.F. (2024) Playing Snake on a Graph.
|
PDF
11MB |
| Abstract: | The mathematical study of puzzles and games has gained quite some popularity. We contribute to this growing area of research by introducing the game of Snake on a graph. Based on the classic computer game Snake, a snake forms a simple path that has to move to an apple while avoiding colliding with itself. When the snake reaches the apple, it grows longer, and a new apple appears. A graph on which the snake has a strategy to keep eating apples until it covers all the vertices of the graph is called snake-winnable. We refer to the problem of determining whether a graph is snake-winnable as the snake problem. We prove the snake problem is NP-hard, even when restricted to grid graphs. For odd-sized bipartite graphs and graphs with vertex-connectivity 1, we fully characterize the snake-winnable graphs. Furthermore, we show that non-Hamiltonian graphs with a girth greater than 6 are never snake-winnable and provide a necessary graph structure for all snake-winnable graphs. |
| Item Type: | Essay (Master) |
| Faculty: | EEMCS: Electrical Engineering, Mathematics and Computer Science |
| Subject: | 31 mathematics |
| Programme: | Applied Mathematics MSc (60348) |
| Link to this item: | https://purl.utwente.nl/essays/102968 |
| Export this item as: | BibTeX EndNote HTML Citation Reference Manager |
Show download statistics for this publication
Show download statistics for this publicationRepository Staff Only: item control page