We consider the popular smartphone game Trainyard: a puzzle game that requires the player to lay down tracks in order to route colored trains from departure stations to suitable arrival stations. While it is already known [Almanza et al., FUN 2016] that the problem of finding a solution to a given Trainyard instance (i.e., game level) is NP-hard, determining the computational complexity of checking whether a candidate solution (i.e., a track layout) solves the level was left as an open problem. In this paper we prove that this verification problem is PSPACE-complete, thus implying that Trainyard players might not only have a hard time finding solutions to a given level, but they might even be unable to efficiently recognize them.

Tracks from hell - when finding a proof may be easier than checking it / Almanza, M.; Leucci, S.; Panconesi, A.. - 100:(2018). (Intervento presentato al convegno 9th International Conference on Fun with Algorithms, FUN 2018 tenutosi a La Maddalena Island; Italy) [10.4230/LIPIcs.FUN.2018.4].

Tracks from hell - when finding a proof may be easier than checking it

Almanza M.;Leucci S.;Panconesi A.
2018

Abstract

We consider the popular smartphone game Trainyard: a puzzle game that requires the player to lay down tracks in order to route colored trains from departure stations to suitable arrival stations. While it is already known [Almanza et al., FUN 2016] that the problem of finding a solution to a given Trainyard instance (i.e., game level) is NP-hard, determining the computational complexity of checking whether a candidate solution (i.e., a track layout) solves the level was left as an open problem. In this paper we prove that this verification problem is PSPACE-complete, thus implying that Trainyard players might not only have a hard time finding solutions to a given level, but they might even be unable to efficiently recognize them.
2018
9th International Conference on Fun with Algorithms, FUN 2018
Puzzle games; Solitaire games; Trainyard; Verification
04 Pubblicazione in atti di convegno::04b Atto di convegno in volume
Tracks from hell - when finding a proof may be easier than checking it / Almanza, M.; Leucci, S.; Panconesi, A.. - 100:(2018). (Intervento presentato al convegno 9th International Conference on Fun with Algorithms, FUN 2018 tenutosi a La Maddalena Island; Italy) [10.4230/LIPIcs.FUN.2018.4].
File allegati a questo prodotto
File Dimensione Formato  
Almanza_Tracks_2018.pdf

accesso aperto

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Creative commons
Dimensione 857.72 kB
Formato Adobe PDF
857.72 kB Adobe PDF

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/1351508
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? ND
social impact