Trainyard is NP-hard

DOI10.1016/J.TCS.2017.09.039MaRDI QIDQ1623273zbMATH OpenOpenAlexFDO

Authors Matteo Almanza, Stefano Leucci, Alessandro Panconesi

Publication date 23 November 2018

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1603.00928, http://hdl.handle.net/11573/1291937

zbMATH Keywords

computational complexitysolitaire gamespuzzle gamestrainyard

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorial games (91A46)

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 cite{Eppstein}. Indeed, many puzzle games --such as Mah-Jongg, Sokoban, Candy Crush, and 2048, to name a few-- are known to be NP-hard cite{CondonFLS97, culberson1999sokoban, GualaLN14, Mehta14a}. 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-hard. We also href{http://trainyard.isnphard.com}{provide} an implementation of our hardness reduction.

Recommendations

• Trainyard is NP-hard
• Tracks from hell -- when finding a proof may be easier than checking it
• Tracks from hell -- when finding a proof may be easier than checking it
• Threes!, Fives, 1024!, and 2048 are hard
• Threes!, Fives, 1024!, and 2048 are hard

Cites work

• Classic Nintendo games are (computationally) hard
• Games, puzzles, and computation
• Gaming is a hard job, but someone has to do it!
• Large peg-army maneuvers
• Random Debaters and the Hardness of Approximating Stochastic Functions
• Rush Hour is PSPACE-complete, or ``Why you should generously tip parking lot attendants
• The \((n^ 2-1)\)-puzzle and related relocation problems
• Two Dots is NP-complete

Cited in

(7)

• Threes!, Fives, 1024!, and 2048 are hard
• Threes!, Fives, 1024!, and 2048 are hard
• Tracks from hell -- when finding a proof may be easier than checking it
• Trains, games, and complexity: 0/1/2-player motion planning through input/output gadgets
• Puzzle and dragons is hard
• Tracks from hell -- when finding a proof may be easier than checking it
• Trainyard is NP-hard

This page was built for publication: Trainyard is NP-hard

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1623273)