Tetris is Hard with Just One Piece Type

This paper establishes that Tetris clearing and survival are NP-hard for any single tetromino type except the O-piece under the Super Rotation System, disproving a long-standing conjecture about the I-piece, while simultaneously providing polynomial-time algorithms for cases involving only dominoes or $1\times k$ pieces under specific initial board conditions.

The Gist

Imagine you are playing a game of Tetris. You know the rules: blocks fall, you rotate them, and you try to clear lines. Usually, the game gives you a random mix of all seven different block shapes (the "I", "O", "T", "L", "J", "S", and "Z" pieces).

This paper asks a very specific, almost silly question: What if the game only gave you ONE type of block? Could you still clear the board? Could you survive? And more importantly, is figuring out the answer to those questions easy for a computer, or is it a nightmare?

The authors, a group from MIT called the "MIT Hardness Group," discovered that for almost every single block shape, the answer is: It's a nightmare. In fact, it's so hard that it belongs to a class of problems called NP-hard.

Here is the breakdown of their findings using simple analogies.

1. The Big Discovery: "One-Shape" Tetris is Still a Monster

For 23 years, experts thought that if you restricted Tetris to only use the "I" piece (the long, straight bar), the game would become easy to solve. They thought, "Oh, it's just a straight line; surely a computer can figure out where to put it."

The authors proved them wrong.

They showed that even if you only have the "I" piece (or the "L", "J", "S", "Z", or "T" pieces), figuring out if you can clear the board is just as hard as solving the most difficult logic puzzles in the world.

• The Analogy: Imagine trying to build a house using only bricks. You might think, "Well, bricks are all the same, so it should be easy." But the authors showed that if the bricks have to fit into a very specific, pre-built maze with narrow corridors, figuring out the exact order to drop them is a brain-busting puzzle.

The Exception: The only piece that might be easy is the "O" piece (the square). The paper doesn't fully solve this one yet, but it's the only one left standing as a mystery.

2. The Secret Weapon: "Kicks" and "Spins"

Why is a single straight line so hard? It's because of a rule in modern Tetris called the Super Rotation System (SRS).

In old Tetris, if you tried to rotate a piece against a wall, it would just get stuck. In modern Tetris, the game tries to "kick" the piece sideways to make the rotation fit.

• The Analogy: Imagine trying to turn a long sofa around a tight corner in a hallway. If you just try to spin it, it hits the wall. But if you nudge it forward, then spin, then nudge it back, you can actually get it to turn. This is called a "kick" or a "spin."
• The authors used these "kicks" to create complex logic machines inside the Tetris board. They built tiny "gadgets" (like logic gates in a computer) using only the "I" pieces, proving that the game can simulate a computer processor. If the game can simulate a computer, solving it is as hard as any computer problem.

3. The Good News: The "Domino" Case

While the "I" piece is a monster, the authors found a bright spot. They looked at Dominoes (which are just 2-block pieces, like a tiny "I").

If you play Tetris with only dominoes, and you assume a simple rule where they can't magically jump up when they rotate, the authors found a fast, easy way to solve it.

• The Analogy: If you are trying to tile a floor with 2x1 tiles, you can just look at the floor and say, "Okay, I'll fill the holes first, then make sure the columns match up." It's a straightforward checklist.
• This solves a 9-year-old mystery about whether "Domino Tetris" is easy or hard. (Spoiler: It's easy, under specific rules).

4. The "7-Bag" Twist

In real Tetris, you don't get random pieces; you get them in "bags" of 7, where every bag has exactly one of each shape.
The authors showed that even if you force the game to follow this "7-bag" rule, but you only care about clearing the board using the "I" pieces (and the other pieces just have to be placed somewhere else to get them out of the way), the problem is still NP-hard.

• The Analogy: Imagine a chef who must use every ingredient in a specific recipe box, but the only dish they care about cooking is a soup made of just potatoes. Even though they have to juggle carrots, onions, and meat just to get the potatoes in the pot, figuring out if the soup can be made is still incredibly difficult.

5. The "Survival" vs. "Clearing" Distinction

The paper looks at two goals:

1. Clearing: Can you wipe the whole board clean?
2. Survival: Can you stay alive long enough to use all the pieces without the stack reaching the top?

They proved that for almost every single piece type, both goals are incredibly hard to predict.

• The Analogy: It's like being a firefighter.
  • Clearing is asking: "Can we put out every single fire in this building?"
  • Survival is asking: "Can we keep the building from burning down for the next hour?"
  • The authors proved that for almost any single tool you have (like a single type of fire hose), figuring out the answer to either question is a massive headache for a computer.

Summary

• The Bad News: If you restrict Tetris to almost any single block shape (especially the long "I" bar), the game becomes a super-complex logic puzzle that computers struggle to solve. The idea that "I" pieces would make the game easy was a myth.
• The Good News: If you play with Dominoes (2-blocks) under simple rules, there is a fast, easy strategy to win.
• The Takeaway: Tetris is deceptively deep. Even when you take away all the variety and give the player just one tool, the game's mechanics (like the "kick" system) are complex enough to simulate the hardest problems in computer science.

In short: Don't underestimate a single straight line in Tetris; it might just be the most complicated puzzle piece in the world.

Technical Summary

Here is a detailed technical summary of the paper "Tetris is Hard with Just One Piece Type" by the MIT Hardness Group.

1. Problem Definition

The paper investigates the computational complexity of two fundamental Tetris objectives under the constraint that the player is restricted to a single polyomino piece type (e.g., only $I$-pieces, only $L$-pieces, etc.):

• Tetris Clearing: Determining if a player can completely clear an initial board state using a given finite sequence of pieces.
• Tetris Survival: Determining if a player can avoid losing (stacking pieces above a certain height) while placing all pieces in a given sequence.

The study assumes the Super Rotation System (SRS), the standard rotation and "wall kick" mechanics used in modern Tetris games (post-2001). This distinguishes the work from previous hardness proofs that often relied on simpler rotation models or restricted piece types (like unrotatable dominoes).

2. Methodology

The authors employ NP-hardness reductions from known NP-complete problems to the Tetris clearing/survival problems. The core methodology involves constructing complex board layouts ("gadgets") that simulate the logic of these source problems.

• Source Problems:
  • 1-in-3SAT: Used for reductions involving $I$-pieces.
  • Planar Biconnected Graph Orientation: Used for reductions involving $J$, $L$, $T$, $S$, and $Z$ pieces. Specifically, variants where nodes must have specific in-degrees (e.g., 0 or 4, or 1 or 3).
  • Planar Monotone Rectilinear 3SAT: Used for reductions involving $O$-pieces.
• Gadget Construction:
  • The authors design specific "gadgets" (Corner, Line, Duplicator, Clause, Crossover, Parity Fixer) that act as logic gates or wires.
  • SRS Mechanics: A critical component of the methodology is leveraging the SRS wall kicks. The proofs rely heavily on the ability of pieces to "spin" or rotate into tight spaces by shifting position when a standard rotation is blocked. This allows for complex maneuvers (like climbing vertical structures) that would be impossible in simpler rotation models.
  • Tunneling: The constructions include "long tunnels" that force a specific tiling order. If a player places a piece incorrectly in the tunnel before the main logic structure is filled, the path becomes blocked, making the board un-clearable. This enforces a strict sequence of operations.
• Polynomial-Time Algorithms: For the positive results (dominoes and $1 \times k$ pieces), the authors use dynamic programming and greedy strategies to track reachable states and hole elimination, proving that these specific restricted cases are in P.

3. Key Contributions and Results

A. NP-Hardness for Single Piece Types (Negative Results)

The paper proves that Tetris clearing and survival are NP-hard for almost all single tetromino types under SRS, even when the input sequence consists of only that specific piece type.

• $I$-pieces (Straight): NP-hard for clearing and survival. This disproves a 23-year-old conjecture (from 2004) that Tetris with only $I$-pieces might be solvable in polynomial time.
• $J$ and $L$-pieces: NP-hard.
• $T$-pieces: NP-hard.
• $S$ and $Z$-pieces: NP-hard.
• $O$-pieces (Square): NP-hard.
• Bag Randomizers: As a corollary, the authors prove that clearing is NP-hard even if the sequence must be generated by a 7-bag randomizer (or $7k$-bag), a standard mechanism in modern Tetris that ensures a balanced distribution of pieces. This is significant because it shows hardness persists even with the "fairness" of modern randomizers.
• Holding Feature: The results hold even if the player has a "hold" slot, as holding identical pieces does not change the permutation possibilities.

B. Polynomial-Time Algorithms (Positive Results)

• Dominoes ($1 \times 2$): The authors provide a polynomial-time algorithm for both clearing and survival with rotatable dominoes, assuming a "falling rotation model" (where the rotation center moves monotonically downward). This resolves an open problem from 2017.
• **$1 \times k$Pieces:** They generalize the domino result to$1 \times k$pieces (sticks) for any fixed$k$, provided the top$k-1$rows of the board are initially empty. This highlights that the NP-hardness of the$I$-piece result specifically relies on the ability to fill the top three rows.

C. Disproving Conjectures

The work explicitly refutes the conjecture that Tetris with only $I$-pieces is in P. The authors demonstrate that the complexity arises from the interaction between the specific geometry of the $I$-piece and the SRS wall kicks, which allow for "spins" that can navigate complex, pre-filled board states.

4. Significance

• Resolution of Long-Standing Open Problems: The paper settles multiple open problems regarding the complexity of Tetris with restricted piece sets, which have been debated since the early 2000s.
• Refinement of Hardness Conditions: It establishes that the computational hardness of Tetris is robust; it does not disappear even when the player is restricted to a single piece type, provided the standard modern rotation system (SRS) is used.
• Mechanism of Hardness: The paper elucidates that the "kicking" mechanic in SRS is a primary source of computational complexity, enabling moves that simulate complex logic gates (like 1-in-3SAT) which are impossible in simpler rotation systems.
• Practical Implications: By proving hardness for 7-bag randomizers, the paper suggests that even "fair" modern Tetris games are computationally intractable to solve optimally, even with perfect information and a single piece type.

5. Remaining Open Problems

The authors identify several remaining challenges:

• $O$-pieces (Square): While they proved hardness for clearing, the complexity of survival with $O$-pieces remains open (though they suspect it is NP-hard).
• Different Rotation Models: The polynomial-time result for dominoes relies on a specific "falling" rotation model. The complexity under a full SRS-like rotation system for dominoes remains unknown.
• Infinite Sequences: The paper focuses on finite sequences. The complexity of clearing/surviving with an infinite stream of a single piece type is an open question.
• Counting Complexity: Whether these problems are #P-hard (counting the number of solutions) or ASP-complete remains an open area of research.

In summary, this paper fundamentally shifts the understanding of Tetris complexity, demonstrating that the game remains computationally intractable even under severe restrictions (single piece type) when played with modern mechanics.