37. Sudoku Solver

Time: O(9^81)

Space: O(1)

Intuition

Backtracking: find the next empty cell, try digits 1 - 9, check validity with the same three-set approach as problem 36, place the digit and recurse. If recursion returns false (dead end), remove the digit and try the next. When no empty cell remains, the board is solved.

Algorithm

1Find the first empty cell (containing "."). If none exists, return true (solved).
2Try each digit "1" - "9". Check if it is valid in the current row, column, and 3*3 box.
3Place the digit, recurse. If recursion returns true, propagate true up.
4Backtrack: reset the cell to "." if recursion fails.
5If no digit works, return false.

Example Walkthrough

Input: A valid Sudoku puzzle

1.Find first empty (r=0,c=0). Try "1": valid? Place "1", recurse.
2.Recursion eventually fails -> backtrack, try "2", ..., try "5": valid, recurse.
3.Continue until all 81 cells are filled consistently.

Output: Board filled in-place

Common Pitfalls

•Cache row/col/box membership in sets for O(1) checks - do not re-scan the board on every placement.
•Return immediately when a valid solution is found to avoid unnecessary backtracking.

37.cs

// Approach: Backtracking DFS. Try placing digits 1–9 at each empty cell,
// validate row/col/box constraints before proceeding, backtrack on failure.
// Time: O(9^81) Space: O(1)

public class Solution
{
    public void SolveSudoku(char[][] board)
    {
        Dfs(board, 0);
    }

    private bool Dfs(char[][] board, int s)
    {
        if (s == 81)
            return true;

        int i = s / 9;
        int j = s % 9;

        if (board[i][j] != '.')
            return Dfs(board, s + 1);

        for (char c = '1'; c <= '9'; ++c)
        {
            if (IsValid(board, i, j, c))
            {
                board[i][j] = c;
                if (Dfs(board, s + 1))
                    return true;
                board[i][j] = '.';
            }
        }

        return false;
    }

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

Was this solution helpful?