Trainyard is NP-hard
type: Item
instance of: scholarly article
title: Trainyard is NP-hard
zbMATH Open document ID: 1402.68078
author: Matteo Almanza
author: Stefano Leucci
author: Alessandro Panconesi
published in: Theoretical Computer Science
publication date: 2018-11-23T00:00:00Z
full work available at URL: https://arxiv.org/abs/1603.00928
full work available at URL: http://hdl.handle.net/11573/1291937
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 91A46
zbMATH DE Number: 6983752
zbMATH Keywords: computational complexity
zbMATH Keywords: puzzle games
zbMATH Keywords: solitaire games
zbMATH Keywords: trainyard
MaRDI profile type: MaRDI publication profile
OpenAlex ID: W2766905312
cites work: Classic Nintendo games are (computationally) hard
cites work: Random Debaters and the Hardness of Approximating Stochastic Functions
cites work: Rush Hour is PSPACE-complete, or ``Why you should generously tip parking lot attendants''
cites work: Large peg-army maneuvers
cites work: Games, puzzles, and computation
cites work: Two Dots is NP-complete
cites work: The \((n^ 2-1)\)-puzzle and related relocation problems
cites work: Gaming is a hard job, but someone has to do it!
DOI: 10.1016/J.TCS.2017.09.039
Recommended article: Trainyard is NP-hard
Recommended article: Tracks from hell -- when finding a proof may be easier than checking it
Recommended article: Threes!, Fives, 1024!, and 2048 are hard
description: scientific article; zbMATH DE number 6983752