2026-08-11T00:06:53Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8795 2024-03-06T10:42:40Z ddc:004 open_access

Tracks from hell - when finding a proof may be easier than checking it Almanza, Matteo Leucci, Stefano Panconesi, Alessandro puzzle games solitaire games Trainyard verification 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Matteo Almanza and Stefano Leucci and Alessandro Panconesi 2018 Is Part Of LIPIcs, Volume 100, 9th International Conference on Fun with Algorithms (FUN 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FUN.2018.4 urn:nbn:de:0030-drops-87954 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2018.4 eng https://creativecommons.org/licenses/by/3.0/legalcode