Tetris

Almost everyone has played Tetris: seven shapes fall into a narrow well, you rotate and slide each one, and a full row vanishes. It feels like a game of reflexes — keep up with the speed and don't let the stack reach the top.

But strip away the clock. Imagine you are handed the entire sequence of pieces in advance and asked a calmer question: place them however you like, and clear as many rows as possible. No time pressure, full information. Surely that is easy?

It is not. Even with the whole future revealed, choosing the placements that maximize cleared lines is one of the hardest kinds of problems we know. The gap between checking a plan and finding the best one is exactly the line that separates the easy problems from the intractable ones.

Here is a tiny offline Tetris: a well only four columns wide, and a short fixed sequence of pieces shown to you in full. There is no clock — your only job is to place each piece (slide it left or right, then drop) so that you clear as many of the two bottom rows as possible.

<p class="hint">{{hint}}</p>
<div class="wrap">
  <div id="well" class="well"></div>
  <div class="side">
    <div class="label">{{label_next}}</div>
    <div id="queue" class="queue"></div>
    <div class="label">{{label_cleared}} <b id="score">0</b> / 2</div>
    <div class="status" id="status">{{status_slide}}</div>
  </div>
</div>
<div class="btns">
  <button id="left" type="button">{{btn_left}}</button>
  <button id="right" type="button">{{btn_right}}</button>
  <button id="drop" type="button">{{btn_drop}}</button>
</div>
<div class="btns">
  <button id="naive" type="button" class="ghost">{{btn_naive}}</button>
  <button id="smart" type="button" class="ghost">{{btn_smart}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.wrap { display: flex; gap: 1.1rem; align-items: flex-start; flex-wrap: wrap; }
.well { display: grid; grid-template-columns: repeat(4, 34px); grid-auto-rows: 34px;
        gap: 2px; background: #d7dde3; padding: 4px; border-radius: 8px; }
.c { width: 34px; height: 34px; border-radius: 5px; background: #eef2f6; }
.c.fill { background: #1d3557; }
.c.cur { background: #4895ef; }
.c.target { box-shadow: inset 0 0 0 2px #adb6c0; }
.side { font-size: .9rem; }
.label { font-weight: 600; margin: .2rem 0 .35rem; color: #333; }
.queue { display: flex; gap: .4rem; margin-bottom: .9rem; }
.mini { display: grid; grid-template-columns: repeat(2, 14px); grid-auto-rows: 14px; gap: 1px; }
.mini .m { width: 14px; height: 14px; border-radius: 3px; background: transparent; }
.mini .m.on { background: #457b9d; }
.status { font-size: .95rem; font-weight: 600; min-height: 1.4em; margin-top: .3rem; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-top: .7rem; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .45; cursor: default; }

// Code not found

Try the Auto: naive button first — it just drops each piece into the leftmost gap and usually leaves holes. Then play it by hand, or press Auto: smart to see the planned placement that clears both rows. Notice the asymmetry: once a final board is shown, checking how many lines it clears takes one glance per row. Finding the placement that clears the most lines means reasoning about how every piece interacts with all the others — and that is the hard part.

How hard is Tetris, really? Not the twitch reflexes — the planning.

• Checking a finished board is trivial: scan each row and count how many are completely full.
• Brute force tries every rotation and column for every piece. With a sequence of n pieces and a handful of choices each, that is exponential — hopeless beyond a few dozen pieces.
• It's NP-hard. In 2003, Erik Demaine, Susan Hohenberger and David Liben-Nowell proved that offline Tetris — where you are given the whole piece sequence up front — is NP-hard for the natural objectives, including maximizing the number of cleared rows. They built the reduction from 3-Partition, encoding a hard number-packing instance as a tower of pieces that clears all its rows only if the numbers can be split into equal-sum groups.
• Even approximating it is hard. The same paper shows you cannot even get close to the optimal number of cleared lines in polynomial time (unless P = NP). So there is no efficient "good enough" shortcut, either.

That is the punchline: the moment the well forces a real choice between placements, you are looking at a genuine instance of the same difficulty behind P vs NP. The piece falling toward you isn't just a reflex test — it's intractability dressed up as a game.

"Fit these shapes into this space without waste" is one of the most common shapes a real problem can take, and Tetris is its friendly face:

• Cutting and packing: laying out parts on a sheet of metal or fabric to waste the least material is the cutting-stock problem, a close cousin of stacking pieces in a well.
• Container and pallet loading: fitting boxes into trucks and shipping containers is three-dimensional Tetris, and logistics companies spend real money getting it close to optimal.
• Memory and storage layout: packing data blocks to avoid wasted gaps is the same "leave no holes" pressure you feel when a piece lands badly.
• Scheduling: fitting jobs into time slots without overlap is another flavor of the same packing tension.

Learn why Tetris is hard and you've met combinatorial packing — the engine under bin packing, cutting stock and countless logistics problems.

Tetris hides a beautiful secret: even when time pressure disappears and the whole future is laid out in front of you, deciding how to play to clear the most lines is NP-hard — and you cannot even reliably get close. Checking a finished board stays instant; finding the best stack is as hard as anything in computer science.

So the next time a piece slots into the only spot left and leaves an ugly hole, take comfort — you may not have played badly. You've simply run into P vs NP falling out of the sky, one block at a time, and there may be no efficient way to avoid the gap at all.