Sudoku Solver Using Backtracking in DSA Rust - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to check if a number is already in the given row.

DSA Rust

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

Drag options to blanks, or click blank then click option'

Arow

Bcol

Cnum

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using the wrong variable like 'row' or 'col' instead of 'num'.

Comparing with 0 instead of the number.

We compare each cell in the row with the number we want to place, so the correct variable is 'num'.

2fill in blank

medium

Complete the code to check if a number is already in the given column.

DSA Rust

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

Drag options to blanks, or click blank then click option'

Anum

B9

Crow

Dcol

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'row' or 'col' instead of 'num' in the comparison.

Comparing with a fixed number like 9.

We compare each cell in the column with the number 'num' to check if it is already present.

3fill in blank

hard

Fix the error in the code to check if a number is in the 3x3 box starting at (box_start_row, box_start_col).

DSA Rust

fn used_in_box(board: &[[u8; 9]; 9], box_start_row: usize, box_start_col: usize, num: u8) -> bool {
    for row in box_start_row..box_start_row + 3 {
        for col in box_start_col..box_start_col + 3 {
            if board[row][col] == [1] {
                return true;
            }
        }
    }
    false
}

Drag options to blanks, or click blank then click option'

Acol

Bbox_start_row

Crow

Dnum

Attempts:

3 left

💡 Hint

Common Mistakes

Comparing with 'row' or 'col' instead of 'num'.

Using 'box_start_row' instead of 'num'.

We want to check if the number 'num' is present in the 3x3 box, so we compare with 'num'.

4fill in blank

hard

Fill both blanks to complete the function that checks if it is safe to place a number at (row, col).

DSA Rust

fn is_safe(board: &[[u8; 9]; 9], row: usize, col: usize, num: u8) -> bool {
    !used_in_row(board, row, [1]) &&
    !used_in_col(board, col, [2]) &&
    !used_in_box(board, row - row % 3, col - col % 3, num)
}

Drag options to blanks, or click blank then click option'

Anum

Brow

Ccol

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Passing 'row' or 'col' instead of 'num' to the functions.

Using 0 instead of 'num'.

We check if 'num' is not used in the row and column, so both blanks should be 'num'.

5fill in blank

hard

Fill all three blanks to complete the backtracking function that solves the Sudoku board.

DSA Rust

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_safe(board, row, col, [1]) {
                        board[row][col] = [2];
                        if solve_sudoku(board) {
                            return true;
                        }
                        board[row][col] = [3];
                    }
                }
                return false;
            }
        }
    }
    true
}

Drag options to blanks, or click blank then click option'

Anum

C0

Drow

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong variables instead of 'num' for placement.

Not resetting the cell to 0 during backtracking.

We try placing 'num' in the cell, then backtrack by resetting to 0 if needed.

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