LIPIcs.FUN.2016.2.pdf
- Filesize: 2.38 MB
- 14 pages
Document
Trainyard is NP-hard
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 AsGet BibTex
Matteo Almanza, Stefano Leucci, and Alessandro Panconesi. Trainyard is NP-hard. In 8th International Conference on Fun with Algorithms (FUN 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 49, pp. 2:1-2:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.FUN.2016.2
https://doi.org/10.4230/LIPIcs.FUN.2016.2
Abstract
Recently, due to the widespread diffusion of smart-phones, mobile puzzle games have experienced a huge increase in their popularity. A successful puzzle has to be both captivating and challenging, and it has been suggested that this features are somehow related to their computational complexity. Indeed, many puzzle games - such as Mah-Jongg, Sokoban, Candy Crush, and 2048, to name a few - are known to be NP-hard.
In this paper we consider Trainyard: a popular mobile puzzle game whose goal is to get colored trains from their initial stations to suitable destination stations. We prove that the problem of determining whether there exists a solution to a given Trainyard level is NP. We also provide an implementation of our hardness reduction (see http://trainyard.isnphard.com).
Keywords
- Complexity of Games
- Trainyard
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Greg Aloupis, Erik D. Demaine, Alan Guo, and Giovanni Viglietta. Classic nintendo games are (computationally) hard. Theoretical Computer Science, 586:135-160, 2015. URL: http://dx.doi.org/10.1016/j.tcs.2015.02.037.
- Casual Games Association. Casual games sector report: Towards the global games market in 2017. http://www.casualconnect.org/education.html. Accessed: 2016-02-22.
- Anne Condon, Joan Feigenbaum, Carsten Lund, and Peter W. Shor. Random debaters and the hardness of approximating stochastic functions. SIAM Journal on Computing, 26(2):369-400, 1997. URL: http://dx.doi.org/10.1137/S0097539793260738.
-
Joseph Culberson. Sokoban is pspace-complete. In Proceedings of the 1st International Conference on Fun with Algorithms (FUN'98), 1998, volume 4, pages 65-76, 1998.
- David Eppstein. Computational complexity of games and puzzles. https://www.ics.uci.edu/~eppstein/cgt/hard.html. Accessed: 2016-02-22.
- Gary William Flake and Eric B. Baum. Rush hour is PSPACE-complete, or "Why you should generously tip parking lot attendants". Theoretical Computer Science, 270(1-2):895-911, 2002. URL: http://dx.doi.org/10.1016/S0304-3975(01)00173-6.
- Luciano Gualà, Stefano Leucci, and Emanuele Natale. Bejeweled, candy crush and other match-three games are (NP-)hard. In Proceedings of the 2014 IEEE Conference on Computational Intelligence and Games (CIG'14), 2014, pages 1-8, 2014. URL: http://dx.doi.org/10.1109/CIG.2014.6932866.
-
Robert A. Hearn and Erik D. Demaine. Games, puzzles, and computation. CRC Press, 2009.
-
Graham Kendall, Andrew J. Parkes, and Kristian Spoerer. A survey of NP-complete puzzles. ICGA Journal, 31(1):13-34, 2008.
-
Rahul Mehta. 2048 is (PSPACE) hard, but sometimes easy. CoRR, abs/1408.6315, 2014.
- Daniel Ratner and Manfred K. Warmuth. Nxn puzzle and related relocation problem. Journal of Symbolic Computation, 10(2):111-138, 1990. URL: http://dx.doi.org/10.1016/S0747-7171(08)80001-6.
- Matt Rix. The story so far. http://struct.ca/2010/the-story-so-far/. Accessed: 2016-02-22.
- Matt Rix. Trains on paper. http://struct.ca/2010/trains-on-paper/. Accessed: 2016-02-22.
- Matt Rix. The week that was. http://struct.ca/2010/the-week-that-was/. Accessed: 2016-02-22.
- Giovanni Viglietta. Gaming is a hard job, but someone has to do it! Theory Computing Systems, 54(4):595-621, 2014. URL: http://dx.doi.org/10.1007/s00224-013-9497-5.