Sudoku Solver

You are given a partly filled 9 × 9 Sudoku grid board. Each cell holds a one-character string: a digit "1" to "9", or "." for a blank cell.

Fill in every blank so that the finished grid obeys the Sudoku rules:

• each row contains every digit 1–9 exactly once,
• each column contains every digit 1–9 exactly once,
• each of the nine 3 × 3 boxes that tile the grid contains every digit 1–9 exactly once.

Modify board in place; your function does not need to return anything. Every test puzzle has exactly one solution, and the judge checks the board after your function finishes.

Example 1

Example 2

Example 3

Constraints

• board.length == 9 and board[i].length == 9
• board[i][j] is a digit "1"–"9" or "."
• The given digits do not break any rule, and the puzzle has exactly one solution.

Pattern Path · Backtracking · problem 126 of 169

Start simple

Fill blanks left to right with every digit and only check the whole grid at the end: up to 9^b grids for b blanks, which is hopeless for a real puzzle.

The key idea

Sudoku is a constraint search: pick a cell, commit to a digit, and see whether the rest can be finished. If not, undo that choice and try the next digit. This is backtracking, and it is guaranteed to find the solution because it implicitly tries every consistent completion.

Two ideas make it fast enough:

• Constant-time legality checks. Keep a set of used digits for every row, column and box (box index r // 3 * 3 + c // 3). Placing a digit adds it to three sets; undoing removes it. The legal digits for a cell are the ones in none of its three sets.
• Most constrained cell first. Before branching, choose the blank cell with the fewest legal digits. A cell with one option costs no branching at all, and a cell with zero options proves the current path is wrong right away instead of many levels deeper. This prunes the search tree dramatically compared with filling cells in reading order.

When no blanks remain, every placement was checked against all three rules, so the board is a valid solution. Since the puzzle's solution is unique, it is the one the judge expects.

Complexity

• Time: O(9<sup>b</sup>) in the worst case for b blanks, far less in practice with pruning
• Space: O(b) for the recursion and the blank list

Python

class Solution:
    def solveSudoku(self, board):
        rows = [set() for _ in range(9)]
        cols = [set() for _ in range(9)]
        boxes = [set() for _ in range(9)]
        empty = []
        for r in range(9):
            for c in range(9):
                d = board[r][c]
                if d == ".":
                    empty.append((r, c))
                else:
                    rows[r].add(d)
                    cols[c].add(d)
                    boxes[r // 3 * 3 + c // 3].add(d)

        def options(cell):
            r, c = cell
            used = rows[r] | cols[c] | boxes[r // 3 * 3 + c // 3]
            return [d for d in "123456789" if d not in used]

        def solve():
            if not empty:
                return True
            # Branch on the cell with the fewest legal digits: it fails fastest.
            best = min(range(len(empty)), key=lambda i: len(options(empty[i])))
            empty[best], empty[-1] = empty[-1], empty[best]
            r, c = cell = empty.pop()
            b = r // 3 * 3 + c // 3
            for d in options(cell):
                board[r][c] = d
                rows[r].add(d)
                cols[c].add(d)
                boxes[b].add(d)
                if solve():
                    return True
                rows[r].remove(d)
                cols[c].remove(d)
                boxes[b].remove(d)
            board[r][c] = "."  # undo and let the caller try its next digit
            empty.append(cell)
            return False

        solve()

JavaScript

var solveSudoku = function(board) {
  const rows = Array.from({ length: 9 }, () => new Set());
  const cols = Array.from({ length: 9 }, () => new Set());
  const boxes = Array.from({ length: 9 }, () => new Set());
  const boxOf = (r, c) => Math.floor(r / 3) * 3 + Math.floor(c / 3);
  const empty = [];
  for (let r = 0; r < 9; r++) {
    for (let c = 0; c < 9; c++) {
      const d = board[r][c];
      if (d === '.') {
        empty.push([r, c]);
      } else {
        rows[r].add(d);
        cols[c].add(d);
        boxes[boxOf(r, c)].add(d);
      }
    }
  }

  const options = ([r, c]) => {
    const result = [];
    for (const d of '123456789') {
      if (!rows[r].has(d) && !cols[c].has(d) && !boxes[boxOf(r, c)].has(d)) result.push(d);
    }
    return result;
  };

  const solve = () => {
    if (empty.length === 0) return true;
    // Branch on the cell with the fewest legal digits: it fails fastest.
    let best = 0;
    let bestCount = 10;
    for (let i = 0; i < empty.length; i++) {
      const count = options(empty[i]).length;
      if (count < bestCount) {
        best = i;
        bestCount = count;
      }
    }
    [empty[best], empty[empty.length - 1]] = [empty[empty.length - 1], empty[best]];
    const cell = empty.pop();
    const [r, c] = cell;
    const b = boxOf(r, c);
    for (const d of options(cell)) {
      board[r][c] = d;
      rows[r].add(d);
      cols[c].add(d);
      boxes[b].add(d);
      if (solve()) return true;
      rows[r].delete(d);
      cols[c].delete(d);
      boxes[b].delete(d);
    }
    board[r][c] = '.'; // undo and let the caller try its next digit
    empty.push(cell);
    return false;
  };

  solve();
};

What the interviewer is checking

This checks that you can write clean backtracking with proper undo, keep fast lookup structures in sync, and reason about pruning such as choosing the most constrained cell.

Mistakes to avoid

• Forgetting to undo the row, column and box sets (and the board cell) when a branch fails.
• Computing the box index wrongly; it is (r // 3) * 3 + c // 3.
• Writing integers instead of one-character strings into the board.
• Continuing to search after a solution is found, which then overwrites it while backtracking.

Follow-ups to expect

• How would you check whether a puzzle has more than one solution? (Count solutions, stop at two.)
• Can bitmasks replace the sets? (Nine-bit integers per row, column, box.)
• How would you generate puzzles with a unique solution? (Remove clues while uniqueness holds.)

In real software

Constraint solvers used for timetabling, register allocation and configuration checking rely on the same backtracking with "most constrained variable first" ordering.

Practice next