Skip to main content

87. Sudoku Solver

hardAsked at Snowflake

Solve a 9x9 Sudoku puzzle. Snowflake asks this to test backtracking with constraint propagation — relevant to constraint solving during type inference and constraint validation.

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

Source citations

Public interview reports confirming this problem appears in Snowflake loops.

  • Glassdoor (2025-Q4)— Snowflake compiler-team uses this for constraint-solver discussion.
  • LeetCode Discuss (2025-09)— Reported at Snowflake SDE-II screens.

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 of the digits 1-9 must occur exactly once in each row, exactly once in each column, and exactly once in each of the 9 3x3 sub-boxes of the grid. The '.' character indicates empty cells. It is guaranteed that the input has only one solution.

Constraints

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

Examples

Example 1

Input
9x9 board with empties
Output
Filled 9x9 board

Approaches

1. Backtracking with linear validation

For each empty cell, try 1-9; validate row/col/box; recurse; revert.

Time
exponential
Space
O(81)
// outline — validation step is O(27) per try; whole solve is bounded by branching.

Tradeoff: Works but rechecks the same row/col/box repeatedly.

2. Backtracking with precomputed sets (optimal)

Precompute Set per row, col, box of digits already present. On placement, add to all three sets; on revert, remove. Pick next empty cell to fill.

Time
exponential, much better constants
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());
  const empties = [];
  for (let r = 0; r < 9; r++) for (let c = 0; c < 9; c++) {
    if (board[r][c] === '.') empties.push([r, c]);
    else {
      rows[r].add(board[r][c]);
      cols[c].add(board[r][c]);
      boxes[Math.floor(r/3)*3 + Math.floor(c/3)].add(board[r][c]);
    }
  }
  function backtrack(idx) {
    if (idx === empties.length) return true;
    const [r, c] = empties[idx];
    const b = Math.floor(r/3)*3 + Math.floor(c/3);
    for (let d = 1; d <= 9; d++) {
      const s = String(d);
      if (rows[r].has(s) || cols[c].has(s) || boxes[b].has(s)) continue;
      board[r][c] = s;
      rows[r].add(s); cols[c].add(s); boxes[b].add(s);
      if (backtrack(idx + 1)) return true;
      board[r][c] = '.';
      rows[r].delete(s); cols[c].delete(s); boxes[b].delete(s);
    }
    return false;
  }
  backtrack(0);
}

Tradeoff: Set operations are O(1). Could be optimized further with bitmasks; typical for production solvers.

Snowflake-specific tips

Snowflake interviewers want the precomputed-sets version because it captures constraint propagation. Bonus signal: discuss MRV (Minimum Remaining Values) heuristic — pick the empty cell with the fewest valid digits next, dramatically reducing branching.

Common mistakes

  • Re-scanning the board for each digit attempt — O(n) per try, when sets give O(1).
  • Forgetting to revert all three sets (row, col, box) when backtracking.
  • Iterating cells in arbitrary order — MRV is much faster than left-to-right scan.

Follow-up questions

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

  • Add MRV heuristic.
  • Solve in bitmask form — set bit per digit per row/col/box.
  • How does Snowflake's type-inference solver propagate constraints?

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 precomputed sets?

Without them, every digit attempt revalidates row/col/box in O(27). Sets bring it to O(1) lookup per constraint.

What's MRV?

Pick the empty cell with the smallest set of legal digits. Filling those first prunes the search tree dramatically — sometimes solves the puzzle without backtracking at all.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →