Introduction

You've seen it on the back page of a newspaper or in a phone app: a 9×9 grid, some squares already filled, and one rule to obey. Every row, every column and every 3×3 box must contain the digits 1 through 9 exactly once.

It feels gentle — a few minutes of quiet logic. But notice the same split that runs through every hard problem: if someone hands you a finished grid, you can check it in seconds. Producing that grid from a sparse set of clues is a different kind of effort entirely.

And here's the twist: the 9×9 board is just the friendly tip. Grow Sudoku to larger sizes and solving it becomes NP-complete — as hard as anything in computer science.

Fill the Grid

Let's shrink it to a 4×4 so the idea fits in one glance: every row, column and 2×2 box must hold 1, 2, 3 and 4. Click a blank cell to cycle its number and try to complete the grid.

<p class="hint">A mini 4×4 Sudoku: every row, every column and every 2×2 box must contain 1, 2, 3 and 4 exactly once. Click a blank cell to cycle its number. Checking a grid is instant — searching for the solution is the hard part.</p>
<div id="grid" class="grid"></div>
<div class="status" id="status">Fill the blanks, then check.</div>
<div class="btns">
  <button id="check" type="button">Check</button>
  <button id="solve" type="button">Solve it</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; }
.grid { display: grid; grid-template-columns: repeat(4, 50px); gap: 0; width: max-content; margin: .4rem 0;
        border: 3px solid #1d3557; }
.cell { width: 50px; height: 50px; display: flex; align-items: center; justify-content: center;
        font: 700 22px ui-monospace, monospace; border: 1px solid #c8d2db; }
/* thick lines between the 2x2 boxes */
.cell.r0 { border-top: none; } .cell.r3 { border-bottom: none; }
.cell.c0 { border-left: none; } .cell.c3 { border-right: none; }
.cell.bx { border-right: 3px solid #1d3557; }
.cell.by { border-bottom: 3px solid #1d3557; }
.given { background: #e8eef3; color: #1d3557; }
.blank { background: #fff; color: #457b9d; cursor: pointer; }
.blank:hover { background: #f1f6fa; }
.cell.bad { background: #fde2e4; color: #c92f3c; }
.status { font-size: 1rem; font-weight: 600; margin: .6rem 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] ?? ''));
// 4x4 Sudoku. Verifying a grid is a quick scan of rows, columns and boxes.
// Solving means searching the tree of choices — backtracking here, but on a
// full 9x9 (or n x n) board this search is NP-complete.
const N = 4, B = 2;
// 0 = blank. Givens have a unique completion.
const PUZZLE = [
  [1,2,0,4],
  [0,4,1,0],
  [0,1,4,0],
  [4,0,0,1],
];
const grid = PUZZLE.map(r => r.slice());
const given = PUZZLE.map(r => r.map(v => v !== 0));

function boxOK(g){ // returns Set of "r,c" cells that violate a constraint
  const bad = new Set();
  const scan = (cells) => { const seen = {};
    cells.forEach(([r,c]) => { const v = g[r][c]; if(!v) return;
      if(seen[v]) { bad.add(r+','+c); bad.add(seen[v]); } else seen[v] = r+','+c; }); };
  for(let r=0;r<N;r++) scan([...Array(N)].map((_,c)=>[r,c]));
  for(let c=0;c<N;c++) scan([...Array(N)].map((_,r)=>[r,c]));
  for(let br=0;br<N;br+=B) for(let bc=0;bc<N;bc+=B){
    const cells=[]; for(let r=0;r<B;r++)for(let c=0;c<B;c++)cells.push([br+r,bc+c]); scan(cells); }
  return bad;
}
function render(bad){
  bad = bad || new Set();
  const el = document.getElementById('grid'); el.innerHTML='';
  for(let r=0;r<N;r++)for(let c=0;c<N;c++){
    const d=document.createElement('div');
    let cls='cell r'+r+' c'+c+(given[r][c]?' given':' blank');
    if(c===1) cls+=' bx'; if(r===1) cls+=' by';
    if(bad.has(r+','+c)) cls+=' bad';
    d.className=cls; d.textContent=grid[r][c]||'';
    if(!given[r][c]) d.addEventListener('click',()=>{ grid[r][c]=(grid[r][c]+1)%(N+1); render(); setStatus('Fill the blanks, then check.',''); });
    el.appendChild(d);
  }
}
function setStatus(t,cls){ const s=document.getElementById('status'); s.textContent=t; s.className='status '+cls; }
function check(){
  const bad=boxOK(grid); render(bad);
  const full=grid.every(row=>row.every(v=>v));
  if(bad.size) setStatus('✗ A number repeats in a row, column or box.','bad');
  else if(full) setStatus('✓ Solved! Every line and box holds 1–4.','ok');
  else setStatus('No conflicts yet — but not finished.','');
}
function solve(){
  let steps=0;
  const blanks=[]; for(let r=0;r<N;r++)for(let c=0;c<N;c++) if(!given[r][c]) blanks.push([r,c]);
  const ok=(r,c,v)=>{ for(let i=0;i<N;i++){ if(grid[r][i]===v||grid[i][c]===v) return false; }
    const br=r-r%B, bc=c-c%B; for(let i=0;i<B;i++)for(let j=0;j<B;j++) if(grid[br+i][bc+j]===v) return false; return true; };
  const bt=(k)=>{ if(k===blanks.length) return true; const [r,c]=blanks[k];
    for(let v=1;v<=N;v++){ steps++; if(ok(r,c,v)){ grid[r][c]=v; if(bt(k+1)) return true; grid[r][c]=0; } } return false; };
  blanks.forEach(([r,c])=>grid[r][c]=0);
  const found=bt(0); render();
  setStatus(found?(fmt('Solved by backtracking in %steps% tries.', { steps: steps })):'No solution.', found?'ok':'bad');
  console.log(found?(fmt('Solution found, %steps% placements tried', { steps: steps })):'unsolvable');
}
document.getElementById('check').addEventListener('click',check);
document.getElementById('solve').addEventListener('click',solve);
document.getElementById('reset').addEventListener('click',()=>{ for(let r=0;r<N;r++)for(let c=0;c<N;c++) if(!given[r][c]) grid[r][c]=0; render(); setStatus('Fill the blanks, then check.',''); });
render();
Result
Console

Checking is instant — a quick scan for any repeated digit. To solve, press the button and watch backtracking at work: it tries a number, moves on, and rewinds whenever it hits a contradiction. On 4×4 that's a handful of tries; on 9×9 a few hundred; but as the grid grows, the search tree explodes.

The Real Complexity

How hard is Sudoku, really?

  • Checking a finished grid is trivial: scan every row, column and box for a repeated digit.
  • Solving 9×9 is easy for a computer — the board is small, and constraint propagation plus backtracking cracks it in milliseconds. (The other famous fact: a valid 9×9 puzzle needs at least 17 given clues to have a unique solution.)
  • But generalized Sudoku is NP-complete. Yato and Seta proved in 2003 that solving an n2n^{2}×n2n^{2} grid is as hard as the whole NP family. The 9×9 you do at breakfast is simply too small to feel it.
  • It's a constraint puzzle in disguise. Sudoku is a special Latin square, and solving it is an instance of exact cover — the same shape Donald Knuth attacks with his elegant Dancing Links algorithm — closely related to graph coloring and SAT.

So Sudoku lives right on the boundary: trivial to verify, comfortable at 9×9, and a full member of the NP-complete family the moment it grows — another face of P vs NP.

Where It Matters

"Fill a grid so no rule is broken" is the heart of many real tasks, and Sudoku is the puzzle that makes it visible:

  • Scheduling and timetabling: assigning classes, shifts or exams so nothing clashes is the same no-repeats-in-a-line logic — see timetabling.
  • Experimental design: Latin squares (Sudoku's mathematical parents) lay out trials so each treatment appears once per row and column.
  • Solver technology: Sudoku is a favorite benchmark for constraint solvers, SAT solvers and exact-cover algorithms.
  • Error-correcting codes and combinatorics: the same balanced-arrangement math shows up far beyond puzzles.

Learn why Sudoku is hard and you've met constraint satisfaction and exact cover — the machinery behind scheduling, graph coloring and much more.

Conclusion

Sudoku is a small miracle of design: simple enough for a coffee break, yet a true member of the NP-complete family once you let the grid grow. Checking a solution is instant; finding one is a search that, in general, no one knows how to make fast.

That's why it belongs on KipuHub. The next time you pencil a number into a corner, you're doing by hand what solvers do by the million — walking the same tree of choices that sits at the heart of P vs NP.

Share this article

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

Comments

Loading comments...

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