Skip to main content

37. Sudoku Solver

hard

Fill in a partially completed 9x9 Sudoku board so that every row, column, and 3x3 box contains digits 1-9. Constraint-propagation backtracking — three sets enforce the rules; recursion does the rest.

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

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. The '.' character indicates empty cells. It is guaranteed that the input board 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 board has only one solution.

Examples

Example 1

Input
board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]
Output
(modifies board in place to fully solved grid)

Explanation: Mutate the input board to the unique solution; no return value.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Maintain three arrays of sets — rows[9], cols[9], boxes[9] — populated from the initial board.

Hint 2

Pick the next empty cell. Try digits 1-9 that don't appear in the cell's row, column, or 3x3 box.

Hint 3

Box index = (row / 3) * 3 + (col / 3).

Hint 4

Place the digit, mark all three sets, recurse; on failure, unmark and try the next digit. Return true as soon as any branch fills the board.

Solution approach

Reveal approach

Preprocess: populate rows[9], cols[9], boxes[9] of seen-digit sets from the initial board. The recursion solve(idx) walks cells in row-major order. If idx == 81, the board is full -> return true. If board[r][c] is filled, recurse(idx + 1). Otherwise, for d in '1'..'9', if d is not in rows[r], cols[c], or boxes[boxIndex] (where boxIndex = (r / 3) * 3 + c / 3), place d, mark all three sets, recurse(idx + 1). If that returns true, propagate true. Otherwise unmark and try the next digit. Return false if no digit fits. Time is bounded by the cell count times digit count to the depth of unfilled cells (essentially constant — 9^(empty cells) worst case, but constraint propagation prunes most branches). Space is O(1) given the fixed 9x9 board.

Complexity

Time
O(9^k) worst case, k = empty cells
Space
O(1)

Related patterns

  • backtracking
  • recursion
  • constraint-satisfaction

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Apple
  • Microsoft
  • Uber

Practice these live with InterviewChamp.AI

Drill Sudoku Solver and Recursion problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →