License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FUN.2016.11
URN: urn:nbn:de:0030-drops-58841
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/5884/
Go to the corresponding LIPIcs Volume Portal

De Biasi, Marzio ; Ophelders, Tim

The Complexity of Snake

pdf-format:
24.pdf (0.6 MB)

Abstract

Snake and Nibbler are two well-known video games in which a snake slithers through a maze and grows as it collects food. During this process, the snake must avoid any collision with its tail. Various goals can be associated with these video games, such as avoiding the tail as long as possible, or collecting a certain amount of food, or reaching some target location. Unfortunately, like many other motion-planning problems, even very restricted variants are computationally intractable. In particular, we prove the NP--hardness of collecting all food on solid grid graphs; as well as its PSPACE-completeness on general grid graphs. Moreover, given an initial and a target configuration of the snake, moving from one configuration to the other is PSPACE-complete, even on grid graphs without food, or with an initially short snake.
Our results make use of the nondeterministic constraint logic framework by Hearn and Demaine, which has been used to analyze the computational complexity of many games and puzzles. We extend this framework for the analysis of puzzles whose initial state is chosen by the player.

BibTeX - Entry

@InProceedings{debiasi_et_al:LIPIcs:2016:5884,
  author =	{Marzio De Biasi and Tim Ophelders},
  title =	{{The Complexity of Snake}},
  booktitle =	{8th International Conference on Fun with Algorithms (FUN 2016)},
  pages =	{11:1--11:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-005-7},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{49},
  editor =	{Erik D. Demaine and Fabrizio Grandoni},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/5884},
  URN =		{urn:nbn:de:0030-drops-58841},
  doi =		{10.4230/LIPIcs.FUN.2016.11},
  annote =	{Keywords: Games, Puzzles, Motion Planning, Nondeterministic Constraint Logic, PSPACE}
}

Keywords: Games, Puzzles, Motion Planning, Nondeterministic Constraint Logic, PSPACE
Collection: 8th International Conference on Fun with Algorithms (FUN 2016)
Issue Date: 2016
Date of publication: 02.06.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI