Sudoku

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.

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">{{hint}}</p>
<div id="grid" class="grid"></div>
<div class="status" id="status">{{fill_prompt}}</div>
<div class="btns">
  <button id="check" type="button">{{btn_check}}</button>
  <button id="solve" type="button">{{btn_solve}}</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; }
.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; }
/* {{c_thick_lines}} */
.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; }

// Code not found

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.

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 $n^{2}$×$n^{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.

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

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.