2016/03/02 by Matteo Almanza, Almanza, Matteo, Stefano Leucci +3
Computer Science · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #cs.CC
paper · pdf · doi:10.48550/arxiv.1603.00928
arxiv created 2016/03/02 · arxiv updated 2016/03/04
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 \citeEppstein. Indeed, many puzzle games --such as Mah-Jongg, Sokoban, Candy Crush, and 2048, to name a few-- are known to be NP-hard \citeCondonFLS97, 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 \hrefhttp://trainyard.isnphard.comprovide an implementation of our hardness reduction.