Introduction

Pick up any Sudoku book and you will see puzzles with 22, 25, or 30 given digits. But the mathematically interesting question is not how many clues make a puzzle comfortable — it is how few clues can force a unique solution.

For years, puzzle enthusiasts knew that 17-clue puzzles exist and that nobody had ever constructed a valid 16-clue puzzle. But "nobody found one" is very different from "none can exist." The question was open for decades.

In 2012, computer scientist Gary McGuire together with Bastian Tugemann and Gilles Civario settled it once and for all. After more than a year of computation on a high-performance cluster — checking all essentially different Sudoku solution grids and showing that none can be reduced to 16 clues while retaining a unique solution — they proved that 17 is the irreducible minimum.

The proof is a landmark in computational mathematics: not a clever argument, but a proof by exhaustive search so large it required months on a supercomputer.

Try It: A Real 17-Clue Puzzle

Below is a genuine 17-clue Sudoku from McGuire's verified catalogue. The 17 given digits are shown in blue — the rest of the 9×99 \times 9 grid is blank. Fill in the empty cells yourself, or press Solve to watch a backtracking solver complete it step by step.

<!-- Sudoku demo — 17-clue puzzle from McGuire et al. (2012) / Gordon Royle list -->
<p class="hint">This is a genuine 17-clue Sudoku from McGuire's verified catalogue (Royle puzzle #1). The blue cells are the 17 given digits — they uniquely determine the entire grid. Click <b>Solve</b> to animate the backtracking solver, or <b>Step</b> to advance one move at a time.</p>
<div id="grid-wrap">
  <table id="sudoku" aria-label="Sudoku grid — 17 clues given in blue"></table>
</div>
<div class="status" id="status"></div>
<div class="btns">
  <button id="btn-solve" type="button">Solve</button>
  <button id="btn-step" type="button">Step</button>
  <button id="btn-reset" type="button" class="ghost">Reset</button>
</div>

/* Base reset and typography */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; padding: .5rem; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
#grid-wrap { overflow-x: auto; }
#sudoku { border-collapse: collapse; margin: 0 auto .6rem; }
#sudoku td {
  width: 36px; height: 36px; text-align: center; vertical-align: middle;
  font: 700 16px ui-monospace, monospace; border: 1px solid #bcc4cc;
  user-select: none;
}
/* Bold borders around each 3x3 box */
#sudoku td:nth-child(3n) { border-right: 2.5px solid #5a7088; }
#sudoku tr:nth-child(3n) td { border-bottom: 2.5px solid #5a7088; }
#sudoku { border: 2.5px solid #5a7088; }
/* Cell colour coding — given (blue), solver-filled (green), empty (grey) */
.cell-given { background: #dde8f4; color: #1d3557; }
.cell-empty { background: #f5f7f9; color: #333; }
.cell-filled { background: #eafbf0; color: #0a7d33; }
/* Status line styling */
.status { font-size: .95rem; font-weight: 600; min-height: 1.5em; margin: .4rem 0; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.status.info { color: #1d3557; }
/* Button row styling */
.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; }
button:disabled { opacity: .45; cursor: not-allowed; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// A genuine 17-clue Sudoku from Gordon Royle's archive, verified by McGuire, Tugemann and Civario (2012).
// Row-major order. 0 = empty cell. Exactly 17 non-zero entries give a unique solution.
// 0 = empty; non-zero = given clue digit.
const GIVEN = [
  [0,0,0, 0,0,0, 0,1,0],
  [4,0,0, 0,0,0, 0,0,0],
  [0,2,0, 0,0,0, 0,0,0],
  [0,0,0, 0,5,0, 4,0,7],
  [0,0,8, 0,0,0, 3,0,0],
  [0,0,1, 0,9,0, 0,0,0],
  [3,0,0, 4,0,0, 2,0,0],
  [0,5,0, 1,0,0, 0,0,0],
  [0,0,0, 8,0,6, 0,0,0]
];

// Ordered list of all empty cells — the backtracking solver fills them in this order.
const BLANKS = [];
for (let r = 0; r < 9; r++)
  for (let c = 0; c < 9; c++)
    if (!GIVEN[r][c]) BLANKS.push([r, c]);

// Mutable working copy of the board updated by the solver.
let board = GIVEN.map(r => r.slice());

// Iterative backtracking state: idx = current blank index; choices[i] = last digit tried at blank i.
// idx = current position in BLANKS; choices[i] = last digit tried at blank i.
let idx = 0;
let choices = new Array(BLANKS.length).fill(0);
let solverReady = false;
let running = false;

// Return true iff digit d can go at (r,c) without conflicting in row, column or 3x3 box.
function canPlace(bd, r, c, d) {
  for (let i = 0; i < 9; i++) {
    if (bd[r][i] === d || bd[i][c] === d) return false;
  }
  const br = Math.floor(r / 3) * 3;
  const bc = Math.floor(c / 3) * 3;
  for (let dr = 0; dr < 3; dr++)
    for (let dc = 0; dc < 3; dc++)
      if (bd[br + dr][bc + dc] === d) return false;
  return true;
}

// Redraw the entire grid from the current board state.
function render() {
  const tbl = document.getElementById('sudoku');
  tbl.innerHTML = '';
  for (let r = 0; r < 9; r++) {
    const tr = document.createElement('tr');
    for (let c = 0; c < 9; c++) {
      const td = document.createElement('td');
      const v = board[r][c];
      if (GIVEN[r][c]) {
        td.className = 'cell-given';
        td.textContent = String(v);
      } else if (v === 0) {
        td.className = 'cell-empty';
      } else {
        td.className = 'cell-filled';
        td.textContent = String(v);
      }
      tr.appendChild(td);
    }
    tbl.appendChild(tr);
  }
}

function setStatus(t, cls) {
  const s = document.getElementById('status');
  s.textContent = t;
  s.className = 'status ' + cls;
}

// Initialise (or reset) the backtracking solver to the puzzle's starting position.
// Reset the backtracking solver to the puzzle's starting state.
function initSolver() {
  board = GIVEN.map(r => r.slice());
  idx = 0;
  choices.fill(0);
  solverReady = true;
}

// Core backtracking step with no side effects — returns 'solved', 'unsolvable', or 'continue'.
// Advance one iteration of backtracking. Returns 'solved', 'unsolvable', or 'continue'.
function rawStep() {
  if (idx >= BLANKS.length) return 'solved'; // Solver has already finished — nothing to do.
  const [r, c] = BLANKS[idx];
  let d = choices[idx] + 1;
  // Try the next digit after the last one attempted at this cell.
  while (d <= 9 && !canPlace(board, r, c, d)) d++;
  if (d <= 9) {
    // Digit fits — place it and advance to the next blank.
    board[r][c] = d;
    choices[idx] = d;
    idx++;
    if (idx === BLANKS.length) return 'solved'; // All blanks filled with no conflicts — puzzle is solved.
  } else {
    // No digit fits at this cell — erase it and backtrack one level.
    board[r][c] = 0;
    choices[idx] = 0;
    idx--;
    if (idx < 0) return 'unsolvable';
    // Also erase the previous cell so the outer loop can retry from the next digit.
    const [pr, pc] = BLANKS[idx];
    board[pr][pc] = 0;
  }
  return 'continue';
}

// One user-visible step: run rawStep and update the display.
// One user-visible step: run rawStep and update display.
function step() {
  if (!solverReady) initSolver();
  const result = rawStep();
  if (result === 'solved') {
    render();
    setStatus(i18nFmt('Solved in %filled% placements — unique solution confirmed!', { filled: BLANKS.length }), 'ok');
    stop();
  } else if (result === 'unsolvable') {
    render();
    setStatus('No solution — the puzzle has no valid completion.', 'bad');
    stop();
  } else {
    render();
    setStatus(i18nFmt('Backtracking… %filled% of %total% cells placed.', { filled: idx, total: BLANKS.length }), 'info');
  }
}

function stop() {
  running = false;
  document.getElementById('btn-solve').disabled = false;
  document.getElementById('btn-step').disabled = false;
}

// Run many iterations per rAF frame for smooth animation.
// Run many iterations per rAF frame, rendering once per frame for smooth animation.
const STEPS_PER_FRAME = 500000;
function tick() {
  if (!running) return;
  let result = 'continue';
  for (let i = 0; i < STEPS_PER_FRAME && result === 'continue'; i++) {
    result = rawStep();
  }
  render();
  if (result === 'solved') {
    setStatus(i18nFmt('Solved in %filled% placements — unique solution confirmed!', { filled: BLANKS.length }), 'ok');
    stop();
  } else if (result === 'unsolvable') {
    setStatus('No solution — the puzzle has no valid completion.', 'bad');
    stop();
  } else {
    setStatus(i18nFmt('Backtracking… %filled% of %total% cells placed.', { filled: idx, total: BLANKS.length }), 'info');
    requestAnimationFrame(tick);
  }
}

document.getElementById('btn-solve').addEventListener('click', () => {
  if (running) return;
  initSolver();
  render();
  running = true;
  document.getElementById('btn-solve').disabled = true;
  document.getElementById('btn-step').disabled = true;
  requestAnimationFrame(tick);
});

document.getElementById('btn-step').addEventListener('click', () => {
  if (running) return;
  if (!solverReady) initSolver();
  step();
});

document.getElementById('btn-reset').addEventListener('click', () => {
  stop(); // Stop any running animation and reset to the initial puzzle state.
  solverReady = false;
  board = GIVEN.map(r => r.slice());
  render();
  setStatus('Press Solve to animate, or Step to go one move at a time.', 'info');
});

render();
setStatus('Press Solve to animate, or Step to go one move at a time.', 'info');
Result
Console

Notice that every empty cell has exactly one digit that fits given the 17 clues. Remove any single clue and the puzzle becomes ambiguous — multiple solutions appear. That fragility is the whole point: 17 is not just sufficient, it is the minimum that still enforces uniqueness.

The Real Complexity

Why did the proof take so long? The raw scale of Sudoku is staggering.

  • Solution grids. There are exactly 6,670,903,752,021,072,936,9606{,}670{,}903{,}752{,}021{,}072{,}936{,}960 completed 9×99 \times 9 Sudoku grids. After accounting for symmetries the number of essentially different grids is still about 5.5×1095.5 \times 10^9.
  • The algorithm. McGuire's team designed a hitting-set method: for each essentially different solution grid GG, they proved that every 16-cell subset of GG fails to rule out at least one other valid completion. This required testing enormous numbers of subsets for every grid.
  • Solving is NP-complete. Generalised n2×n2n^2 \times n^2 Sudoku (deciding whether a partially filled grid has any completion) is NP-complete — the same class as SAT. For the standard 9×99 \times 9 case the grid is fixed, but solvers still use backtracking search that can branch 9819^{81} ways in the worst case.
  • The computation. The proof ran for over a year of CPU time on a cluster, completing in roughly seven months of wall-clock time. Independent verification by other researchers later confirmed the result.

The lesson is that some mathematical truths are not discovered by insight but by exhaustion — and the boundary between "no one found one" and "none exist" can cost millions of processor-hours to cross.

Where It Matters

The question "what is the minimum information that forces a unique solution?" appears across computer science and mathematics:

  • Constraint satisfaction. Sudoku is a classic constraint satisfaction problem (CSP). The 17-clue result is a sharp statement about the minimum necessary constraints to make a CSP uniquely solvable — a question that arises in scheduling, planning and configuration.
  • Puzzle design. Every well-formed Sudoku puzzle you buy has been checked for uniqueness. The 17-clue theorem sets the hard lower bound below which puzzle designers cannot go, shaping the entire puzzle industry.
  • Error-correcting codes. Redundancy in codes serves the same role as extra clues in Sudoku: enough redundancy forces unique decoding. Minimum-clue results parallel minimum-distance theorems in coding theory.
  • Exhaustive-search proofs. The proof method itself — computer-assisted exhaustive verification — is increasingly common in mathematics. Famous examples include the four-colour theorem (1976) and Kepler's sphere-packing conjecture (2005). The 17-clue proof belongs to this family.

Whenever you need to know not just whether a solution exists but how little information forces uniqueness, you are in the territory this proof mapped.

Conclusion

Seventeen is a small number with a very hard proof behind it. The fact that no 16-clue Sudoku can have a unique solution is not obvious — it resisted every human attempt for decades and only yielded to months of supercomputer search.

That gap between "intuition says so" and "we can prove it" is exactly where computational mathematics lives. Sometimes the only way to cross that gap is to check every case, one by one, even when the cases number in the billions.

The next time you sit down with a Sudoku, the given digits are not arbitrary — they are carrying the minimum load needed to make the puzzle have exactly one answer. Pull out even one, and the uniqueness guarantee, tested by a supercomputer across 5.5×1095.5 \times 10^9 grids, can silently collapse.

Share this article

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

Comments

Loading comments...

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