Sudoku puzzle completion challenge

You're sitting in an interview at Bloomberg, and the interviewer slides a partially filled Sudoku grid across the table. "Forget solving it by hand," they say. "Write me a program that solves any valid Sudoku board." This problem, also known as the "Sudoku Solver" on other platforms, is a classic test of your ability to implement constraint satisfaction through backtracking. It's a favorite at companies like Bloomberg, Microsoft, Adobe, and Google because it combines recursion, validation logic, and in-place mutation into one compact challenge.

TL;DR

Solve Sudoku by scanning left-to-right, top-to-bottom for the first empty cell, then trying digits '1' through '9'. For each candidate, check whether the digit already appears in the same row, column, or 3x3 sub-grid. If the placement is valid, recurse to fill the next empty cell. If no digit works, backtrack by resetting the cell to '.' and returning false. The recursion bottoms out when every cell is filled, returning true to signal success. Time complexity is O((9!)^9) in the worst case, though constraint pruning makes real puzzles solve in milliseconds.

Why This Problem Matters

Sudoku solving is the textbook example of backtracking with constraint propagation. In interviews, it tests whether you can decompose a complex problem into a clean recursive structure. The same pattern of "try, validate, recurse, backtrack" appears in problems like N-Queens, permutation generation, and word search. If you can implement a Sudoku solver cleanly, you've demonstrated mastery of a technique that transfers to dozens of other problems.

Understanding the Problem

Here's what we need to do:

Given: A 9x9 board where filled cells contain '1'-'9' and empty cells contain '.' Task: Fill every '.' cell so that each row, column, and 3x3 sub-grid contains the digits 1-9 exactly once Constraint: The input always has exactly one valid solution Return: The completed board (modified in-place)

The first three rows of the example puzzle look like this. Blue cells are pre-filled, and purple cells are the empty slots we need to fill:

Loading visualization...

The Three Constraints

Every time we place a digit, it must satisfy all three Sudoku rules simultaneously:

Row constraint: The digit does not appear elsewhere in the same row
Column constraint: The digit does not appear elsewhere in the same column
Sub-grid constraint: The digit does not appear in the same 3x3 box

For a cell like position (0,2), we need to check against the green cells (row), the purple cells (column), and the blue cells (3x3 sub-grid):

Loading visualization...

This decision tree shows what happens at cell (0,2). We try each digit, check constraints, and only proceed when a valid placement is found. If a later cell reaches a dead end, we unwind back here and try the next digit.

Edge Cases

Nearly complete board: Only a few empty cells, so the solver finishes almost instantly
Fully empty board: The worst case for backtracking, though still solvable because the first valid path through all 81 cells works
Dense constraints: Boards where most cells are pre-filled tend to have fewer branching possibilities, making them faster to solve

Solution Approach

The algorithm follows a simple loop:

Scan every cell from top-left to bottom-right
When you find an empty cell, try placing digits '1' through '9'
For each candidate digit, validate it against the row, column, and 3x3 sub-grid
If the digit is valid, place it and recursively solve the rest of the board
If the recursive call succeeds, propagate true upward
If it fails, reset the cell to '.' (backtrack) and try the next digit
If no digit works, return false to trigger backtracking in the caller
When no empty cells remain, the puzzle is solved. Return true.

The validation function isValid is the workhorse. It uses a single loop from 0 to 8 to check all three constraints simultaneously. For index i:

board[row][i] checks the entire row
board[i][col] checks the entire column
board[row / 3 * 3 + i / 3][col / 3 * 3 + i % 3] checks the 3x3 sub-grid

That sub-grid formula is the tricky part. For a cell at (row, col), row / 3 * 3 gives the starting row of the sub-grid (using integer division). Adding i / 3 moves through the three rows of the sub-grid. Similarly, col / 3 * 3 + i % 3 walks through the three columns. As i goes from 0 to 8, you visit all nine cells of the sub-grid.

Implementation

Prefer a different language? Jump to solutions in other languages.

public class Solution {

  public char[][] solveSudoku(char[][] board) {
    solve(board);
    return board;
  }

  private boolean solve(char[][] board) {
    for (int row = 0; row < 9; row++) {
      for (int col = 0; col < 9; col++) {
        if (board[row][col] == '.') {
          for (char num = '1'; num <= '9'; num++) {
            if (isValid(board, row, col, num)) {
              board[row][col] = num;
              if (solve(board)) {
                return true;
              }
              board[row][col] = '.';
            }
          }
          return false;
        }
      }
    }
    return true;
  }

  private boolean isValid(char[][] board, int row, int col, char num) {
    for (int i = 0; i < 9; i++) {
      if (board[row][i] == num || board[i][col] == num
          || board[row / 3 * 3 + i / 3][col / 3 * 3 + i % 3] == num) {
        return false;
      }
    }
    return true;
  }
}

Let's trace through the key moments. The solve method scans cell by cell. It finds the first empty cell at (0,2). The isValid check rejects 1 (not present, wait, actually let's look: row 0 has 5, 3, 7, so 1 is not in the row. Column 2 has 8. The sub-grid has 5, 3, 6, 9, 8. So 1 is not a conflict, but downstream cells might force a backtrack). The solver places each valid candidate, recurses, and backtracks as needed.

The key line is board[row][col] = '.' after a failed recursive call. Without this reset, cells would retain incorrect values and pollute future constraint checks.

The Sub-Grid Index Formula

The expression board[row / 3 * 3 + i / 3][col / 3 * 3 + i % 3] deserves a closer look. Consider cell (4, 7). Using integer division:

row / 3 * 3 = 4 / 3 * 3 = 1 * 3 = 3 (sub-grid starts at row 3)
col / 3 * 3 = 7 / 3 * 3 = 2 * 3 = 6 (sub-grid starts at column 6)

As i ranges from 0 to 8:

i / 3 produces 0, 0, 0, 1, 1, 1, 2, 2, 2 (row offsets)
i % 3 produces 0, 1, 2, 0, 1, 2, 0, 1, 2 (column offsets)

This visits cells (3,6), (3,7), (3,8), (4,6), (4,7), (4,8), (5,6), (5,7), (5,8), which is exactly the 3x3 block containing (4,7).

Completed Board

After the solver runs on our example puzzle, the first three rows look like this. Blue cells were given, and orange cells were filled by the algorithm:

Loading visualization...

Complexity Analysis

Time Complexity: O((9!)^9)

In the theoretical worst case, each of the 9 rows could have up to 9! valid permutations. Since there are 9 rows, the upper bound is O((9!)^9). In practice, constraint checking prunes the vast majority of branches. Most standard Sudoku puzzles with 25+ givens solve in under a millisecond because each placement eliminates candidates from roughly 20 other cells (the row, column, and sub-grid peers).

Space Complexity: O(1)

The board is modified in-place with a fixed size of 81 cells. The recursion stack depth is bounded by the number of empty cells, which is at most 81. Since both the board dimensions and recursion depth are constants (independent of any input parameter), the space complexity is O(1).

Alternative Approaches

Constraint propagation with backtracking: Reduce candidates for each cell before guessing. This is what expert Sudoku players do mentally and dramatically cuts the search space.
Dancing Links (DLX): Treats Sudoku as an exact cover problem. Extremely fast but complex to implement and not expected in interviews.
Bit manipulation: Use bitmasks to track which digits are used in each row, column, and sub-grid. Turns validation into O(1) bitwise operations. A good optimization to mention as a follow-up.

Common Pitfalls

Forgetting to backtrack: The line board[row][col] = '.' is essential. Without it, incorrect guesses remain on the board and break constraint checks for other cells.
Returning the wrong value: After trying all 9 digits for an empty cell, you must return false. Falling through without returning causes the solver to skip empty cells and produce invalid boards.
Wrong sub-grid formula: Using row % 3 instead of row / 3 * 3 computes the offset within the sub-grid rather than the sub-grid's starting position. This is the most common bug in interviews.
Modifying the board without returning it: The problem asks you to return the board even though it's modified in-place. Forgetting the return statement is an easy mistake.

Interview Tips

When solving this problem live:

Start with the structure: Explain the three Sudoku constraints and the backtracking strategy before writing any code. Interviewers want to see your thought process.
Write isValid first: It's the simpler function and establishes the constraint-checking foundation. Then build solve on top of it.
Walk through the sub-grid formula: This is the part interviewers ask about most. Draw a 9x9 grid, pick a cell, and show how the formula visits the correct 3x3 block.
Mention optimizations: After presenting the basic solution, discuss how bitmasks or constraint propagation could speed things up. This shows depth beyond the textbook answer.
Relate to other backtracking problems: If you've solved N-Queens or word search, point out the shared "try-validate-recurse-backtrack" pattern.

Key Takeaways

The backtracking template for Sudoku (find empty cell, try digits, validate, recurse, reset on failure) is the standard interview solution at companies like Bloomberg, Microsoft, and Google.
The sub-grid formula row / 3 * 3 + i / 3 and col / 3 * 3 + i % 3 lets you check all 9 cells of a 3x3 block in a single loop alongside the row and column checks.
Always reset the cell to '.' when backtracking. This single line is the difference between a correct solver and one that produces garbage.
Real-world Sudoku solving uses constraint propagation to reduce candidates before guessing. Mention this as an optimization if time permits.
The same "try, validate, recurse, backtrack" pattern powers solutions for N-Queens, permutation generation, combination sum, and word search problems.

Solutions in Other Languages

Python

class Solution:
    def solve_sudoku(self, board):
        def is_valid(board, row, col, num):
            for i in range(9):
                if board[row][i] == num or board[i][col] == num:
                    return False
                if board[3 * (row // 3) + i // 3][3 * (col // 3) + i % 3] == num:
                    return False
            return True

        def solve():
            for i in range(9):
                for j in range(9):
                    if board[i][j] == '.':
                        for num in map(str, range(1, 10)):
                            if is_valid(board, i, j, num):
                                board[i][j] = num
                                if solve():
                                    return True
                                board[i][j] = '.'
                        return False
            return True

        solve()
        return board

JavaScript

class Solution {
  solveSudoku(board) {
    const isValid = (board, row, col, num) => {
      for (let i = 0; i < 9; i++) {
        if (board[row][i] === num || board[i][col] === num ||
            board[Math.floor(row / 3) * 3 + Math.floor(i / 3)][Math.floor(col / 3) * 3 + i % 3] === num) {
          return false;
        }
      }
      return true;
    };

    const solve = () => {
      for (let row = 0; row < 9; row++) {
        for (let col = 0; col < 9; col++) {
          if (board[row][col] === '.') {
            for (let num = 1; num <= 9; num++) {
              const charNum = num.toString();
              if (isValid(board, row, col, charNum)) {
                board[row][col] = charNum;
                if (solve()) return true;
                board[row][col] = '.';
              }
            }
            return false;
          }
        }
      }
      return true;
    };

    solve();
    return board;
  }
}

TypeScript

class Solution {
  solveSudoku(board: string[][]): string[][] {
    const isValid = (board: string[][], row: number, col: number, num: string): boolean => {
      for (let i = 0; i < 9; i++) {
        if (board[row][i] === num || board[i][col] === num ||
            board[Math.floor(row / 3) * 3 + Math.floor(i / 3)][Math.floor(col / 3) * 3 + i % 3] === num) {
          return false;
        }
      }
      return true;
    };

    const solve = (): boolean => {
      for (let row = 0; row < 9; row++) {
        for (let col = 0; col < 9; col++) {
          if (board[row][col] === '.') {
            for (let num = 1; num <= 9; num++) {
              const charNum = num.toString();
              if (isValid(board, row, col, charNum)) {
                board[row][col] = charNum;
                if (solve()) return true;
                board[row][col] = '.';
              }
            }
            return false;
          }
        }
      }
      return true;
    };

    solve();
    return board;
  }
}

C++

#include <vector>

class Solution {
public:
  std::vector<std::vector<char>> solveSudoku(std::vector<std::vector<char>> &board) {
    solve(board);
    return board;
  }

private:
  bool solve(std::vector<std::vector<char>> &board) {
    for (int row = 0; row < 9; ++row) {
      for (int col = 0; col < 9; ++col) {
        if (board[row][col] == '.') {
          for (char num = '1'; num <= '9'; ++num) {
            if (isValid(board, row, col, num)) {
              board[row][col] = num;
              if (solve(board)) return true;
              board[row][col] = '.';
            }
          }
          return false;
        }
      }
    }
    return true;
  }

  bool isValid(const std::vector<std::vector<char>> &board, int row, int col, char num) {
    for (int i = 0; i < 9; ++i) {
      if (board[row][i] == num || board[i][col] == num ||
          board[row / 3 * 3 + i / 3][col / 3 * 3 + i % 3] == num) {
        return false;
      }
    }
    return true;
  }
};

Scala

class Solution {
  def solveSudoku(board: Array[Array[Char]]): Array[Array[Char]] = {
    def isValid(board: Array[Array[Char]], row: Int, col: Int, num: Char): Boolean = {
      for (i <- 0 until 9) {
        if (board(row)(i) == num || board(i)(col) == num ||
            board(3 * (row / 3) + i / 3)(3 * (col / 3) + i % 3) == num) {
          return false
        }
      }
      true
    }

    def solve(board: Array[Array[Char]]): Boolean = {
      for (row <- 0 until 9) {
        for (col <- 0 until 9) {
          if (board(row)(col) == '.') {
            for (num <- '1' to '9') {
              if (isValid(board, row, col, num)) {
                board(row)(col) = num
                if (solve(board)) return true
                board(row)(col) = '.'
              }
            }
            return false
          }
        }
      }
      true
    }

    solve(board)
    board
  }
}

Kotlin

class Solution {
  fun solveSudoku(board: Array<CharArray>): Array<CharArray> {
    solve(board)
    return board
  }

  private fun solve(board: Array<CharArray>): Boolean {
    for (row in 0 until 9) {
      for (col in 0 until 9) {
        if (board[row][col] == '.') {
          for (num in '1'..'9') {
            if (isValid(board, row, col, num)) {
              board[row][col] = num
              if (solve(board)) return true
              board[row][col] = '.'
            }
          }
          return false
        }
      }
    }
    return true
  }

  private fun isValid(board: Array<CharArray>, row: Int, col: Int, num: Char): Boolean {
    for (i in 0 until 9) {
      if (board[row][i] == num || board[i][col] == num ||
          board[row / 3 * 3 + i / 3][col / 3 * 3 + i % 3] == num) {
        return false
      }
    }
    return true
  }
}

Ruby

class Solution
  def solve_sudoku(board)
    solve(board)
    board
  end

  def solve(board)
    (0...9).each do |row|
      (0...9).each do |col|
        if board[row][col] == '.'
          ('1'..'9').each do |num|
            if valid?(board, row, col, num)
              board[row][col] = num
              return true if solve(board)
              board[row][col] = '.'
            end
          end
          return false
        end
      end
    end
    true
  end

  def valid?(board, row, col, num)
    (0...9).each do |i|
      if board[row][i] == num || board[i][col] == num ||
         board[row / 3 * 3 + i / 3][col / 3 * 3 + i % 3] == num
        return false
      end
    end
    true
  end
end

Swift

class Solution {
  func solveSudoku(_ board: [[Character]]) -> [[Character]] {
    var board = board
    solve(&board)
    return board
  }

  private func solve(_ board: inout [[Character]]) -> Bool {
    for row in 0..<9 {
      for col in 0..<9 {
        if board[row][col] == Character(".") {
          for num in "123456789" {
            if isValid(board, row, col, num) {
              board[row][col] = num
              if solve(&board) { return true }
              board[row][col] = Character(".")
            }
          }
          return false
        }
      }
    }
    return true
  }

  private func isValid(_ board: [[Character]], _ row: Int, _ col: Int, _ num: Character) -> Bool {
    for i in 0..<9 {
      if board[row][i] == num || board[i][col] == num ||
         board[row / 3 * 3 + i / 3][col / 3 * 3 + i % 3] == num {
        return false
      }
    }
    return true
  }
}

Rust

impl Solution {
    pub fn solve_sudoku(&self, mut board: Vec<Vec<char>>) -> Vec<Vec<char>> {
        Self::solve(&mut board);
        board
    }

    fn solve(board: &mut Vec<Vec<char>>) -> bool {
        for row in 0..9 {
            for col in 0..9 {
                if board[row][col] == '.' {
                    for num in '1'..='9' {
                        if Self::is_valid(board, row, col, num) {
                            board[row][col] = num;
                            if Self::solve(board) { return true; }
                            board[row][col] = '.';
                        }
                    }
                    return false;
                }
            }
        }
        true
    }

    fn is_valid(board: &[Vec<char>], row: usize, col: usize, num: char) -> bool {
        for i in 0..9 {
            if board[row][i] == num || board[i][col] == num ||
               board[row / 3 * 3 + i / 3][col / 3 * 3 + i % 3] == num {
                return false;
            }
        }
        true
    }
}

C#

public class Solution {
    public char[][] SolveSudoku(char[][] board) {
        Solve(board);
        return board;
    }

    private bool Solve(char[][] board) {
        for (int row = 0; row < 9; row++) {
            for (int col = 0; col < 9; col++) {
                if (board[row][col] == '.') {
                    for (char num = '1'; num <= '9'; num++) {
                        if (IsValid(board, row, col, num)) {
                            board[row][col] = num;
                            if (Solve(board)) return true;
                            board[row][col] = '.';
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }

    private bool IsValid(char[][] board, int row, int col, char num) {
        for (int i = 0; i < 9; i++) {
            if (board[row][i] == num || board[i][col] == num ||
                board[row / 3 * 3 + i / 3][col / 3 * 3 + i % 3] == num) {
                return false;
            }
        }
        return true;
    }
}

Dart

class Solution {
  List<List<String>> solveSudoku(List<List<String>> board) {
    _solve(board);
    return board;
  }

  bool _solve(List<List<String>> board) {
    for (int row = 0; row < 9; row++) {
      for (int col = 0; col < 9; col++) {
        if (board[row][col] == '.') {
          for (int num = 1; num <= 9; num++) {
            String numStr = num.toString();
            if (_isValid(board, row, col, numStr)) {
              board[row][col] = numStr;
              if (_solve(board)) return true;
              board[row][col] = '.';
            }
          }
          return false;
        }
      }
    }
    return true;
  }

  bool _isValid(List<List<String>> board, int row, int col, String num) {
    for (int i = 0; i < 9; i++) {
      if (board[row][i] == num || board[i][col] == num ||
          board[row ~/ 3 * 3 + i ~/ 3][col ~/ 3 * 3 + i % 3] == num) {
        return false;
      }
    }
    return true;
  }
}

PHP

class Solution {
    public function solveSudoku(array $board): array {
        $this->solve($board);
        return $board;
    }

    private function solve(array &$board): bool {
        for ($row = 0; $row < 9; $row++) {
            for ($col = 0; $col < 9; $col++) {
                if ($board[$row][$col] === '.') {
                    for ($num = 1; $num <= 9; $num++) {
                        $charNum = (string)$num;
                        if ($this->isValid($board, $row, $col, $charNum)) {
                            $board[$row][$col] = $charNum;
                            if ($this->solve($board)) return true;
                            $board[$row][$col] = '.';
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }

    private function isValid(array $board, int $row, int $col, string $num): bool {
        for ($i = 0; $i < 9; $i++) {
            if ($board[$row][$i] === $num || $board[$i][$col] === $num ||
                $board[intdiv($row, 3) * 3 + intdiv($i, 3)][intdiv($col, 3) * 3 + $i % 3] === $num) {
                return false;
            }
        }
        return true;
    }
}

Frequently Asked Questions

What is the time complexity of solving Sudoku with backtracking?

The theoretical worst case is O((9!)^9) since each row can have at most 9! permutations, and there are 9 rows. In practice, constraint checking prunes the search space dramatically, making most puzzles solvable in milliseconds. The guaranteed single-solution constraint further reduces the effective search space.

Why is backtracking the standard approach for solving Sudoku?

Backtracking systematically explores valid placements and abandons paths as soon as a constraint is violated. This is efficient because Sudoku constraints propagate heavily. Placing one digit often reduces choices for neighboring cells. More advanced techniques like constraint propagation or dancing links exist, but backtracking is the expected interview solution.

How does the isValid function check all three Sudoku constraints?

A single loop from 0 to 8 checks all three constraints simultaneously. For each index i: board[row][i] checks the row, board[i][col] checks the column, and board[row/3*3 + i/3][col/3*3 + i%3] checks the 3x3 sub-grid. The sub-grid formula maps i from 0-8 to the nine cells within the correct 3x3 block.

What is the space complexity of the backtracking Sudoku solver?

The space complexity is O(1) because the board is modified in-place and has a fixed size of 81 cells. The recursion depth is bounded by the number of empty cells, which is at most 81. Since the board dimensions are constant, the stack space is also bounded by a constant.

How does backtracking differ from brute force for Sudoku?

Brute force would try all possible combinations of digits in empty cells and validate at the end. Backtracking validates constraints incrementally as each digit is placed. If placing a digit at cell (i,j) violates a constraint, all subsequent branches from that state are pruned immediately, avoiding billions of wasted computations.

Can Sudoku be solved without recursion?

Yes, you can use an explicit stack to simulate the recursion. Maintain a list of empty cell coordinates and iterate through them with a pointer. When backtracking, move the pointer backward and try the next number. The recursive approach is cleaner and easier to explain in interviews, which is why it is preferred.

How do you identify the 3x3 sub-grid for a given cell?

For a cell at position (row, col), the top-left corner of its 3x3 sub-grid is at (row/3*3, col/3*3) using integer division. For example, cell (5,7) belongs to the sub-grid starting at (3,6). The formula row/3*3 + i/3 and col/3*3 + i%3 iterates through all 9 cells of that sub-grid as i goes from 0 to 8.

What happens if the Sudoku puzzle has no solution?

The solve function returns false after exhausting all possibilities for every empty cell. The backtracking unwinds completely, and the board remains in its original state since every placement is undone during backtracking. In this problem, the input is guaranteed to have exactly one solution.

How does this problem relate to the Sudoku Board Integrity Check problem?

The integrity check (problem 183) validates whether a partially filled board follows Sudoku rules without solving it. The solver (this problem) builds on that validation logic. The isValid function used during backtracking performs the same constraint checks, but applies them incrementally as digits are placed rather than checking the entire board at once.

What are common mistakes when implementing a Sudoku solver?

The most frequent mistakes are forgetting to backtrack (resetting the cell to '.'), returning the wrong boolean value from the recursive function, and incorrect sub-grid index calculation. Another common error is not returning false after trying all 9 digits for an empty cell, which causes infinite loops or incorrect solutions.

TL;DR

Why This Problem Matters

Understanding the Problem

The Three Constraints

Edge Cases

Solution Approach

Implementation

The Sub-Grid Index Formula

Completed Board

Complexity Analysis

Time Complexity: O((9!)^9)

Space Complexity: O(1)

Alternative Approaches

Common Pitfalls

Interview Tips

Key Takeaways

Related Problems and Practice

Solutions in Other Languages

Python

JavaScript

TypeScript

C++

Scala

Kotlin

Ruby

Swift

Rust

C#

Dart

PHP

Frequently Asked Questions