Algorithms & EmergenceComputational Complexity

Your Favorite Games Are Mathematically Hard

Tetris and Minesweeper are as hard as the hardest quick-to-check puzzles

You've stared at a Minesweeper board with no safe move left. Was it your fault, or is the game itself working against you?

You'll find out

  • Why some boards force a pure guess
  • Where Tetris meets a famous open problem
  • Why no strategy wins every game

Why it matters

The hardness that keeps your favorite puzzles fun is the same that stumps the world's fastest computers.

About 3 min6 interactive slides · 5 questionsLesson 716 · Zone 80

Play this lesson

Free to play in your browser or on iPhone

More in this zone

  1. 712AI in ScienceAI Beats the Weather SupercomputersA model trained on decades of weather now forecasts in a minute
  2. 713BlockchainFrom Mining to StakingEthereum cut its energy use by more than 99% in a single day
  3. 714High-Energy PhysicsCherenkov's Blue GlowParticles can outrun light inside water and leave a blue glow
  4. 715Philosophy of AIThe Chinese RoomCan a system understand without understanding anything?
  5. 717Post-Quantum SecurityThe Quantum ThreatA future computer could pick today's digital locks
  6. 718Graph TheoryFour Colors Are EnoughAny map of one-piece countries can be colored with four colors, but proving it took a century
  7. 719Computer-Assisted ProofsThe Proof Too Large to CheckThe four-color proof needed a computer, and mathematicians argued about it
  8. 720Surface PhysicsCold Welding in SpaceClean metals can fuse on contact when there's no air between them