Skip to main content

93. Sudoku Solver

hardAsked at Reddit

Solve a 9x9 Sudoku puzzle in-place using backtracking. Reddit uses this to test constraint-propagation backtracking — the same shape used when assigning thousands of users to a finite set of moderator-approval slots under multiple non-conflict constraints.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Reddit loops.

  • Glassdoor (2026-Q1)— Reddit on-site backtracking hard.

Problem

Write a program to solve a Sudoku puzzle by filling the empty cells. A sudoku solution must satisfy all of the following rules: each digit 1-9 must occur exactly once in each row, each column, and each of the 9 3x3 sub-boxes of the grid. The '.' character indicates empty cells.

Constraints

  • board.length == 9
  • board[i].length == 9
  • board[i][j] is a digit or '.'.
  • It is guaranteed that the input board has only one solution.

Examples

Example 1

Input
board = [valid 9x9 partial Sudoku]
Output
board filled in

Approaches

1. Brute force try every digit

Try 1-9 in each cell; backtrack on conflict.

Time
huge
Space
O(81)
// Same as below but without precomputed constraint sets. Slower.

Tradeoff: Repeatedly checks row/col/box.

2. Backtracking with constraint sets (optimal)

Precompute row, col, box sets. Try valid digits; recurse; undo on backtrack.

Time
exponential worst-case
Space
O(81)
function solveSudoku(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());
  for (let i = 0; i < 9; i++) for (let j = 0; j < 9; j++) {
    if (board[i][j] !== '.') {
      rows[i].add(board[i][j]);
      cols[j].add(board[i][j]);
      boxes[Math.floor(i/3)*3 + Math.floor(j/3)].add(board[i][j]);
    }
  }
  function backtrack(idx) {
    if (idx === 81) return true;
    const i = Math.floor(idx / 9), j = idx % 9;
    if (board[i][j] !== '.') return backtrack(idx + 1);
    const b = Math.floor(i/3)*3 + Math.floor(j/3);
    for (let d = 1; d <= 9; d++) {
      const ch = String(d);
      if (rows[i].has(ch) || cols[j].has(ch) || boxes[b].has(ch)) continue;
      board[i][j] = ch;
      rows[i].add(ch); cols[j].add(ch); boxes[b].add(ch);
      if (backtrack(idx + 1)) return true;
      board[i][j] = '.';
      rows[i].delete(ch); cols[j].delete(ch); boxes[b].delete(ch);
    }
    return false;
  }
  backtrack(0);
}

Tradeoff: O(1) check per cell thanks to precomputed sets. Bitmask version would be faster.

Reddit-specific tips

Reddit interviewers grade on the constraint-set tracking. Bonus signal: mention MRV (most constrained variable) heuristic — pick the empty cell with fewest options first for major speedup.

Common mistakes

  • Recomputing row/col/box check on every digit try (vs. precomputed sets).
  • Forgetting to undo state on backtrack.
  • Iterating in cell-by-cell order without MRV (functionally correct, slower).

Follow-up questions

An interviewer at Reddit may pivot to one of these next:

  • Valid Sudoku (LC 36) — only validation.
  • N-Queens (LC 51) — similar backtracking.
  • Sudoku with MRV heuristic.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why three sets per dimension?

Each digit must appear once per row, col, and box. Three separate constraints, each O(1) check.

How does MRV help?

Pick the empty cell with fewest valid candidates next. Reduces branching factor dramatically.

Practice these live with InterviewChamp.AI

Drill Sudoku Solver and other Reddit interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →