Sudoku Solver Using Backtracking in DSA Rust - Build from Scratch

Sudoku Solver Using Backtracking

📖 Scenario: You have a Sudoku puzzle represented as a 9x9 grid. Some cells are filled with numbers from 1 to 9, and others are empty (represented by 0). Your task is to write a program that fills the empty cells so that every row, every column, and every 3x3 box contains all digits from 1 to 9 exactly once.This is a classic puzzle-solving problem that can be solved using a method called backtracking, which tries numbers one by one and backtracks if a number doesn't fit.

🎯 Goal: Build a Sudoku solver in Rust that uses backtracking to fill the empty cells of the Sudoku board correctly.

📋 What You'll Learn

Create a 9x9 Sudoku board as a 2D array with given initial values

Write a function to check if placing a number in a specific cell is valid

Implement the backtracking algorithm to solve the Sudoku

Print the solved Sudoku board in a readable format

💡 Why This Matters

🌍 Real World

Sudoku solving algorithms are examples of constraint satisfaction problems, which appear in scheduling, planning, and resource allocation tasks.

💼 Career

Understanding backtracking and constraint checking is important for software engineers working on optimization problems, game development, and AI.

1

Create the Sudoku board

Create a 9x9 two-dimensional array called board with the exact values below, where 0 represents an empty cell:

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

DSA Rust

# Create the 9x9 Sudoku board with the given values
# Your code here

Hint

Use a 2D array with 9 rows and 9 columns. Each inner array represents a row.

2

Write a function to check if a number can be placed

Add a function called is_valid that takes board as a mutable reference, row and col as usize, and num as i32. It should return true if placing num at board[row][col] does not break Sudoku rules (no duplicates in the same row, column, or 3x3 box), otherwise false.

DSA Rust

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

    // Add the is_valid function below
    // Your code here
}

Hint

Check the row, column, and 3x3 box for the number. Return false if found, true otherwise.

3

Implement the backtracking solver function

Add a function called solve_sudoku that takes board as a mutable reference. It should find an empty cell (0), try numbers 1 to 9, check validity using is_valid, place the number if valid, and recursively call itself. If no number fits, reset the cell to 0 and backtrack. Return true if solved, false otherwise.

DSA Rust

fn is_valid(board: &[[i32; 9]; 9], row: usize, col: usize, num: i32) -> bool {
    // existing code
}

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

    // Add the solve_sudoku function below
    // Your code here
}

Hint

Try numbers 1 to 9 in empty cells, use recursion to solve, and backtrack if needed.

4

Print the solved Sudoku board

Call solve_sudoku with board. Then print the board row by row, with numbers separated by spaces. Use a for loop with variable row to iterate over board, and print each row's numbers separated by spaces.

DSA Rust

fn is_valid(board: &[[i32; 9]; 9], row: usize, col: usize, num: i32) -> bool {
    // existing code
}

fn solve_sudoku(board: &mut [[i32; 9]; 9]) -> bool {
    // existing code
}

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

    solve_sudoku(&mut board);

    // Print the solved board below
    // Your code here
}

Hint

Use nested loops to print each row and each number separated by spaces. Use print!("{} ", num) for numbers and println!() after each row.

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