Backtracking

Sudoku Solver

Find an empty cell, try digits 1-9. For each digit, check if it's valid in the current row, column, and 3×3 box. If valid, place it and recurse. If the recursion fails, remove the digit and try the next one.

O(9^(empty cells))

O(1)

How It Works

The Sudoku solver backtracks over empty cells: find the next blank, try digits 1 through 9, and for each digit check that it does not already appear in the cell's row, column, or 3x3 box. If a digit passes, write it in and recurse to the next blank; if the recursion eventually fails, erase the digit and try the next one. When no blanks remain, the board is solved. The box index for cell (r, c) is (r / 3) * 3 + c / 3 using integer division, which maps all nine cells of a box to one identifier.

Because the board is fixed at 9x9, worst-case work is bounded by a (large) constant, but the practical speedups matter: precomputed boolean arrays for each row, column, and box make validity O(1), and choosing the empty cell with the fewest legal candidates (most-constrained-first) collapses the search tree dramatically. Space is O(1) beyond the recursion over at most 81 cells.

Step-by-Step Visualization

Sudoku solver: fill empty cells with valid digits

MethodBacktracking

1/3

Code

Java

static void solveSudoku(char[][] board) {
  solve(board);
}

static boolean solve(char[][] board) {
  for (int r = 0; r < 9; r++)
    for (int c = 0; c < 9; c++)
      if (board[r][c] == '.') {
        for (char n = '1'; n <= '9'; n++) {
          if (isValid(board, r, c, n)) {
            board[r][c] = n;
            if (solve(board)) return true;
            board[r][c] = '.';
          }
        }
        return false;
      }
  return true;
}

static 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) return false;
    int r = 3*(row/3) + i/3, c = 3*(col/3) + i%3;
    if (board[r][c] == num) return false;
  }
  return true;
}

Tips & Gotchas

1Find empty cell, try digits 1-9

2Check row, column, and 3x3 box constraints

3Backtrack immediately on constraint violation

Practice Problems

1Sudoku Solver
2Valid Sudoku
3N-Queens
4Word Search II

About the Backtracking Pattern

Systematically explore all possible solutions by making choices one at a time. If a choice leads to a dead end, undo it (backtrack) and try the next option. Think of it as exploring a decision tree — you go deep, and come back up when stuck.

Key insight

Every recursive solution has: base case, recursive case, and combining step. For backtracking, add: make choice → recurse → undo choice. Prune early to avoid TLE.

Common Recursion Interview Problems

Subsets
Permutations
Combination Sum
N-Queens
Word Search
Generate Parentheses
Letter Combinations of Phone Number

Frequently Asked Questions

Why does picking the most constrained cell first speed things up so much?

A cell with few legal digits either forces the right value quickly or fails immediately, exposing contradictions near the top of the search tree where pruning saves the most work. Filling cells in raw scan order defers those failures deep into the tree, multiplying wasted exploration.

How should I track used digits to avoid rescanning rows and columns?

Maintain three 9x9 boolean tables — rows[r][d], cols[c][d], boxes[b][d] — updated on every placement and removal. Validity becomes three O(1) lookups. Bitmasks (one 9-bit integer per row, column, and box) achieve the same with less memory and fast candidate enumeration via bit tricks.

Is Sudoku solving polynomial since the board is fixed at 9x9?

For the standard 9x9 board, yes — the search space is bounded, so the algorithm runs in constant time in a formal sense. Generalized n^2 x n^2 Sudoku, however, is NP-complete, which is why backtracking with pruning, rather than a known polynomial algorithm, is the standard approach.