Minesweeper

For decades, Minesweeper shipped with Windows and quietly ate millions of work hours. The rules are tiny: behind a grid sit hidden mines, and every number you uncover tells you how many mines touch that square. Read the clues, flag the mines, never click one.

Most of the time you play by instinct. But every move is really a piece of logic: from the numbers alone, which covered squares must be mines, which must be safe — and when are you simply forced to guess?

That little gap between "the clues force it" and "you have to guess" is not a quirk of the game. It is the same line that separates the easy problems from the hardest ones in all of computer science.

Here is a small board with the mines hidden. Every number is a clue — it counts the mines in the eight squares around it. Click the gray cells to place mines until every clue is satisfied.

<p class="hint">{{hint_para}}</p>
<div id="board" class="board"></div>
<div class="status" id="status">{{place_hint}}</div>
<div class="btns">
  <button id="check" type="button">{{btn_check}}</button>
  <button id="find" type="button">{{btn_find}}</button>
  <button id="reset" type="button" class="ghost">{{btn_clear}}</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; }
.board { display: grid; grid-template-columns: repeat(5, 46px); gap: 4px; margin: .4rem 0; }
.cell { width: 46px; height: 46px; display: flex; align-items: center; justify-content: center;
        font: 700 18px ui-monospace, monospace; border-radius: 8px; user-select: none; }
.clue { background: #e8eef3; color: #1d3557; border: 1px solid #cdd9e3; }
.clue.zero { color: transparent; }
.cand { background: #c9ccd1; border: 1px solid #adb1b8; cursor: pointer; transition: all .1s; }
.cand:hover { background: #bcc0c6; }
.cand.mine { background: #e63946; border-color: #c92f3c; color: #fff; }
.cand.mine::after { content: "✹"; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
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; }

// Code not found

Notice the asymmetry. Checking a finished board is effortless: walk over each number and count its neighbors. Finding a layout that satisfies all the clues at once is the hard part — press Find a valid layout and the computer simply tries every combination of mines. With five covered cells that's 32 possibilities; add more covered cells and the count doubles each time.

How hard is Minesweeper, really? Not the playing — the reasoning.

• Checking a candidate board is trivial: confirm each clue equals the mines around it.
• Brute force tries every way to place mines on the covered cells — $2^{n}$ layouts, hopeless once there are more than a few dozen unknowns.
• It's NP-complete. In 2000 the mathematician Richard Kaye showed that the consistency question — "is there any mine layout that fits these numbers?" — is as hard as any problem in NP. He did it by building wires, AND, OR and NOT gates entirely out of Minesweeper clues, turning any SAT formula into a board.
• So deciding even is-this-board-possible is equivalent to the whole NP-complete family — and figuring out whether a particular square is guaranteed safe is just as hard.

That is the punchline: the moment a position can't be settled by quick local logic, you are staring at a genuine instance of the same problem behind P vs NP. The guesses Minesweeper forces on you are not bad luck — they are intractability made playable.

"Satisfy all these local constraints at once" is one of the most common shapes a real problem can take, and Minesweeper is its friendly face:

• Logic and SAT solving: the gate-building trick is how researchers prove a problem is hard, and SAT solvers attack the same constraints in the real world.
• Hardware verification: checking that a circuit can never reach a forbidden state is a giant consistency question.
• Scheduling and configuration: timetables, seating and product options are all "find an assignment that breaks no rule."
• Teaching complexity: because everyone has played it, Minesweeper is one of the clearest on-ramps to what NP-completeness even means.

Learn why Minesweeper is hard and you've met constraint satisfaction — the engine under SAT, graph coloring and countless scheduling problems.

Minesweeper hides a beautiful secret: the same numbers that taught you to flag mines can be wired into logic gates, and through them into any problem in NP. Checking a board stays instant; deciding whether a board is even possible is as hard as anything in computer science.

So the next time the grid leaves you with a 50/50 and no safe click, take comfort — you haven't played badly. You've simply run into P vs NP hiding behind a smiley face, and there may be no clever way around the guess at all.