The Complexity of Snake

Authors Marzio De Biasi, Tim Ophelders



PDF
Thumbnail PDF

File

LIPIcs.FUN.2016.11.pdf
  • Filesize: 0.62 MB
  • 13 pages

Document Identifiers

Author Details

Marzio De Biasi
Tim Ophelders

Cite AsGet BibTex

Marzio De Biasi and Tim Ophelders. The Complexity of Snake. In 8th International Conference on Fun with Algorithms (FUN 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 49, pp. 11:1-11:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.FUN.2016.11

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.
Keywords
  • Games
  • Puzzles
  • Motion Planning
  • Nondeterministic Constraint Logic
  • PSPACE

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Elias Dahlhaus, Peter Horák, Mirka Miller, and Joseph F. Ryan. The train marshalling problem. Discrete Applied Mathematics, 103(1-3):41-54, 2000. URL: http://dx.doi.org/10.1016/S0166-218X(99)00219-X.
  2. Erik D. Demaine and Robert A. Hearn. Playing games with algorithms: Algorithmic combinatorial game theory. In Games of No Chance 3, volume 56 of Mathematical Sciences Research Institute Publications, pages 3-56. Cambridge University Press, 2009. Google Scholar
  3. Robert A Hearn and Erik D Demaine. PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation. Theoretical Computer Science, 343(1):72-96, 2005. Google Scholar
  4. Robert A. Hearn and Erik D. Demaine. Games, puzzles and computation. A K Peters, 2009. Google Scholar
  5. Graham Kendall, Andrew J. Parkes, and Kristian Spoerer. A survey of NP-complete puzzles. ICGA Journal, 31(1):13-34, 2008. Google Scholar
  6. Irina Kostitsyna and Valentin Polishchuk. Simple wriggling is hard unless you are a fat hippo. Theory of Computing Systems, 50(1):93-110, 2012. URL: http://dx.doi.org/10.1007/s00224-011-9337-4.
  7. J.-C. Latombe. Robot Motion Planning. Kluwer, Boston, MA, 1991. Google Scholar
  8. Amit Pamecha, Imme Ebert-Uphoff, and Gregory S. Chirikjian. Useful metrics for modular robot motion planning. IEEE Transactions on Robotics and Automation, 13(4):531-545, 1997. URL: http://dx.doi.org/10.1109/70.611311.
  9. Christos H. Papadimitriou and Umesh V. Vazirani. On two geometric problems related to the traveling salesman problem. Journal of Algorithms, 5(2):231-246, 1984. URL: http://dx.doi.org/10.1016/0196-6774(84)90029-4.
  10. Roberto Tamassia. On embedding a graph in the grid with the minimum number of bends. SIAM Journal on Computing, 16(3):421-444, 1987. URL: http://dx.doi.org/10.1137/0216030.
  11. Christopher Umans and William Lenhart. Hamiltonian cycles in solid grid graphs. In FOCS, pages 496-505, 1997. URL: http://dx.doi.org/10.1109/SFCS.1997.646138.
  12. Tom C. van der Zanden. Parameterized Complexity of Graph Constraint Logic. In IPEC, pages 282-293, 2015. URL: http://dx.doi.org/10.4230/LIPIcs.IPEC.2015.282.
  13. Giovanni Viglietta. Gaming is a hard job, but someone has to do it! Theory of Computing Systems, 54(4):595-621, 2014. URL: http://dx.doi.org/10.1007/s00224-013-9497-5.
  14. Zhi Yan, Nicolas Jouandeau, and Arab Ali Cherif. A survey and analysis of multi-robot coordination. International Journal of Advanced Robotic Systems, 10:399, 2013. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail