Bird
Raised Fist0
DSA Pythonprogramming~5 mins

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

Choose your learning style10 modes available
LearnWhyDeepVisualTryChallengeProjectRecallTime
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 does the backtracking method's work grow with the number of empty cells?

Scenario Under Consideration

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


def solve_sudoku(board):
    empty = find_empty_cell(board)
    if not empty:
        return True
    row, col = empty
    for num in range(1, 10):
        if is_valid(board, row, col, num):
            board[row][col] = num
            if solve_sudoku(board):
                return True
            board[row][col] = 0
    return False

This code tries numbers 1 to 9 in each empty cell, checking if the number fits, and uses recursion to solve the rest.

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: Up to 9 choices per empty cell, repeated for each empty cell recursively.
How Execution Grows With Input

Each empty cell can try up to 9 numbers, and for each choice, the solver tries the next empty cell similarly.

Input Size (empty cells)Approx. Operations
10Up to 9^10 = 3,486,784,401 tries
20Up to 9^20 ≈ 1.21e19 tries
30Up to 9^30 ≈ 1.21e28 tries

Pattern observation: The number of operations grows exponentially with the number of empty cells.

Final Time Complexity

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

This means the time needed can grow very fast as more cells are empty, because each cell tries many possibilities recursively.

Common Mistake

[X] Wrong: "The solver always tries exactly 9 options per empty cell, so it's always 9 times the number of empty cells."

[OK] Correct: The solver tries up to 9 options per cell, but it explores many combinations recursively, so the total tries multiply, not just add.

Interview Connect

Understanding this exponential growth helps you explain why backtracking can be slow and why pruning or smarter methods matter.

It shows your grasp of recursion and problem-solving limits, which is valuable in interviews.

Self-Check

"What if we added a heuristic to pick the empty cell with the fewest valid options first? How would that affect the time complexity?"

Practice

(1/5)
1. What is the main purpose of backtracking in a Sudoku solver?
easy
A. To count how many empty cells are in the Sudoku grid
B. To randomly fill the Sudoku grid without checking rules
C. To sort the numbers in each row before solving
D. To try possible numbers and undo choices if they lead to conflicts

Solution

  1. Step 1: Understand backtracking role

    Backtracking tries numbers in empty cells and removes them if they cause conflicts.

  2. Step 2: Compare other options

    Other options do not describe backtracking's trial and error approach.

  3. Final Answer:

    To try possible numbers and undo choices if they lead to conflicts -> Option D

  4. Quick Check:

    Backtracking = Try and undo choices [OK]
Hint: Backtracking means try, check, and undo if wrong [OK]
Common Mistakes:
  • Thinking backtracking fills randomly without checks
  • Confusing backtracking with sorting or counting
  • Ignoring the undo step in backtracking
2. Which of the following is the correct Python syntax to check if a number is safe to place in a Sudoku cell using backtracking?
easy
A. if is_safe(board, row, col, num):
B. if isSafe(board, row, col, num);
C. if is_safe(board, row, col, num)
D. if is_safe board, row, col, num:

Solution

  1. Step 1: Identify correct function call syntax

    Python requires parentheses and a colon after the if condition, so 'if is_safe(board, row, col, num):' is correct.

  2. Step 2: Check other options for syntax errors

    if isSafe(board, row, col, num); uses semicolon instead of colon; C misses colon; D misses parentheses.

  3. Final Answer:

    if is_safe(board, row, col, num): -> Option A

  4. Quick Check:

    Python if syntax = condition + colon [OK]
Hint: Remember if statements end with a colon in Python [OK]
Common Mistakes:
  • Forgetting the colon at the end of if statement
  • Missing parentheses around function arguments
  • Using semicolon instead of colon
3. What will be the output of the following code snippet when solving a Sudoku board with backtracking?
board = [
  [5, 3, 0, 0, 7, 0, 0, 0, 0],
  [6, 0, 0, 1, 9, 5, 0, 0, 0],
  [0, 9, 8, 0, 0, 0, 0, 6, 0],
  [8, 0, 0, 0, 6, 0, 0, 0, 3],
  [4, 0, 0, 8, 0, 3, 0, 0, 1],
  [7, 0, 0, 0, 2, 0, 0, 0, 6],
  [0, 6, 0, 0, 0, 0, 2, 8, 0],
  [0, 0, 0, 4, 1, 9, 0, 0, 5],
  [0, 0, 0, 0, 8, 0, 0, 7, 9]
]

solve_sudoku(board)
print(board)
medium
A. [[5,3,4,6,7,8,9,1,2],[6,7,2,1,9,5,3,4,8],[1,9,8,3,4,2,5,6,7],[8,5,9,7,6,1,4,2,3],[4,2,6,8,5,3,7,9,1],[7,1,3,9,2,4,8,5,6],[9,6,1,5,3,7,2,8,4],[2,8,7,4,1,9,6,3,5],[3,4,5,2,8,6,1,7,9]]
B. [[5,3,0,0,7,0,0,0,0],[6,0,0,1,9,5,0,0,0],[0,9,8,0,0,0,0,6,0],[8,0,0,0,6,0,0,0,3],[4,0,0,8,0,3,0,0,1],[7,0,0,0,2,0,0,0,6],[0,6,0,0,0,0,2,8,0],[0,0,0,4,1,9,0,0,5],[0,0,0,0,8,0,0,7,9]]
C. SyntaxError
D. RuntimeError

Solution

  1. Step 1: Understand solve_sudoku function effect

    The solve_sudoku function fills empty cells (zeros) with correct numbers to complete the Sudoku board.

  2. Step 2: Analyze output after solving

    After solving, the board will be fully filled with valid numbers, matching [[5,3,4,6,7,8,9,1,2],[6,7,2,1,9,5,3,4,8],[1,9,8,3,4,2,5,6,7],[8,5,9,7,6,1,4,2,3],[4,2,6,8,5,3,7,9,1],[7,1,3,9,2,4,8,5,6],[9,6,1,5,3,7,2,8,4],[2,8,7,4,1,9,6,3,5],[3,4,5,2,8,6,1,7,9]]'s completed grid.

  3. Final Answer:

    Completed Sudoku board with all zeros replaced by correct numbers -> Option A

  4. Quick Check:

    Backtracking fills zeros to complete board [OK]
Hint: Backtracking fills zeros to complete Sudoku [OK]
Common Mistakes:
  • Expecting the board to remain unchanged after solve
  • Confusing syntax or runtime errors with correct output
  • Not recognizing that zeros are placeholders for empty cells
4. Identify the error in this backtracking Sudoku solver code snippet:
def solve(board):
    for row in range(9):
        for col in range(9):
            if board[row][col] == 0:
                for num in range(1, 10):
                    if is_safe(board, row, col, num):
                        board[row][col] = num
                        if solve(board):
                            return True
                        board[row][col] = 0
                return False
    return True

# Error: The function is_safe is not defined anywhere.
medium
A. The range for num should be range(0, 9)
B. The board size should be 8 instead of 9
C. The function is_safe is missing, causing NameError
D. The function solve should return False at the end

Solution

  1. Step 1: Check for missing functions

    The code calls is_safe but does not define it, causing a NameError at runtime.

  2. Step 2: Verify other options

    Board size 9 is correct for Sudoku; num range 1-9 is correct; solve returns True at end which is correct.

  3. Final Answer:

    The function is_safe is missing, causing NameError -> Option C

  4. Quick Check:

    Undefined function causes NameError [OK]
Hint: Always define helper functions before calling them [OK]
Common Mistakes:
  • Assuming board size is 8 instead of 9
  • Using wrong range for numbers (should be 1 to 9)
  • Forgetting to return True when solved
5. Given a partially filled Sudoku board, which strategy best improves the efficiency of the backtracking solver?
hard
A. Fill cells randomly without checking constraints
B. Always pick the next empty cell with the fewest possible valid numbers
C. Try numbers in ascending order without checking row or column
D. Restart solving from the first cell after each failed attempt

Solution

  1. Step 1: Understand backtracking optimization

    Choosing the empty cell with the fewest valid options reduces branching and speeds solving.

  2. Step 2: Evaluate other options

    Random filling ignores constraints; trying numbers without checks wastes time; restarting after failure is inefficient.

  3. Final Answer:

    Always pick the next empty cell with the fewest possible valid numbers -> Option B

  4. Quick Check:

    Minimum options first = faster backtracking [OK]
Hint: Choose cell with fewest options to speed solving [OK]
Common Mistakes:
  • Ignoring constraints when filling cells
  • Trying numbers in fixed order without pruning
  • Restarting solving unnecessarily wastes time
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard