37. Sudoku Solver

Fill a partially-completed 9×9 Sudoku so every row, column, and 3×3 box holds the digits 1–9 exactly once. Walk to the first blank, try each legal digit using row / col / box used-sets for O(1) checks, recurse, and undo on failure.

● HardBacktrackingConstraint PropagationTypeScript

PROBLEM What we're solving

Given a 9×9 grid of characters (digits 1–9 for givens, '.' for blanks), fill every blank so each row, each column, and each of the nine 3×3 sub-boxes contains 1–9 with no repeats. Mutate the board in place.

Concrete example. The cell at row 0, col 2 is blank. Its row already holds 5,3; its column holds 8,1,9,...; its box holds 5,3,6,7,1,9,8. The only digit absent from all three is 4, so that cell must be 4.

before          after
5 3 .           5 3 4
6 . . 1 9 5     6 7 2 1 9 5
. 9 8 . . .     1 9 8 3 4 2

KEY IDEA Backtracking over blanks, O(1) legality via used-sets

Insight → A Sudoku is just N-Queens with three constraints instead of two. Walk to the first empty cell, try each digit 1–9 that is legal, recurse, and undo if the branch dead-ends. Legality is “not already in this row, column, or 3×3 box.” Keep one Setper row, per column, and per box so that check — and its undo — is O(1), no scanning. The box a cell belongs to is ⌊r/3⌋·3 + ⌊c/3⌋.

RECIPE Seed sets, fill first blank, recurse, undo

0 · Build used-sets. Nine rows[], nine cols[], nine boxes[] sets. Scan the givens once and add each digit to its row / col / box set.
1 · Find the first blank. Scan row-major for the first '.'. If none exists, every cell is filled — the puzzle is solved, return true.
2 · Try each digit. For d in 1–9, skip it if rows[r], cols[c], or boxes[b] already contains it.
3 · Place. Write the digit into the cell and add it to all three sets.
4 · Recurse. Call backtrack(). If it returns true, a full solution was found below — propagate true straight up; stop trying digits.
5 · Undo. If the recursion failed, reset the cell to '.' and delete the digit from the three sets, then try the next digit. If none of 1–9 works, return false— a dead end the caller must back out of.

Classic confusion → the box-index formula is ⌊r/3⌋·3 + ⌊c/3⌋, NOT r/3 + c/3 or r·3+c. For row 4, col 7 it gives 1·3 + 2 = 5 — box 5. The ·3 lays the boxes out in row-major order across the grid.

COST Complexity & alternatives

Rescan row/col/box per candidate

O(9^m·9)

Each legality test costs O(9) scanning the line and box.

Backtracking + used-sets

O(9^m)

O(1) legality & undo; m = number of empty cells.

Worst case is exponential in m, the count of blanks: up to nine choices per blank. But constraint pruning (only legal digits are tried) and the order of filling collapse the real search tree to something tiny for typical puzzles. Auxiliary space is O(1) — 27 fixed-size sets and O(m) recursion depth on a fixed 81-cell board.

Pattern transfer → identical place / recurse / undo machinery powers N-Queens (col + two diagonal sets), Valid Sudoku (the same used-sets but a single validation pass, no recursion), Word Search(grid DFS with a visited set), and any “fill cells under mutual-exclusion constraints” puzzle.

RUN IT Fill the first blank with the lowest legal digit, recurse, undo on failure

board =

step 0 / 51

STARTSeed row/col/box used-sets from the 6givens' neighbours, then fill the first empty cell with the lowest legal digit.

1function solveSudoku(board: string[][]): void {
2▶  const rows = Array.from({ length: 9 }, () => new Set<string>());
3▶  const cols = Array.from({ length: 9 }, () => new Set<string>());
4▶  const boxes = Array.from({ length: 9 }, () => new Set<string>());
5▶  const boxId = (r: number, c: number) => Math.floor(r / 3) * 3 + Math.floor(c / 3);
6 
7  // Seed the used-sets from the givens.
8  for (let r = 0; r < 9; r++) {
9    for (let c = 0; c < 9; c++) {
10      const v = board[r][c];
11      if (v !== '.') {
12        rows[r].add(v); cols[c].add(v); boxes[boxId(r, c)].add(v);
13      }
14    }
15  }
16 
17  function backtrack(): boolean {
18    // Find the first empty cell.
19    for (let r = 0; r < 9; r++) {
20      for (let c = 0; c < 9; c++) {
21        if (board[r][c] !== '.') continue;
22        const b = boxId(r, c);
23        for (let d = 1; d <= 9; d++) {
24          const v = String(d);
25          if (rows[r].has(v) || cols[c].has(v) || boxes[b].has(v)) continue;
26          // Place
27          board[r][c] = v;
28          rows[r].add(v); cols[c].add(v); boxes[b].add(v);
29 
30          if (backtrack()) return true;
31 
32          // Undo
33          board[r][c] = '.';
34          rows[r].delete(v); cols[c].delete(v); boxes[b].delete(v);
35        }
36        return false; // no digit fits — dead end
37      }
38    }
39    return true; // no empty cell left — solved
40  }
41 
42  backtrack();
43}

State

empty left: 6

placements: 0

backtracks: 0

Current empty cellDigit placed by solverConflict / backtrackGiven clue

slowfast

TYPESCRIPT The solution, annotated

solveSudoku.ts
function solveSudoku(board: string[][]): void {
  const rows  = Array.from({ length: 9 }, () => new Set<string>());
  const cols  = Array.from({ length: 9 }, () => new Set<string>());
  const boxes = Array.from({ length: 9 }, () => new Set<string>());
  const boxId = (r: number, c: number) => Math.floor(r / 3) * 3 + Math.floor(c / 3);

  // Seed the used-sets from the givens so legality checks are O(1).
  for (let r = 0; r < 9; r++) {
    for (let c = 0; c < 9; c++) {
      const v = board[r][c];
      if (v !== '.') {
        rows[r].add(v); cols[c].add(v); boxes[boxId(r, c)].add(v);
      }
    }
  }

  function backtrack(): boolean {
    for (let r = 0; r < 9; r++) {
      for (let c = 0; c < 9; c++) {
        if (board[r][c] !== '.') continue;   // skip filled cells
        const b = boxId(r, c);
        for (let d = 1; d <= 9; d++) {
          const v = String(d);
          if (rows[r].has(v) || cols[c].has(v) || boxes[b].has(v)) continue;
          // Place
          board[r][c] = v;
          rows[r].add(v); cols[c].add(v); boxes[b].add(v);

          if (backtrack()) return true;       // solved deeper — propagate up

          // Undo (backtrack)
          board[r][c] = '.';
          rows[r].delete(v); cols[c].delete(v); boxes[b].delete(v);
        }
        return false;   // no digit fit this empty cell — dead end
      }
    }
    return true;        // no empty cell remained — solved
  }

  backtrack();
}

Reading it block by block

Lines 2–5 — the used-set state. Nine sets each for rows, columns, and 3×3 boxes turn legality into an O(1) membership test instead of a scan. boxId maps any (r, c) to its box ⌊r/3⌋·3 + ⌊c/3⌋.

Lines 7–15 — seed from the givens. One pass over the board records every pre-filled digit into its row, column, and box set. After this, any candidate digit can be rejected in constant time.

Lines 18–22 — find the first blank. Scan row-major for the first '.'. Already-filled cells are skipped. Reaching the bottom with no blank means every cell is legal — return true (line 39).

Lines 23–30 — try, place, recurse. For each digit not already present in the row/col/box, write it and add it to the three sets, then recurse. A truefrom the recursive call means the rest of the board completed — propagate it upward and stop.

Lines 32–37 — undo and dead-end. If recursion failed, restore the cell to '.' and delete the digit from all three sets, then try the next one. If no digit 1–9 fits, return false— the caller must back out and revise an earlier choice.

Complexity → Time: O(9^m) worst case, where m is the number of empty cells (up to nine candidates each). Constraint pruning makes the realized tree far smaller. Space: O(1) for the 27 fixed-size sets plus O(m) recursion depth on the fixed 81-cell grid.

INTERVIEWFollow-ups they'll ask

“Why return a boolean from backtrack?” Sudoku needs exactly one solution, not all of them. Returning true on the first complete fill short-circuits every remaining branch instead of exhausting the tree like N-Queens does.
“How would you speed it up?” Use the most-constrained cell heuristic (MRV): instead of the first blank, pick the empty cell with the fewest legal candidates. That prunes dramatically on hard puzzles.
“Bitmask the sets?” Replace each Set with a 9-bit integer; candidates are ~(rows[r] | cols[c] | boxes[b]) & 0x1FF, and you isolate the lowest with x & -x.
“Generalize to N×N?” The box key becomes ⌊r/k⌋·k + ⌊c/k⌋ with k = √N, and digits run 1–N.
“Validate the input first?” A solver assumes valid givens; in an interview, run the Valid Sudoku check up front so a contradictory board fails fast rather than after a full fruitless search.

OPTIMAL Backtracking

solveSudoku.ts
function solveSudoku(board: string[][]): void {
  const rows  = Array.from({ length: 9 }, () => new Set<string>());
  const cols  = Array.from({ length: 9 }, () => new Set<string>());
  const boxes = Array.from({ length: 9 }, () => new Set<string>());
  const boxId = (r: number, c: number) => Math.floor(r / 3) * 3 + Math.floor(c / 3);

  // Seed the used-sets from the givens so legality checks are O(1).
  for (let r = 0; r < 9; r++) {
    for (let c = 0; c < 9; c++) {
      const v = board[r][c];
      if (v !== '.') {
        rows[r].add(v); cols[c].add(v); boxes[boxId(r, c)].add(v);
      }
    }
  }

  function backtrack(): boolean {
    for (let r = 0; r < 9; r++) {
      for (let c = 0; c < 9; c++) {
        if (board[r][c] !== '.') continue;   // skip filled cells
        const b = boxId(r, c);
        for (let d = 1; d <= 9; d++) {
          const v = String(d);
          if (rows[r].has(v) || cols[c].has(v) || boxes[b].has(v)) continue;
          // Place
          board[r][c] = v;
          rows[r].add(v); cols[c].add(v); boxes[b].add(v);

          if (backtrack()) return true;       // solved deeper — propagate up

          // Undo (backtrack)
          board[r][c] = '.';
          rows[r].delete(v); cols[c].delete(v); boxes[b].delete(v);
        }
        return false;   // no digit fit this empty cell — dead end
      }
    }
    return true;        // no empty cell remained — solved
  }

  backtrack();
}

ALT 1 Bitmask used-sets

Time O(9^m) · Space O(1)

Swap each Set for a 9-bit integer; candidates fall out of a single bitwise expression and the lowest is isolated with x & -x.

approach-2.ts
function solveSudoku(board: string[][]): void {
  const rows = new Array(9).fill(0);
  const cols = new Array(9).fill(0);
  const boxes = new Array(9).fill(0);
  const boxId = (r: number, c: number) => Math.floor(r / 3) * 3 + Math.floor(c / 3);

  for (let r = 0; r < 9; r++)
    for (let c = 0; c < 9; c++)
      if (board[r][c] !== '.') {
        const bit = 1 << (+board[r][c] - 1);
        rows[r] |= bit; cols[c] |= bit; boxes[boxId(r, c)] |= bit;
      }

  function backtrack(): boolean {
    for (let r = 0; r < 9; r++) {
      for (let c = 0; c < 9; c++) {
        if (board[r][c] !== '.') continue;
        const b = boxId(r, c);
        // Bits set here are digits still available for this cell.
        let avail = ~(rows[r] | cols[c] | boxes[b]) & 0x1ff;
        while (avail) {
          const bit = avail & -avail;        // lowest available digit
          avail ^= bit;
          const d = Math.log2(bit) + 1;
          board[r][c] = String(d);
          rows[r] |= bit; cols[c] |= bit; boxes[b] |= bit;
          if (backtrack()) return true;
          board[r][c] = '.';
          rows[r] &= ~bit; cols[c] &= ~bit; boxes[b] &= ~bit;
        }
        return false;
      }
    }
    return true;
  }

  backtrack();
}

Note → A 9-bit mask per row/col/box replaces the three Set objects; avail & -avail isolates the lowest legal digit in one instruction. Same backtracking shape, far less allocation and pointer chasing.

ALT 2 Most-Constrained-Variable (MRV) ordering

Time O(9^m) worst case · Space O(1)

Instead of the first blank, always fill the empty cell with the fewestlegal candidates — the heuristic that makes hard puzzles tractable.

approach-3.ts
function solveSudoku(board: string[][]): void {
  const rows = Array.from({ length: 9 }, () => new Set<string>());
  const cols = Array.from({ length: 9 }, () => new Set<string>());
  const boxes = Array.from({ length: 9 }, () => new Set<string>());
  const boxId = (r: number, c: number) => Math.floor(r / 3) * 3 + Math.floor(c / 3);

  for (let r = 0; r < 9; r++)
    for (let c = 0; c < 9; c++)
      if (board[r][c] !== '.') {
        const v = board[r][c];
        rows[r].add(v); cols[c].add(v); boxes[boxId(r, c)].add(v);
      }

  const candidates = (r: number, c: number): string[] => {
    const out: string[] = [];
    for (let d = 1; d <= 9; d++) {
      const v = String(d);
      if (!rows[r].has(v) && !cols[c].has(v) && !boxes[boxId(r, c)].has(v)) out.push(v);
    }
    return out;
  };

  function backtrack(): boolean {
    // Pick the empty cell with the fewest legal digits.
    let best: { r: number; c: number; opts: string[] } | null = null;
    for (let r = 0; r < 9; r++)
      for (let c = 0; c < 9; c++)
        if (board[r][c] === '.') {
          const opts = candidates(r, c);
          if (opts.length === 0) return false;          // dead end early
          if (!best || opts.length < best.opts.length) best = { r, c, opts };
        }
    if (!best) return true;                              // no blanks left

    const { r, c, opts } = best;
    const b = boxId(r, c);
    for (const v of opts) {
      board[r][c] = v;
      rows[r].add(v); cols[c].add(v); boxes[b].add(v);
      if (backtrack()) return true;
      board[r][c] = '.';
      rows[r].delete(v); cols[c].delete(v); boxes[b].delete(v);
    }
    return false;
  }

  backtrack();
}

Note → Scanning for the most-constrained cell costs O(81) per level but slashes the branching factor, so it dominates the naive first-blank order on tough puzzles. The detect-zero-candidates check also prunes contradictions immediately.

MNEMONIC The one-liner

"First blank, try 1-9 that fit, recurse, undo. Row/col/box sets make every check O(1); box = ⌊r/3⌋·3 + ⌊c/3⌋."

TRIGGERS When you see _ → reach for _

fill a grid under per-region uniqueness constraints	backtracking + row/col/box used-sets
each row/col/box must hold each symbol once	three Sets, O(1) legality + undo
need exactly ONE solution, not all	return boolean; propagate true to stop early
map a cell to its 3×3 block	⌊r/3⌋·3 + ⌊c/3⌋

SKELETON The reusable shape

skeleton.ts
const rows  = Array.from({length:9}, () => new Set<string>());
const cols  = Array.from({length:9}, () => new Set<string>());
const boxes = Array.from({length:9}, () => new Set<string>());
const boxId = (r,c) => Math.floor(r/3)*3 + Math.floor(c/3);
// seed sets from givens...

function backtrack(): boolean {
  // find first empty cell (r,c); if none -> return true
  for (let d = 1; d <= 9; d++) {
    const v = String(d);
    if (rows[r].has(v) || cols[c].has(v) || boxes[b].has(v)) continue;
    board[r][c] = v; rows[r].add(v); cols[c].add(v); boxes[b].add(v);
    if (backtrack()) return true;
    board[r][c] = '.'; rows[r].delete(v); cols[c].delete(v); boxes[b].delete(v);
  }
  return false; // dead end
}

FLASHCARDS Tap to flip

What three sets does the solver maintain, and why?

One Set per row, per column, and per 3×3box. They make the “is this digit legal here?” check and its undo O(1) instead of scanning.

tap to flip

1 / 8

Answer to reveal explanations. No penalty for retries.Score: 0 / 9

QUESTION 01

Which formula gives the 3×3 box index for cell (r, c)?

QUESTION 02

Why does backtrack() return a boolean here, whereas N-Queens returns void?

QUESTION 03

What is the undo (backtrack) step after a failed recursion?

QUESTION 04

When does backtrack() return false?

QUESTION 05

Worst-case time complexity, where m is the number of empty cells?

QUESTION 06

What is the purpose of the row/col/box Sets?

QUESTION 07

Which optimization most helps on hard puzzles?

QUESTION 08

#37 · Sudoku SolverFill a 9×9 Sudoku by backtracking: place a legal digit in the first empty cell (checked against row, column, and 3×3 box sets), recurse, and undo on failure. Used-sets make each legality test O(1).Which algorithmic approach does this primarily use?

QUESTION 09

PROBLEM What we're solving

KEY IDEA Backtracking over blanks, O(1) legality via used-sets

RECIPE Seed sets, fill first blank, recurse, undo

COST Complexity & alternatives

RUN IT Fill the first blank with the lowest legal digit, recurse, undo on failure

TYPESCRIPT The solution, annotated

Reading it block by block

INTERVIEWFollow-ups they'll ask

OPTIMAL Backtracking

ALT 1 Bitmask used-sets

ALT 2 Most-Constrained-Variable (MRV) ordering

MNEMONIC The one-liner

TRIGGERS When you see ___ → reach for ___

SKELETON The reusable shape

FLASHCARDS Tap to flip

TRIGGERS When you see _ → reach for _