Sudoku Solver Using Backtracking in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Sudoku Board After One Step of Backtracking

Given the initial Sudoku board and one step of the backtracking solver, what is the state of the board after placing the first valid number in the first empty cell?

DSA Rust

let mut board = vec![
    vec![5, 3, 0, 0, 7, 0, 0, 0, 0],
    vec![6, 0, 0, 1, 9, 5, 0, 0, 0],
    vec![0, 9, 8, 0, 0, 0, 0, 6, 0],
    vec![8, 0, 0, 0, 6, 0, 0, 0, 3],
    vec![4, 0, 0, 8, 0, 3, 0, 0, 1],
    vec![7, 0, 0, 0, 2, 0, 0, 0, 6],
    vec![0, 6, 0, 0, 0, 0, 2, 8, 0],
    vec![0, 0, 0, 4, 1, 9, 0, 0, 5],
    vec![0, 0, 0, 0, 8, 0, 0, 7, 9],
];
// After one step of backtracking, the first empty cell (0,2) is filled with 1

A [[5,3,4,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]]

B [[5,3,2,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 [[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]]

D [[5,3,1,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]]

💡 Hint

Look for the first empty cell and try numbers 1 to 9 to find the first valid placement.

The first empty cell is at row 0, column 2. The number 1 is the first valid number that can be placed there without breaking Sudoku rules.

🧠 Conceptual

intermediate

Understanding Backtracking in Sudoku Solver

Which of the following best describes the role of backtracking in solving Sudoku puzzles?

A Backtracking solves Sudoku by sorting rows and columns to find the missing numbers.

B Backtracking tries numbers in empty cells and reverts if a conflict arises, exploring all possibilities systematically.

C Backtracking randomly fills cells and hopes to find a solution by chance.

D Backtracking fills all empty cells with the number 1 and then adjusts the board to fit Sudoku rules.

💡 Hint

Think about how the solver tries and undoes moves to find a valid solution.

Backtracking is a method where the solver tries a number in an empty cell, checks if it fits, and if not, it reverts and tries another number, exploring all options systematically.

🔧 Debug

advanced

Identify the Error in Sudoku Validity Check Function

Consider this Rust function snippet that checks if placing a number in a cell is valid. What error will this code cause?

DSA Rust

fn is_valid(board: &Vec<Vec<u8>>, row: usize, col: usize, num: u8) -> bool {
    for i in 0..9 {
        if board[row][i] == num || board[i][col] == num {
            return false;
        }
    }
    let box_row = row / 3 * 3;
    let box_col = col / 3 * 3;
    for i in box_row..box_row + 3 {
        for j in box_col..box_col + 3 {
            if board[i][j] == num {
                return false;
            }
        }
    }
    true
}

// Usage example: is_valid(&board, 0, 0, 5);

A No error; function works correctly for all valid inputs

B Type mismatch error due to incorrect vector type

C Index out of bounds panic when row or col is 9 or more

D Infinite loop due to incorrect for loop ranges

💡 Hint

Check the ranges and indexing carefully.

The function correctly checks the row, column, and 3x3 box for the number. The ranges are valid and indexing is safe for inputs 0 to 8.

❓ Predict Output

advanced

Final Solved Sudoku Board Output

What is the final solved Sudoku board after running a correct backtracking solver on this initial board?

DSA Rust

let board = vec![
    vec![5, 3, 0, 0, 7, 0, 0, 0, 0],
    vec![6, 0, 0, 1, 9, 5, 0, 0, 0],
    vec![0, 9, 8, 0, 0, 0, 0, 6, 0],
    vec![8, 0, 0, 0, 6, 0, 0, 0, 3],
    vec![4, 0, 0, 8, 0, 3, 0, 0, 1],
    vec![7, 0, 0, 0, 2, 0, 0, 0, 6],
    vec![0, 6, 0, 0, 0, 0, 2, 8, 0],
    vec![0, 0, 0, 4, 1, 9, 0, 0, 5],
    vec![0, 0, 0, 0, 8, 0, 0, 7, 9],
];
// After solving, the board is:

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,1,6,7,8,9,2,4],[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,4,5,3,7,2,8,1],[2,8,7,4,1,9,6,3,5],[3,4,5,2,8,6,1,7,9]]

C ]]9,7,1,6,8,2,5,4,3[,]5,3,6,9,1,4,7,8,2[,]4,8,2,7,3,5,1,6,9[,]6,5,8,4,2,9,3,1,7[,]1,9,7,3,5,8,6,2,4[,]3,2,4,1,6,7,9,5,8[,]7,6,5,2,4,3,8,9,1[,]8,4,3,5,9,1,2,7,6[,]2,1,9,8,7,6,4,3,5[[

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,0]]

💡 Hint

Check carefully the known solved Sudoku solution for this puzzle.

Option A matches the known correct solved Sudoku board for the given initial puzzle. Option A has a wrong number in the first row last column, B has misplaced numbers, and D has a zero in the last cell.

🚀 Application

expert

Time Complexity of Sudoku Solver Using Backtracking

What is the worst-case time complexity of a backtracking Sudoku solver for a 9x9 board?

A O(1) because Sudoku puzzles have fixed size and are solved instantly

B O(81^9) because each number 1-9 is tried in all 81 cells

C O(9^(81)) because each of the 81 cells can have up to 9 possibilities

D O(9*81) because it tries 9 numbers for each of the 81 cells once

💡 Hint

Consider how many choices are tried for each empty cell in the worst case.

In the worst case, the solver tries all 9 numbers for each of the 81 cells, leading to O(9^81) complexity. This is exponential and explains why backtracking can be slow for hard puzzles.

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