Sudoku Solver Using Backtracking in DSA Rust - 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 does the backtracking method's work grow with the number of empty cells?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

fn solve_sudoku(board: &mut [[u8; 9]; 9]) -> bool {
    for row in 0..9 {
        for col in 0..9 {
            if board[row][col] == 0 {
                for num in 1..=9 {
                    if is_valid(board, row, col, num) {
                        board[row][col] = num;
                        if solve_sudoku(board) {
                            return true;
                        }
                        board[row][col] = 0;
                    }
                }
                return false;
            }
        }
    }
    true
}

This code tries to fill empty cells (marked 0) with numbers 1 to 9, checking if the number fits rules, and uses backtracking to find a solution.

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 depending on puzzle difficulty.

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.21e19 tries
30	Up to 9^30 ≈ 1.21e28 tries

Pattern observation: The work grows exponentially with the number of empty cells, making the problem much harder as empties increase.

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 empty cell can try up to 9 numbers recursively.

Common Mistake

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

[OK] Correct: The solver tries many combinations recursively, so the total tries multiply, not just add, leading to exponential growth.

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 how recursive search explores many possibilities and why complexity matters in real problems.

Self-Check

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

Practice

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 fill the Sudoku grid randomly without checking rules

C. To sort the numbers in each row before placing them

D. To try possible numbers and undo choices if they lead to conflicts

Solution

1. Step 1: Understand backtracking role

   Backtracking tries placing numbers and removes them if they cause conflicts.

2. Step 2: Compare options

   Only To try possible numbers and undo choices if they lead to conflicts describes this trial and undo process correctly.

3. Final Answer:

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

4. Quick Check:

   Backtracking = Try and undo [OK]

Hint: Backtracking means try and undo wrong moves [OK]

Common Mistakes:

• Thinking backtracking fills randomly
• Confusing backtracking with sorting
• Ignoring the undo step in backtracking

2. Which Rust syntax correctly defines a function to check if a number can be placed in a Sudoku cell?

easy

A. fn can_place(board: &[[u8; 9]; 9], row: usize, col: usize, num: u8) -> bool { /* code */ }

B. function can_place(board, row, col, num) { /* code */ }

C. def can_place(board, row, col, num): return True

D. let can_place = (board, row, col, num) => { /* code */ }

Solution

1. Step 1: Identify Rust function syntax

   Rust functions start with fn, specify parameter types and return type.

2. Step 2: Match options to Rust syntax

   Only fn can_place(board: &[[u8; 9]; 9], row: usize, col: usize, num: u8) -> bool { /* code */ } uses fn and types correctly.

3. Final Answer:

   fn can_place(board: &[[u8; 9]; 9], row: usize, col: usize, num: u8) -> bool { /* code */ } -> Option A

4. Quick Check:

   Rust fn syntax = fn can_place(board: &[[u8; 9]; 9], row: usize, col: usize, num: u8) -> bool { /* code */ } [OK]

Hint: Rust functions start with fn and specify types [OK]

Common Mistakes:

• Using JavaScript or Python syntax in Rust
• Omitting parameter types
• Not specifying return type

3. Given this partial Rust code snippet for Sudoku backtracking, what will be printed?

let mut board = [[0u8; 9]; 9];
board[0][0] = 5;
println!("{}", board[0][0]);

medium

A. 0

B. 5

C. Error

D. None

Solution

1. Step 1: Understand board initialization

   The board is a 9x9 grid initialized with zeros.

2. Step 2: Check assignment and print

   board[0][0] is set to 5, so printing it outputs 5.

3. Final Answer:

   5 -> Option B

4. Quick Check:

   board[0][0] = 5 prints 5 [OK]

Hint: Assigned value prints, not initial zero [OK]

Common Mistakes:

• Assuming default zero prints after assignment
• Confusing index order
• Expecting error due to mutability

4. Identify the bug in this Rust function snippet for Sudoku backtracking:

fn solve(board: &mut [[u8; 9]; 9]) -> bool {
  for row in 0..9 {
    for col in 0..9 {
      if board[row][col] == 0 {
        for num in 1..9 {
          if can_place(board, row, col, num) {
            board[row][col] = num;
            if solve(board) {
              return true;
            }
            board[row][col] = 0;
          }
        }
        return false;
      }
    }
  }
  true
}

medium

A. The function never returns true when the board is full

B. The board parameter should not be mutable

C. The range 1..9 excludes 9, should be 1..10

D. The nested loops should be swapped

Solution

1. Step 1: Check number range in loop

   Rust range 1..9 iterates from 1 to 8 (exclusive end), missing 9 which is required for Sudoku.

2. Step 2: Compare options

   Only The range 1..9 excludes 9, should be 1..10 correctly identifies the range bug and suggests 1..10 (1 through 9).

3. Step 3: Verify other options

   A: Incorrect; returns true after loops if no empty cells. C: Wrong; mutable needed for changes. D: Unnecessary; order is fine.

4. Final Answer:

   The range 1..9 excludes 9, should be 1..10 -> Option C

5. Quick Check:

   Rust 1..9 = 1-8, use 1..10 for 1-9 [OK]

Hint: Remember Rust 1..10 excludes 10, includes 9 [OK]

Common Mistakes:

• Thinking 1..10 includes 10
• Not marking board mutable
• Swapping loops unnecessarily

5. How does the backtracking algorithm ensure that the Sudoku solution is valid and complete?

hard

A. By placing numbers only if they don't violate Sudoku rules and backtracking on conflicts until the board is full

B. By filling all cells with random numbers and checking at the end

C. By sorting each row and column before placing numbers

D. By using a queue to store all possible numbers for each cell

Solution

1. Step 1: Understand backtracking validation

   The algorithm tries numbers only if they don't break Sudoku rules (row, column, box).

2. Step 2: Understand backtracking completeness

   If a number leads to conflict later, it removes it (backtracks) and tries another number until the board is full.

3. Step 3: Eliminate wrong options

   Options B, C, and D describe incorrect or unrelated methods.

4. Final Answer:

   By placing numbers only if they don't violate Sudoku rules and backtracking on conflicts until the board is full -> Option A

5. Quick Check:

   Backtracking = Try-valid-undo until complete [OK]

Hint: Backtracking tries valid numbers, undoes on conflict [OK]

Common Mistakes:

• Thinking random fill works
• Confusing sorting with validation
• Using queues instead of recursion