Sudoku Solver Using Backtracking in DSA C - Time & Space Complexity

Time Complexity: Sudoku Solver Using Backtracking

O(9^m)

Understanding Time Complexity

We want to understand how the time needed to solve a Sudoku puzzle changes as the puzzle size or difficulty changes.

Specifically, how the backtracking method's steps grow with the puzzle's empty cells.

Scenario Under Consideration

Analyze the time complexity of the following Sudoku solver code using backtracking.

bool solveSudoku(int board[9][9]) {
    for (int row = 0; row < 9; row++) {
        for (int col = 0; col < 9; col++) {
            if (board[row][col] == 0) {
                for (int num = 1; num <= 9; num++) {
                    if (isSafe(board, row, col, num)) {
                        board[row][col] = num;
                        if (solveSudoku(board))
                            return true;
                        board[row][col] = 0;
                    }
                }
                return false;
            }
        }
    }
    return true;
}

This code tries numbers 1 to 9 in empty cells, checks if safe, and uses recursion to fill the board.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Trying numbers 1 to 9 in each empty cell and recursively solving the rest.
• How many times: For each empty cell, up to 9 attempts; recursion explores many combinations until solution or failure.

How Execution Grows With Input

As the number of empty cells increases, the number of possible number placements grows very fast.

Input Size (empty cells)	Approx. Operations
10	Up to 9^10 = 3,486,784,401 tries
20	Up to 9^20 = 1.21e+19 tries
30	Up to 9^30 = 2.06e+28 tries

Pattern observation: The operations grow exponentially with the number of empty cells, making the problem very costly for many blanks.

Final Time Complexity

Time Complexity: O(9^m) where m is the number of empty cells

This means the time needed grows exponentially as more cells need filling, because each cell can try up to 9 numbers.

Common Mistake

[X] Wrong: "The solver always tries 81 cells with 9 numbers each, so it's just 81*9 = 729 steps."

[OK] Correct: The solver tries many combinations recursively, not just one pass. The number of tries multiplies for each empty cell, causing exponential growth.

Interview Connect

Understanding this exponential growth helps you explain why backtracking can be slow and when it's suitable. It shows your grasp of recursive problem solving and complexity.

Self-Check

"What if we limit the numbers tried in each cell to only valid candidates instead of all 9? How would the time complexity change?"