Sudoku Solver Using Backtracking in DSA Rust - Execution Trace

Concept Flow - Sudoku Solver Using Backtracking

Start at first empty cell

↓

Try number 1 to 9

↓

Is number valid?

No→Try next number

Yes↓

Place number

↓

Move to next empty cell

↓

Repeat until board full

↓

If stuck, backtrack to previous cell

↓

Try next number there

↓

Continue until solved or no solution

The solver tries numbers 1-9 in empty cells, checks validity, places valid numbers, moves forward, and backtracks if stuck until the board is solved.

Execution Sample

DSA Rust

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

This code tries to fill empty cells with valid numbers recursively, backtracking when no valid number fits.

Execution Table

Step	Operation	Cell (row,col)	Number Tried	Valid?	Action	Board State Snapshot
1	Find empty cell	(0,2)	-	-	Try numbers 1 to 9	[5 3 0 | 0 7 0 | 0 0 0] ...
2	Try number	(0,2)	1	No	Try next number	[5 3 0 | 0 7 0 | 0 0 0] ...
3	Try number	(0,2)	2	No	Try next number	[5 3 0 | 0 7 0 | 0 0 0] ...
4	Try number	(0,2)	3	No	Try next number	[5 3 0 | 0 7 0 | 0 0 0] ...
5	Try number	(0,2)	4	Yes	Place number 4	[5 3 4 | 0 7 0 | 0 0 0] ...
6	Recurse to next empty	(0,3)	-	-	Try numbers 1 to 9	[5 3 4 | 0 7 0 | 0 0 0] ...
7	Try number	(0,3)	1	Yes	Place number 1	[5 3 4 | 1 7 0 | 0 0 0] ...
8	Recurse to next empty	(0,5)	-	-	Try numbers 1 to 9	[5 3 4 | 1 7 0 | 0 0 0] ...
9	Try number	(0,5)	2	No	Try next number	[5 3 4 | 1 7 0 | 0 0 0] ...
10	Try number	(0,5)	3	No	Try next number	[5 3 4 | 1 7 0 | 0 0 0] ...
11	Try number	(0,5)	4	No	Try next number	[5 3 4 | 1 7 0 | 0 0 0] ...
12	Try number	(0,5)	5	No	Try next number	[5 3 4 | 1 7 0 | 0 0 0] ...
13	Try number	(0,5)	6	Yes	Place number 6	[5 3 4 | 1 7 6 | 0 0 0] ...
14	Recurse to next empty	(0,6)	-	-	Try numbers 1 to 9	[5 3 4 | 1 7 6 | 0 0 0] ...
15	Try number	(0,6)	1	No	Try next number	[5 3 4 | 1 7 6 | 0 0 0] ...
16	Try number	(0,6)	2	Yes	Place number 2	[5 3 4 | 1 7 6 | 2 0 0] ...
...	...	...	...	...	...	...
N	Backtrack	(0,6)	No valid number	-	Reset cell to 0 and backtrack	[5 3 4 | 1 7 6 | 0 0 0] ...
N+1	Try next number	(0,5)	8	Yes	Place number 8	[5 3 4 | 1 7 8 | 0 0 0] ...
...	...	...	...	...	...	...
Final	All cells filled	-	-	-	Sudoku solved	[5 3 4 | 1 7 6 | 2 9 8] ...

💡 All cells filled with valid numbers, recursion returns true, puzzle solved

Variable Tracker

Variable	Start	After Step 5	After Step 13	After Step 16	After Backtrack	Final
board	[5 3 0 | 0 7 0 | 0 0 0] ...	[5 3 4 | 0 7 0 | 0 0 0] ...	[5 3 4 | 1 7 6 | 0 0 0] ...	[5 3 4 | 1 7 6 | 2 0 0] ...	[5 3 4 | 1 7 6 | 0 0 0] ...	[5 3 4 | 1 7 6 | 2 9 8] ...
row	0	0	0	0	0	-
col	2	2	5	6	6	-
num	-	4	6	2	-	-

Key Moments - 3 Insights

Why do we reset the cell to 0 when backtracking?

When no valid number fits in a cell (see step N), we reset it to 0 to mark it empty again so previous calls can try other numbers (see execution_table row N).

How does the solver know when the puzzle is solved?

When the solver finds no empty cells in the nested loops (no return false triggered), it returns true (final step), meaning all cells are filled validly.

Why do we try numbers 1 to 9 in order?

Trying numbers in order ensures systematic exploration. If a number is invalid, we try the next (see steps 2-4). This order helps backtracking explore all possibilities.

Visual Quiz - 3 Questions

Look at the execution_table at step 5, what number was placed in cell (0,2)?

A 4

B 3

C 1

D 0

💡 Hint

Check the 'Number Tried' and 'Action' columns at step 5 in execution_table.

At which step does the solver backtrack from cell (0,6)?

A Step 16

B Step N

C Step 13

D Step 5

💡 Hint

Look for the 'Backtrack' operation in execution_table rows.

If the number 4 was invalid at cell (0,2), what would happen next?

A Try number 5 next

B Backtrack immediately

C Try number 3 next

D Try number 1 next

💡 Hint

See steps 2-5 in execution_table where numbers are tried in order.

Concept Snapshot

Sudoku Solver Using Backtracking:
- Find first empty cell
- Try numbers 1 to 9
- Check if number is valid (row, column, 3x3 box)
- If valid, place number and recurse
- If stuck, reset cell and backtrack
- Repeat until board is full and solved

Full Transcript

This visualization shows how a Sudoku solver uses backtracking to fill empty cells. It tries numbers 1 to 9 in each empty cell, checks if the number is valid by Sudoku rules, and places it if valid. Then it moves to the next empty cell recursively. If no number fits, it backtracks by resetting the cell to empty and tries other numbers in previous cells. This continues until the entire board is filled correctly. The execution table tracks each step, showing which number is tried, if it is valid, and the board state. The variable tracker shows how the board and pointers change. Key moments clarify why backtracking resets cells and how the solver knows when it is done. The quiz tests understanding of these steps.

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