Skip to main content

94. Sudoku Solver

hardAsked at Plaid

Solve a 9x9 Sudoku in place. Plaid asks this as a backtracking + constraint-propagation problem — the same shape as their constraint-satisfaction engine that validates merchant-category assignments under multi-axis rules.

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

Source citations

Public interview reports confirming this problem appears in Plaid loops.

  • Glassdoor (2025)— Plaid platform-team hard.
  • LeetCode Discuss (2026)— Plaid constraint-satisfaction.

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, column, and each of the nine 3x3 sub-boxes. 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
Standard partially-filled Sudoku grid
Output
Fully solved grid

Approaches

1. Brute force all assignments

Try every digit at every empty cell.

Time
9^81 worst
Space
O(81)
// Brute. Don't ship.

Tradeoff: Catastrophic.

2. Backtracking with constraint tracking

Maintain rows/cols/boxes bitmasks. For each empty cell, try valid digits and recurse.

Time
exponential worst, fast in practice
Space
O(81)
function solveSudoku(board) {
  const rows = new Array(9).fill(0), cols = new Array(9).fill(0), boxes = new Array(9).fill(0);
  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[(Math.floor(r / 3)) * 3 + Math.floor(c / 3)] |= bit;
    }
  }
  function bt(pos) {
    if (pos === 81) return true;
    const r = Math.floor(pos / 9), c = pos % 9;
    if (board[r][c] !== '.') return bt(pos + 1);
    const b = Math.floor(r / 3) * 3 + Math.floor(c / 3);
    for (let d = 1; d <= 9; d++) {
      const bit = 1 << (d - 1);
      if (rows[r] & bit || cols[c] & bit || boxes[b] & bit) continue;
      board[r][c] = String(d);
      rows[r] |= bit; cols[c] |= bit; boxes[b] |= bit;
      if (bt(pos + 1)) return true;
      board[r][c] = '.';
      rows[r] ^= bit; cols[c] ^= bit; boxes[b] ^= bit;
    }
    return false;
  }
  bt(0);
}

Tradeoff: Bitmask checks are O(1). The constraint tracking prunes aggressively, making the worst case rare in practice.

Plaid-specific tips

Plaid loves the bitmask trick because it generalizes to multi-axis constraint validation in their merchant-category engine. Bonus signal: discuss the 'most-constrained cell first' heuristic (MRV) — pick the empty cell with the fewest legal options to prune faster.

Common mistakes

  • Not maintaining the row/col/box bitmasks — O(9) checks instead of O(1) per attempt.
  • Forgetting to undo the bitmask update on backtrack.
  • Off-by-one in the box index calculation.

Follow-up questions

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

  • Generate a Sudoku puzzle (not just solve).
  • Solve faster using MRV heuristic + AC-3.
  • Generalize to 16x16.

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 bitmask instead of Set?

Faster — bitmask checks and updates are single integer ops. For 9 possible values, a single int suffices.

What's MRV?

Minimum Remaining Values — pick the empty cell with the fewest legal digits first. Cuts branching factor dramatically.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →