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

Time Complexity: Sudoku Solver Using Backtracking

O(9^n)

Understanding Time Complexity

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

Specifically, we ask: How does the backtracking solver's work increase with more empty cells?

Scenario Under Consideration

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

func solveSudoku(board [][]byte) bool {
    for i := 0; i < 9; i++ {
        for j := 0; j < 9; j++ {
            if board[i][j] == '.' {
                for c := byte('1'); c <= '9'; c++ {
                    if isValid(board, i, j, c) {
                        board[i][j] = c
                        if solveSudoku(board) {
                            return true
                        }
                        board[i][j] = '.'
                    }
                }
                return false
            }
        }
    }
    return true
}

This code tries digits 1 to 9 in each empty cell, checking if the choice is valid, and uses recursion to fill the next cells.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Trying digits 1 to 9 in each empty cell and recursively solving the rest.
• How many times: Potentially up to 9 choices per empty cell, repeated recursively for all empty cells.

How Execution Grows With Input

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

Empty Cells (n)	Approx. Operations
10	Up to 9^10 (about 3.5 billion) tries
20	Up to 9^20 (very large, trillions of trillions)
30	Up to 9^30 (astronomically large)

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

Final Time Complexity

Time Complexity: O(9^n)

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

Common Mistake

[X] Wrong: "The solver only tries each empty cell once, so time is linear in empty cells."

[OK] Correct: The solver tries many digits per cell and backtracks, so it explores many combinations, not just one pass.

Interview Connect

Understanding this exponential growth helps you explain why backtracking is powerful but can be slow, and shows your grasp of recursive problem solving.

Self-Check

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

Practice

1. What is the main idea behind the backtracking technique used in a Sudoku solver?

easy

A. Use a fixed sequence of numbers without checking

B. Fill the board randomly and check if solved

C. Try placing numbers and undo if they lead to conflicts

D. Only fill cells with one possible number

Solution

1. Step 1: Understand backtracking concept

   Backtracking tries a number in a cell and moves forward if valid, else it undoes (backtracks) and tries another number.

2. Step 2: Compare options

   Only Try placing numbers and undo if they lead to conflicts describes this trial and undo process correctly, others do not represent backtracking.

3. Final Answer:

   Try placing numbers and undo if they lead to conflicts -> Option C

4. Quick Check:

   Backtracking = Try and undo [OK]

Hint: Backtracking means try, check, undo if wrong [OK]

Common Mistakes:

• Thinking backtracking fills randomly without checks
• Assuming backtracking fills only cells with one option
• Confusing backtracking with brute force without undo

2. Which of the following Go function signatures is correct for checking if placing a number is valid in Sudoku?

easy

A. func isValid(board [][]int, row int, col int, num int) bool

B. func isValid(board [9][9]int, num int) int

C. func isValid(board [][]int, num int) string

D. func isValid(board [][]int, row int, col int) bool

Solution

1. Step 1: Identify required parameters for validity check

   We need the board, row, column, and number to check if placing is valid.

2. Step 2: Check return type and parameters

   func isValid(board [][]int, row int, col int, num int) bool has correct parameters and returns bool indicating validity. Others miss parameters or have wrong return types.

3. Final Answer:

   func isValid(board [][]int, row int, col int, num int) bool -> Option A

4. Quick Check:

   Correct params and bool return = func isValid(board [][]int, row int, col int, num int) bool [OK]

Hint: Check all inputs needed: board, row, col, number [OK]

Common Mistakes:

• Missing row or col parameters
• Wrong return type like int or string
• Using fixed size array instead of slice

3. Given the partial Sudoku board below and the code snippet, what will be the output after calling solveSudoku(board)?

board := [][]int{
  {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},
}
solveSudoku(board)
fmt.Println(board)

medium

A. Runtime error due to invalid index

B. Same board with zeros unchanged

C. Partial board with some zeros replaced incorrectly

D. [[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]]

Solution

1. Step 1: Understand solveSudoku function

   It uses backtracking to fill all zeros with valid numbers to complete the Sudoku.

2. Step 2: Check expected output

   The function fills all empty cells correctly, so the printed board is the fully solved Sudoku as in [[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]].

3. Final Answer:

   Fully solved Sudoku board with no zeros -> Option D

4. Quick Check:

   Backtracking solves all zeros = [[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]] [OK]

Hint: Backtracking fills all zeros to complete board [OK]

Common Mistakes:

• Expecting zeros to remain after solve
• Thinking partial fill is output
• Assuming runtime error without index issues

4. Identify the bug in this Go code snippet for Sudoku backtracking solver:

func solve(board [][]int) bool {
  for r := 0; r < 9; r++ {
    for c := 0; c < 9; c++ {
      if board[r][c] == 0 {
        for num := 1; num <= 9; num++ {
          if isValid(board, r, c, num) {
            board[r][c] = num
            if solve(board) {
              return true
            }
            board[r][c] = 0
          }
        }
        return false
      }
    }
  }
  return true
}

medium

A. No bug; code is correct

B. Missing return false if no number fits in a cell

C. Not resetting cell to zero after backtracking

D. Incorrect loop ranges for rows and columns

Solution

1. Step 1: Analyze backtracking logic

   The code tries numbers 1-9 in empty cells, recurses, and resets cell if no solution found.

2. Step 2: Check for missing returns or resets

   It returns false if no number fits, resets cell to zero after backtracking, and loops are correct.

3. Final Answer:

   No bug; code is correct -> Option A

4. Quick Check:

   Backtracking code with proper returns and resets = No bug; code is correct [OK]

Hint: Check if all backtracking steps have return and reset [OK]

Common Mistakes:

• Forgetting to reset cell to zero after failed try
• Missing return false after trying all numbers
• Using wrong loop limits for rows or columns

5. How can you optimize the Sudoku solver to reduce the number of checks during backtracking?

hard

A. Increase board size to 16x16 for more options

B. Use additional data structures to track used numbers in rows, columns, and boxes

C. Only fill cells in the first row and ignore others

D. Try numbers in random order without checking validity

Solution

1. Step 1: Understand optimization needs

   Backtracking checks validity repeatedly; tracking used numbers speeds up validity checks.

2. Step 2: Evaluate options

   Use additional data structures to track used numbers in rows, columns, and boxes uses extra data structures (like arrays or maps) to quickly check if a number is used in row, column, or box, reducing repeated scans.

3. Final Answer:

   Use additional data structures to track used numbers in rows, columns, and boxes -> Option B

4. Quick Check:

   Tracking usage reduces checks = Use additional data structures to track used numbers in rows, columns, and boxes [OK]

Hint: Track used numbers to avoid repeated scanning [OK]

Common Mistakes:

• Trying numbers randomly without checks
• Ignoring cells outside first row
• Increasing board size which complicates solving