Puzzle and dragons is hard

DOI10.1016/J.TCS.2024.114477MaRDI QIDQ6204537zbMATH OpenFDO

Authors Junyi Guo, Po-Chun Yu

Publication date 28 March 2024

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

Full work available at URL https://doi.org/10.1016/J.TCS.2024.114477

zbMATH Keywords

NP-completeNP-hard

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Quantum computation (81P68) Stochastic games, stochastic differential games (91A15)

Recommendations

• Trainyard is NP-hard
• Trainyard is NP-hard
• Bust-a-Move/Puzzle Bobble is NP-complete
• Classic Nintendo games are (computationally) hard
• The computational complexity of Angry Birds

Cites work

• A real-time algorithm for the \((n^{2}-1)\)-puzzle
• A simple proof that the \((n^{2} - 1)\)-puzzle is hard
• Games, puzzles, and computation
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Playing games with algorithms: algorithmic combinatorial game theory
• The \((n^ 2-1)\)-puzzle and related relocation problems

This page was built for publication: Puzzle and dragons is hard

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