Sudoku Solver Using Backtracking in DSA Rust

Mental Model

Try placing numbers one by one in empty cells and backtrack if a number causes a conflict.

Analogy: Like trying keys on a locked door one by one, and if a key doesn't fit, you go back and try another key until the door opens.

5 3 _ | _ 7 _ | _ _ _
6 _ _ | 1 9 5 | _ _ _
_ 9 8 | _ _ _ | _ 6 _
------+-------+------
8 _ _ | _ 6 _ | _ _ 3
4 _ _ | 8 _ 3 | _ _ 1
7 _ _ | _ 2 _ | _ _ 6
------+-------+------
_ 6 _ | _ _ _ | 2 8 _
_ _ _ | 4 1 9 | _ _ 5
_ _ _ | _ 8 _ | _ 7 9
↑ empty cells marked as _

Dry Run Walkthrough

Input: Partially filled 9x9 Sudoku board with empty cells marked as 0

Goal: Fill all empty cells with digits 1-9 so that each row, column, and 3x3 box contains all digits without repetition

Step 1: Find first empty cell at row 0, column 2; try number 1

5 3 1 | _ 7 _ | _ _ _
6 _ _ | 1 9 5 | _ _ _
_ 9 8 | _ _ _ | _ 6 _
------+-------+------
8 _ _ | _ 6 _ | _ _ 3
4 _ _ | 8 _ 3 | _ _ 1
7 _ _ | _ 2 _ | _ _ 6
------+-------+------
_ 6 _ | _ _ _ | 2 8 _
_ _ _ | 4 1 9 | _ _ 5
_ _ _ | _ 8 _ | _ 7 9

Why: Try smallest number first to find a valid placement

Step 2: Check if 1 is valid in row 0, column 2; it's valid, so place it

5 3 1 | _ 7 _ | _ _ _
6 _ _ | 1 9 5 | _ _ _
_ 9 8 | _ _ _ | _ 6 _
------+-------+------
8 _ _ | _ 6 _ | _ _ 3
4 _ _ | 8 _ 3 | _ _ 1
7 _ _ | _ 2 _ | _ _ 6
------+-------+------
_ 6 _ | _ _ _ | 2 8 _
_ _ _ | 4 1 9 | _ _ 5
_ _ _ | _ 8 _ | _ 7 9

Why: Number 1 does not violate Sudoku rules here

Step 3: Move to next empty cell at row 0, column 3; try number 1

5 3 1 | 1 7 _ | _ _ _
6 _ _ | 1 9 5 | _ _ _
_ 9 8 | _ _ _ | _ 6 _
------+-------+------
8 _ _ | _ 6 _ | _ _ 3
4 _ _ | 8 _ 3 | _ _ 1
7 _ _ | _ 2 _ | _ _ 6
------+-------+------
_ 6 _ | _ _ _ | 2 8 _
_ _ _ | 4 1 9 | _ _ 5
_ _ _ | _ 8 _ | _ 7 9

Why: Try placing 1 again in next empty cell

Step 4: Check if 1 is valid in row 0, column 3; it's invalid (1 already in row), try 2

5 3 1 | _ 7 _ | _ _ _
6 _ _ | 1 9 5 | _ _ _
_ 9 8 | _ _ _ | _ 6 _
------+-------+------
8 _ _ | _ 6 _ | _ _ 3
4 _ _ | 8 _ 3 | _ _ 1
7 _ _ | _ 2 _ | _ _ 6
------+-------+------
_ 6 _ | _ _ _ | 2 8 _
_ _ _ | 4 1 9 | _ _ 5
_ _ _ | _ 8 _ | _ 7 9

Why: Backtrack because 1 conflicts; try next number

Step 5: Try number 2 in row 0, column 3; check validity; valid, place 2

5 3 1 | 2 7 _ | _ _ _
6 _ _ | 1 9 5 | _ _ _
_ 9 8 | _ _ _ | _ 6 _
------+-------+------
8 _ _ | _ 6 _ | _ _ 3
4 _ _ | 8 _ 3 | _ _ 1
7 _ _ | _ 2 _ | _ _ 6
------+-------+------
_ 6 _ | _ _ _ | 2 8 _
_ _ _ | 4 1 9 | _ _ 5
_ _ _ | _ 8 _ | _ 7 9

Why: Number 2 fits without conflicts

Step 6: Continue this process for all empty cells, backtracking when no number fits

Fully filled valid Sudoku board

Why: Backtracking ensures all possibilities are explored to find a solution

Result:

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

Annotated Code

DSA Rust

fn is_valid(board: &[[u8; 9]; 9], row: usize, col: usize, num: u8) -> bool {
    for x in 0..9 {
        if board[row][x] == num || board[x][col] == num {
            return false; // number conflicts in row or column
        }
    }
    let box_row_start = (row / 3) * 3;
    let box_col_start = (col / 3) * 3;
    for r in box_row_start..box_row_start + 3 {
        for c in box_col_start..box_col_start + 3 {
            if board[r][c] == num {
                return false; // number conflicts in 3x3 box
            }
        }
    }
    true // no conflicts found
}

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; // place number
                        if solve_sudoku(board) {
                            return true; // solved
                        }
                        board[row][col] = 0; // backtrack
                    }
                }
                return false; // no valid number found, trigger backtrack
            }
        }
    }
    true // all cells filled correctly
}

fn print_board(board: &[[u8; 9]; 9]) {
    for (i, row) in board.iter().enumerate() {
        if i % 3 == 0 && i != 0 {
            println!("------+-------+------");
        }
        for (j, &val) in row.iter().enumerate() {
            if j % 3 == 0 && j != 0 {
                print!("| ");
            }
            if val == 0 {
                print!("_ ");
            } else {
                print!("{} ", val);
            }
        }
        println!();
    }
}

fn main() {
    let mut 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],
    ];
    println!("Initial Sudoku board:");
    print_board(&board);
    if solve_sudoku(&mut board) {
        println!("\nSolved Sudoku board:");
        print_board(&board);
    } else {
        println!("No solution exists");
    }
}

for x in 0..9 { if board[row][x] == num || board[x][col] == num { return false; } }

check row and column for conflicts

for r in box_row_start..box_row_start + 3 { for c in box_col_start..box_col_start + 3 { if board[r][c] == num { return false; } } }

check 3x3 box for conflicts

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; }

try numbers 1-9 in empty cell, backtrack if needed

true

all cells filled correctly, puzzle solved

Output

Initial Sudoku board:

5 3 _ | _ 7 _ | _ _ _ 

6 _ _ | 1 9 5 | _ _ _ 

_ 9 8 | _ _ _ | _ 6 _ 

------+-------+------

8 _ _ | _ 6 _ | _ _ 3 

4 _ _ | 8 _ 3 | _ _ 1 

7 _ _ | _ 2 _ | _ _ 6 

------+-------+------

_ 6 _ | _ _ _ | 2 8 _ 

_ _ _ | 4 1 9 | _ _ 5 

_ _ _ | _ 8 _ | _ 7 9 



Solved Sudoku board:

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 

Complexity Analysis

Time: O(9^(n)) where n is number of empty cells, because each empty cell tries up to 9 numbers with backtracking

Space: O(n) for recursion stack where n is number of empty cells

vs Alternative: Brute force tries all combinations without pruning; backtracking prunes invalid paths early, reducing search space

Edge Cases

Empty board (all zeros)

Solver tries all possibilities; may take longer but still works

DSA Rust

if board[row][col] == 0 { for num in 1..=9 { ... } }

Already solved board

Solver quickly returns true without changes

DSA Rust

true // all cells filled correctly

No solution board (conflicting clues)

Solver returns false after exploring all options

DSA Rust

return false; // no valid number found, trigger backtrack

When to Use This Pattern

When you see a problem requiring filling a grid with constraints and trial/error, reach for backtracking because it tries options and undoes wrong choices systematically.

Common Mistakes

Mistake: Not checking 3x3 box conflicts, leading to invalid solutions
Fix: Add nested loops to check the 3x3 box for the number before placing

Mistake: Not resetting cell to zero when backtracking, causing stuck states
Fix: Set board[row][col] = 0 after recursive call fails to backtrack properly

Summary

It fills empty Sudoku cells by trying numbers and backtracking on conflicts.

Use it when you need to solve puzzles with constraints and multiple choices.

The key insight is to try a choice, move forward, and undo if it leads to a dead end.

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