DROPS

Document

DOI: 10.4230/LIPIcs.FUN.2024.24

Tetris with Few Piece Types

Authors: MIT Hardness Group, Erik D. Demaine, Holden Hall, and Jeffery Li

Published in: LIPIcs, Volume 291, 12th International Conference on Fun with Algorithms (FUN 2024)

Abstract

We prove NP-hardness and #P-hardness of Tetris clearing (clearing an initial board using a given sequence of pieces) with the Super Rotation System (SRS), even when the pieces are limited to any two of the seven Tetris piece types. This result is the first advance on a question posed twenty years ago: which piece sets are easy vs. hard? All previous Tetris NP-hardness proofs used five of the seven piece types. We also prove ASP-completeness of Tetris clearing, using three piece types, as well as versions of 3-Partition and Numerical 3-Dimensional Matching where all input integers are distinct. Finally, we prove NP-hardness of Tetris survival and clearing under the "hard drops only" and "20G" modes, using two piece types, improving on a previous "hard drops only" result that used five piece types.

Cite as

MIT Hardness Group, Erik D. Demaine, Holden Hall, and Jeffery Li. Tetris with Few Piece Types. In 12th International Conference on Fun with Algorithms (FUN 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 291, pp. 24:1-24:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{mithardnessgroup_et_al:LIPIcs.FUN.2024.24,
  author =	{MIT Hardness Group and Demaine, Erik D. and Hall, Holden and Li, Jeffery},
  title =	{{Tetris with Few Piece Types}},
  booktitle =	{12th International Conference on Fun with Algorithms (FUN 2024)},
  pages =	{24:1--24:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-314-0},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{291},
  editor =	{Broder, Andrei Z. and Tamir, Tami},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2024.24},
  URN =		{urn:nbn:de:0030-drops-199322},
  doi =		{10.4230/LIPIcs.FUN.2024.24},
  annote =	{Keywords: complexity, hardness, video games, counting}
}

Search Results

Documents authored by Li, Jeffery

Tetris with Few Piece Types

Abstract

Cite as

Thanks for your feedback!

Could not send message