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

DOI10.4230/LIPICS.FUN.2016.22MaRDI QIDQ5282820zbMATH OpenOpenAlexFDO

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

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)

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

Cited in

(10)

• Making change in 2048
• 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

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)