Introduction

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.

Deduce the Mines

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">The numbers are clues: each says how many mines touch it (including diagonals). Click the gray cells to place mines so that <b>every</b> number is satisfied. Checking a board is instant — finding a valid layout is the hard part.</p>
<div id="board" class="board"></div>
<div class="status" id="status">Place mines, then check.</div>
<div class="btns">
  <button id="check" type="button">Check board</button>
  <button id="find" type="button">Find a valid layout</button>
  <button id="reset" type="button" class="ghost">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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Minesweeper "consistency": given the clue numbers, is there a placement of
// mines on the covered (gray) cells so that every clue equals the count of
// mines around it? Checking one layout is a quick scan; finding one in general
// is NP-complete (Kaye, 2000) — brute force tries 2^(covered cells).
const N = 5;
// The 5 covered candidate cells (row,col). The intended solution marks 3 of them.
const CAND = [[1,1],[1,3],[2,2],[3,2],[3,3]];
const SOLUTION = new Set(['1,1','1,3','3,2']); // mines; (2,2) and (3,3) are safe
const candKey = (r,c) => r + ',' + c;
const isCand = (r,c) => CAND.some(([a,b]) => a===r && b===c);

// Clue value for every non-candidate cell = mines (from SOLUTION) in its 8-neighborhood.
function neighbors(r,c){ const o=[]; for(let dr=-1;dr<=1;dr++)for(let dc=-1;dc<=1;dc++){
  if(!dr&&!dc)continue; const nr=r+dr,nc=c+dc; if(nr>=0&&nr<N&&nc>=0&&nc<N)o.push([nr,nc]); } return o; }
const CLUE = {};
for(let r=0;r<N;r++)for(let c=0;c<N;c++) if(!isCand(r,c))
  CLUE[candKey(r,c)] = neighbors(r,c).filter(([a,b])=>SOLUTION.has(candKey(a,b))).length;

const placed = new Set(); // player's mines

function render(){
  const b = document.getElementById('board'); b.innerHTML='';
  for(let r=0;r<N;r++)for(let c=0;c<N;c++){
    const d=document.createElement('div'); const k=candKey(r,c);
    if(isCand(r,c)){
      d.className='cell cand'+(placed.has(k)?' mine':'');
      d.addEventListener('click',()=>{ placed.has(k)?placed.delete(k):placed.add(k); render(); setStatus('Place mines, then check.',''); });
    } else {
      const v=CLUE[k]; d.className='cell clue'+(v===0?' zero':''); d.textContent=v;
    }
    b.appendChild(d);
  }
}
function setStatus(t,cls){ const s=document.getElementById('status'); s.textContent=t; s.className='status '+cls; }

// A layout is valid iff every clue equals the mines around it.
function valid(mines){
  for(const k in CLUE){ const [r,c]=k.split(',').map(Number);
    const cnt=neighbors(r,c).filter(([a,b])=>mines.has(candKey(a,b))).length;
    if(cnt!==CLUE[k]) return false; }
  return true;
}
function check(){
  if(valid(placed)) setStatus('✓ Every clue is satisfied — valid layout!','ok');
  else setStatus('✗ Some clue is wrong. Keep deducing.','bad');
}
function find(){
  let steps=0, sol=null;
  for(let mask=0; mask<(1<<CAND.length); mask++){ steps++;
    const m=new Set(); CAND.forEach(([r,c],i)=>{ if(mask&(1<<i)) m.add(candKey(r,c)); });
    if(valid(m)){ sol=m; break; } }
  if(sol){ placed.clear(); sol.forEach(k=>placed.add(k)); render();
    setStatus(fmt('Found a valid layout after checking %steps% of %v%.', { steps: steps, v: 1<<CAND.length }),'ok');
    console.log('Solution mines:', [...sol].join(' '), '| checked', steps, 'layouts'); }
  else setStatus('No layout satisfies these clues.','bad');
}
document.getElementById('check').addEventListener('click',check);
document.getElementById('find').addEventListener('click',find);
document.getElementById('reset').addEventListener('click',()=>{ placed.clear(); render(); setStatus('Place mines, then check.',''); });
render();
Result
Console

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.

The Real Complexity

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 — 2n2^{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.

Where It Matters

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

Conclusion

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.

Share this article

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

Comments

Loading comments...

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