2015/05/16 by Stefan Langerman, Yushi Uno, Langerman, Stefan +1
Computer Science · #Computational Complexity (cs.CC) #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #cs.CC #cs.GT
paper · pdf · doi:10.48550/arxiv.1505.04274
14 pages, 9 figures
arxiv created 2015/05/16 · arxiv updated 2015/05/19
We analyze the computational complexity of the popular computer games Threes!, 1024!, 2048 and many of their variants. For most known versions expanded to an m x n board, we show that it is NP-hard to decide whether a given starting position can be played to reach a specific (constant) tile value.