LIPIcs.FUN.2016.11.pdf
- Filesize: 0.62 MB
- 13 pages
Document
The Complexity of Snake
Authors
-
Part of:
Volume:
8th International Conference on Fun with Algorithms (FUN 2016)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Conference on Fun with Algorithms (FUN) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2016-06-02
Cite As Get 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.
Subject Classification
Keywords
- Games
- Puzzles
- Motion Planning
- Nondeterministic Constraint Logic
- PSPACE
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- 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.
-
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.
-
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.
-
Robert A. Hearn and Erik D. Demaine. Games, puzzles and computation. A K Peters, 2009.
-
Graham Kendall, Andrew J. Parkes, and Kristian Spoerer. A survey of NP-complete puzzles. ICGA Journal, 31(1):13-34, 2008.
- 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.
-
J.-C. Latombe. Robot Motion Planning. Kluwer, Boston, MA, 1991.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
-
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.