License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FUN.2016.22
URN: urn:nbn:de:0030-drops-58661
Go to the corresponding LIPIcs Volume Portal

Langerman, Stefan ; Uno, Yushi

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

30.pdf (0.9 MB)


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*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.

BibTeX - Entry

  author =	{Stefan Langerman and Yushi Uno},
  title =	{{Threes!, Fives, 1024!, and 2048 are Hard}},
  booktitle =	{8th International Conference on Fun with Algorithms (FUN 2016)},
  pages =	{22:1--22:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-005-7},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{49},
  editor =	{Erik D. Demaine and Fabrizio Grandoni},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-58661},
  doi =		{10.4230/LIPIcs.FUN.2016.22},
  annote =	{Keywords: algorithmic combinatorial game theory}

Keywords: algorithmic combinatorial game theory
Collection: 8th International Conference on Fun with Algorithms (FUN 2016)
Issue Date: 2016
Date of publication: 02.06.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI