Skip to main content

96. Sudoku Solver

hardAsked at Datadog

Solve a 9x9 Sudoku via backtracking. Datadog uses this as a deep constraint-satisfaction question — same shape as their resource-allocation solver that fills a constrained schedule.

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

Source citations

Public interview reports confirming this problem appears in Datadog loops.

  • Glassdoor (2026-Q1)— Datadog onsite — CSP problem.

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; each of the digits 1-9 must occur exactly once in each column; each of the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.

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 = standard partially-filled 9x9
Output
completed valid 9x9

Approaches

1. Try all digits, validate fully each time

For each empty cell, try 1-9; after each, re-validate the full board.

Time
way too slow
Space
O(81)
// Brute force with full re-validation. Anti-pattern.

Tradeoff: Quadratic-per-step validation. Datadog will reject.

2. Backtracking with row/col/box sets (optimal)

Pre-build rows[], cols[], boxes[] sets. For each empty cell, try digits not in any set. Backtrack on failure.

Time
exponential worst case but fast in practice
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 i = 0; i < 9; i++) for (let j = 0; j < 9; j++) {
    if (board[i][j] === '.') empties.push([i, j]);
    else {
      rows[i].add(board[i][j]);
      cols[j].add(board[i][j]);
      boxes[3*Math.floor(i/3)+Math.floor(j/3)].add(board[i][j]);
    }
  }
  function dfs(idx) {
    if (idx === empties.length) return true;
    const [i, j] = empties[idx];
    const b = 3*Math.floor(i/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)) {
        board[i][j] = ch;
        rows[i].add(ch); cols[j].add(ch); boxes[b].add(ch);
        if (dfs(idx + 1)) return true;
        board[i][j] = '.';
        rows[i].delete(ch); cols[j].delete(ch); boxes[b].delete(ch);
      }
    }
    return false;
  }
  dfs(0);
}

Tradeoff: Pre-built sets give O(1) validity check. Backtracking explores only legal branches. Datadog-canonical CSP.

Datadog-specific tips

Datadog grades on (1) pre-building row/col/box constraint sets for O(1) validity, and (2) clean backtracking with mark/unmark. Mention MRV (most-constrained variable) heuristic for further speed.

Common mistakes

  • Validating by scanning rows/cols/boxes each time — O(27) per check, slow.
  • Forgetting to UNmark on backtrack — corrupts state.
  • Not modifying board in place — wastes memory.

Follow-up questions

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

  • Valid Sudoku (LC 36) — validate only.
  • MRV heuristic — pick the most-constrained cell next.
  • Datadog-style: resource scheduler with multi-dim 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 pre-build sets?

O(1) validity check vs O(27). Critical for the inner backtracking loop.

MRV?

Most-Remaining-Values: at each step, pick the empty cell with the fewest legal digits. Dramatically reduces branching.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →