Document Open Access Logo

Trainyard is NP-hard

Authors Matteo Almanza, Stefano Leucci, Alessandro Panconesi

PDF

File

Thumbnail PDF
PDF
LIPIcs.FUN.2016.2.pdf
  • Filesize: 2.38 MB
  • 14 pages

Document Identifiers

Subject Classification

Keywords
  • Complexity of Games
  • Trainyard

Metrics

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

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).

Cite As Get 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

Author Details

Matteo Almanza
Stefano Leucci
Alessandro Panconesi

References

  1. 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.
  2. Casual Games Association. Casual games sector report: Towards the global games market in 2017. http://www.casualconnect.org/education.html. Accessed: 2016-02-22.
  3. 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.
  4. 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. Google Scholar
  5. David Eppstein. Computational complexity of games and puzzles. https://www.ics.uci.edu/~eppstein/cgt/hard.html. Accessed: 2016-02-22.
  6. 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.
  7. 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.
  8. Robert A. Hearn and Erik D. Demaine. Games, puzzles, and computation. CRC Press, 2009. Google Scholar
  9. Graham Kendall, Andrew J. Parkes, and Kristian Spoerer. A survey of NP-complete puzzles. ICGA Journal, 31(1):13-34, 2008. Google Scholar
  10. Rahul Mehta. 2048 is (PSPACE) hard, but sometimes easy. CoRR, abs/1408.6315, 2014. Google Scholar
  11. 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.
  12. Matt Rix. The story so far. http://struct.ca/2010/the-story-so-far/. Accessed: 2016-02-22.
  13. Matt Rix. Trains on paper. http://struct.ca/2010/trains-on-paper/. Accessed: 2016-02-22.
  14. Matt Rix. The week that was. http://struct.ca/2010/the-week-that-was/. Accessed: 2016-02-22.
  15. 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.
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact