Paper by Erik D. Demaine

Reference:

Hugo Akitaya, Erik D. Demaine, Jason S. Ku, Jayson Lynch, Mike Paterson, and Csaba D. Tóth, “2048 Without Merging”, in Proceedings of the 32nd Canadian Conference in Computational Geometry (CCCG 2020), Saskatchewan, Saskatoon, Canada, August 5–7, 2020.

BibTeX

@InProceedings{2048_CCCG2020,
  AUTHOR        = {Hugo Akitaya and Erik D. Demaine and Jason S. Ku and Jayson Lynch and Mike Paterson and Csaba D. T{\'o}th},
  TITLE         = {2048 Without Merging},
  BOOKTITLE     = {Proceedings of the 32nd Canadian Conference in Computational Geometry (CCCG 2020)},
  bookurl       = {http://vga.usask.ca/cccg2020/},
  ADDRESS       = {Saskatchewan, Saskatoon, Canada},
  MONTH         = {August 5--7},
  YEAR          = 2020,

  withstudent   = 1,
  unrefereed    = 1,
  dblp          = {https://dblp.org/rec/conf/cccg/AkitayaDKLT20},
  comments      = {Hugo Akitaya's presentation is available on <A HREF="https://youtu.be/m3jkm53WtaU">YouTube</A>.},
}

Abstract:

Imagine t ≤ m n unit-square tiles in an m × n rectangular box that you can tilt to cause all tiles to slide maximally in one of the four orthogonal directions. Given two tiles of interest, is there a tilt sequence that brings them to adjacent squares? We give a linear-time algorithm for this problem, motivated by 2048 endgames. We also bound the number of reachable configurations, and design instances where all t tiles permute according to a cyclic permutation every four tilts.

Comments:

Hugo Akitaya's presentation is available on YouTube.

Availability:

The paper is available in PDF (774k).

See information on file formats.

[Google Scholar search]