Introduction

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.

Try It

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">Offline Tetris: you know the whole sequence in advance. A well 4 columns wide. Slide the current piece with <b>◀ ▶</b>, then <b>Drop</b>. Your goal: clear <b>both</b> bottom rows. Checking a finished board is one glance per row — finding the placements that clear the most is the hard part.</p>
<div class="wrap">
  <div id="well" class="well"></div>
  <div class="side">
    <div class="label">Next pieces</div>
    <div id="queue" class="queue"></div>
    <div class="label">Cleared rows: <b id="score">0</b> / 2</div>
    <div class="status" id="status">Slide and drop the piece.</div>
  </div>
</div>
<div class="btns">
  <button id="left" type="button">◀ Left</button>
  <button id="right" type="button">Right ▶</button>
  <button id="drop" type="button">Drop</button>
</div>
<div class="btns">
  <button id="naive" type="button" class="ghost">Auto: naive</button>
  <button id="smart" type="button" class="ghost">Auto: smart</button>
  <button id="reset" type="button" class="ghost">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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// OFFLINE TETRIS (NP-hard, Demaine-Hohenberger-Liben-Nowell 2003).
// Width-4 well; the sequence of pieces is known in advance. Goal: clear the
// two bottom rows. Two square (O) pieces tile both rows perfectly IF you put
// one on the left two columns and one on the right two — but a naive "drop in the leftmost gap" strategy stacks them and clears nothing. Checking a final board is one scan per row; finding the clearing placement is the hard part.
const W = 4, H = 6;
// Each piece: list of [dr,dc] cells with dr measured from the piece top.
const O = [[0,0],[0,1],[1,0],[1,1]];
const SEQUENCE = [O, O];          // the known, fixed sequence
const widthOf = (cells) => Math.max(...cells.map(c => c[1])); // 0-based span

let board, idx, curCol;
function reset(){
  board = Array.from({length:H}, () => Array(W).fill(0));
  idx = 0; curCol = 0;
  setStatus('Slide and drop the piece.', '');
  render();
}

// Find the resting top-row for `cells` dropped at column `col`; null if illegal.
function landingRow(b, cells, col){
  if (col < 0 || col + widthOf(cells) >= W) return null;
  for (let r = H - 1; r >= -3; r--){
    let valid = true;
    for (const [dr,dc] of cells){
      const rr = r+dr, cc = col+dc;
      if (rr < 0 || rr >= H || cc < 0 || cc >= W || b[rr][cc]){ valid = false; break; }
    }
    if (!valid) continue;
    const occ = new Set(cells.map(([dr,dc]) => (r+dr)+','+(col+dc)));
    let supported = false;
    for (const [dr,dc] of cells){
      const rr = r+dr+1, cc = col+dc;
      if (rr >= H){ supported = true; break; }
      if (!occ.has(rr+','+cc) && b[rr][cc]){ supported = true; break; }
    }
    if (supported) return r;
  }
  return null;
}

function place(b, cells, col){
  const r = landingRow(b, cells, col);
  if (r === null) return null;
  const nb = b.map(row => row.slice());
  for (const [dr,dc] of cells) nb[r+dr][col+dc] = 1;
  return nb;
}

// How many of the two bottom rows are completely full.
function clearedBottom2(b){
  let n = 0;
  for (const r of [H-1, H-2]) if (b[r].every(x => x)) n++;
  return n;
}

function setStatus(t, cls){ const s = document.getElementById('status'); s.textContent = t; s.className = 'status ' + cls; }

function curCells(){ return SEQUENCE[idx]; }

function render(){
  const well = document.getElementById('well');
  well.innerHTML = '';
  // ghost: where the current piece would land
  const ghost = new Set();
  if (idx < SEQUENCE.length){
    const r = landingRow(board, curCells(), curCol);
    if (r !== null) for (const [dr,dc] of curCells()) ghost.add((r+dr)+','+(curCol+dc));
  }
  for (let r = 0; r < H; r++) for (let c = 0; c < W; c++){
    const d = document.createElement('div');
    let cls = 'c';
    if (board[r][c]) cls += ' fill';
    else if (ghost.has(r+','+c)) cls += ' cur';
    d.className = cls;
    well.appendChild(d);
  }
  // queue preview
  const q = document.getElementById('queue'); q.innerHTML = '';
  for (let i = idx; i < SEQUENCE.length; i++){
    const m = document.createElement('div'); m.className = 'mini';
    const set = new Set(SEQUENCE[i].map(([dr,dc]) => dr+','+dc));
    for (let r = 0; r < 2; r++) for (let c = 0; c < 2; c++){
      const cell = document.createElement('div');
      cell.className = 'm' + (set.has(r+','+c) ? ' on' : '');
      m.appendChild(cell);
    }
    q.appendChild(m);
  }
  document.getElementById('score').textContent = clearedBottom2(board);
  const done = idx >= SEQUENCE.length;
  document.getElementById('left').disabled = done;
  document.getElementById('right').disabled = done;
  document.getElementById('drop').disabled = done;
}

function clampCol(){
  const maxCol = W - 1 - widthOf(curCells());
  if (curCol < 0) curCol = 0;
  if (curCol > maxCol) curCol = maxCol;
}

function dropCurrent(){
  if (idx >= SEQUENCE.length) return;
  const nb = place(board, curCells(), curCol);
  if (nb === null){ setStatus('That column has no room — slide over.', 'bad'); return; }
  board = nb; idx++; curCol = 0;
  finishIfDone();
  render();
}

function finishIfDone(){
  if (idx < SEQUENCE.length) return;
  const cleared = clearedBottom2(board);
  if (cleared === 2) setStatus('Both rows cleared — perfect packing!', 'ok');
  else setStatus(fmt('Cleared %cleared% of 2. Reset and try the other arrangement.', { cleared: cleared }), 'bad');
}

// Naive strategy: each piece drops into the leftmost legal column.
function autoNaive(){
  reset();
  for (let i = 0; i < SEQUENCE.length; i++){
    let c = 0; while (c < W && place(board, SEQUENCE[i], c) === null) c++;
    const nb = place(board, SEQUENCE[i], c);
    if (nb) board = nb;
    idx++;
  }
  curCol = 0;
  setStatus(fmt('Naive: each piece in the leftmost gap → cleared %clearedBottom2% of 2.', { clearedBottom2: clearedBottom2(board) }), clearedBottom2(board) === 2 ? 'ok' : 'bad');
  render();
}

// Smart strategy: brute-force search over (column for each piece) and keep the
// arrangement clearing the most rows. This is the search that blows up in general.
function autoSmart(){
  reset();
  let best = null, bestScore = -1;
  const cols = [];
  function rec(b, i){
    if (i === SEQUENCE.length){
      const s = clearedBottom2(b);
      if (s > bestScore){ bestScore = s; best = cols.slice(); }
      return;
    }
    for (let c = 0; c <= W - 1 - widthOf(SEQUENCE[i]); c++){
      const nb = place(b, SEQUENCE[i], c);
      if (nb){ cols.push(c); rec(nb, i+1); cols.pop(); }
    }
  }
  rec(board, 0);
  if (best){
    for (let i = 0; i < SEQUENCE.length; i++){ board = place(board, SEQUENCE[i], best[i]); idx++; }
  }
  curCol = 0;
  setStatus(fmt('Smart: searched all placements → cleared %clearedBottom2% of 2.', { clearedBottom2: clearedBottom2(board) }), clearedBottom2(board) === 2 ? 'ok' : 'bad');
  render();
}

document.getElementById('left').addEventListener('click', () => { curCol--; clampCol(); render(); });
document.getElementById('right').addEventListener('click', () => { curCol++; clampCol(); render(); });
document.getElementById('drop').addEventListener('click', dropCurrent);
document.getElementById('naive').addEventListener('click', autoNaive);
document.getElementById('smart').addEventListener('click', autoSmart);
document.getElementById('reset').addEventListener('click', reset);
reset();
Result
Console

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.

The Real Complexity

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.

Where It Matters

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

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/tetris/Content licensed under CC BY-NC 4.0.