Threes!, Fives, 1024!, and 2048 are hard

DOI10.4230/LIPICS.FUN.2016.22zbMATH Open1369.68243OpenAlexW2964098108MaRDI QIDQ5282820FDOQ5282820

Authors: Stefan Langerman, Yushi Uno 

Publication date: 17 July 2017

Full work available at URL: http://dx.doi.org/10.4230/LIPIcs.FUN.2016.22

Recommendations

• Threes!, Fives, 1024!, and 2048 are hard
• 2048 without new tiles is still hard
• Trainyard is NP-hard
• Trainyard is NP-hard
• TETRIS IS HARD, EVEN TO APPROXIMATE

zbMATH Keywords

algorithmic combinatorial game theory20481024!FivesThrees!

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)

Cited In (10)

• Systematic selection of \(N\)-tuple networks for 2048
• Threes!, Fives, 1024!, and 2048 are hard
• Trainyard is NP-hard
• 2048 without new tiles is still hard
• HOW DIFFICULT IS IT TO INVENT A NONTRIVIAL GAME?
• TETRIS IS HARD, EVEN TO APPROXIMATE
• Tetris is Hard, Even to Approximate
• Tracks from hell -- when finding a proof may be easier than checking it
• Trainyard is NP-hard
• Making change in 2048

This page was built for publication: Threes!, Fives, 1024!, and 2048 are hard

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