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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Sudoku Board After One Backtracking Step

Given the initial Sudoku board and one step of backtracking filling the first empty cell, what is the board state?

DSA Go

package main

import "fmt"

func main() {
    board := [][]int{
        {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},
    }

    // Fill first empty cell (row 0, col 2) with 4 (valid number)
    board[0][2] = 4

    for _, row := range board {
        fmt.Println(row)
    }
}

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

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 9 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 fill it with the smallest valid number.

The first empty cell is at row 0, column 2. The smallest valid number that fits Sudoku rules here is 4.

🧠 Conceptual

intermediate

Understanding Backtracking in Sudoku Solver

What is the main reason backtracking is used in Sudoku solving algorithms?

A To randomly fill the board and check if it is solved

B To sort the numbers in each row before placing them

C To try all possible numbers in empty cells and backtrack when a conflict occurs

D To use a queue to process cells in order

💡 Hint

Think about how the algorithm handles wrong guesses.

Backtracking tries numbers in empty cells one by one and goes back if a number causes a conflict, ensuring all possibilities are explored systematically.

🔧 Debug

advanced

Identify the Error in Sudoku Validity Check

What error does the following Go function cause when checking if a number can be placed in a Sudoku cell?

DSA Go

func isValid(board [][]int, row, col, num int) bool {
    for i := 0; i < 9; i++ {
        if board[row][i] == num {
            return false
        }
        if board[i][col] == num {
            return false
        }
    }
    startRow := row / 3 * 3
    startCol := col / 3 * 3
    for i := startRow; i < startRow+3; i++ {
        for j := startCol; j < startCol+3; j++ {
            if board[i][j] == num {
                return false
            }
        }
    }
    return true
}

// Usage: isValid(board, 0, 0, 5)

A Index out of range error when row or col is 9

B No error; function works correctly

C Function returns false positives for valid placements

D Function does not check the 3x3 subgrid correctly

💡 Hint

Check the loops and conditions carefully.

The function correctly checks the row, column, and 3x3 subgrid for the number's presence and returns true only if the number can be placed.

❓ Predict Output

advanced

Final Sudoku Board After Complete Backtracking Solve

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

DSA Go

package main

import "fmt"

func main() {
    board := [][]int{
        {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},
    }

    // Assume solveSudoku(board) fills the board correctly
    solved := [][]int{
        {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},
    }

    for _, row := range solved {
        fmt.Println(row)
    }
}

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

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

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

💡 Hint

Look for the fully completed board with no zeros and valid Sudoku solution.

Option A shows the fully solved Sudoku board with all cells filled correctly according to Sudoku rules.

🚀 Application

expert

Time Complexity of Sudoku Solver Using Backtracking

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

A O(1) because Sudoku size is fixed

B O(81^9) because 81 cells raised to 9 possibilities

C O(9*81) because 9 numbers checked for each cell

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

💡 Hint

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

In the worst case, the solver tries up to 9 numbers for each of the 81 cells, leading to O(9^81) complexity.

Practice

1. What is the main idea behind the backtracking technique used in a Sudoku solver?

easy

A. Use a fixed sequence of numbers without checking

B. Fill the board randomly and check if solved

C. Try placing numbers and undo if they lead to conflicts

D. Only fill cells with one possible number

Solution

1. Step 1: Understand backtracking concept

   Backtracking tries a number in a cell and moves forward if valid, else it undoes (backtracks) and tries another number.

2. Step 2: Compare options

   Only Try placing numbers and undo if they lead to conflicts describes this trial and undo process correctly, others do not represent backtracking.

3. Final Answer:

   Try placing numbers and undo if they lead to conflicts -> Option C

4. Quick Check:

   Backtracking = Try and undo [OK]

Hint: Backtracking means try, check, undo if wrong [OK]

Common Mistakes:

• Thinking backtracking fills randomly without checks
• Assuming backtracking fills only cells with one option
• Confusing backtracking with brute force without undo

2. Which of the following Go function signatures is correct for checking if placing a number is valid in Sudoku?

easy

A. func isValid(board [][]int, row int, col int, num int) bool

B. func isValid(board [9][9]int, num int) int

C. func isValid(board [][]int, num int) string

D. func isValid(board [][]int, row int, col int) bool

Solution

1. Step 1: Identify required parameters for validity check

   We need the board, row, column, and number to check if placing is valid.

2. Step 2: Check return type and parameters

   func isValid(board [][]int, row int, col int, num int) bool has correct parameters and returns bool indicating validity. Others miss parameters or have wrong return types.

3. Final Answer:

   func isValid(board [][]int, row int, col int, num int) bool -> Option A

4. Quick Check:

   Correct params and bool return = func isValid(board [][]int, row int, col int, num int) bool [OK]

Hint: Check all inputs needed: board, row, col, number [OK]

Common Mistakes:

• Missing row or col parameters
• Wrong return type like int or string
• Using fixed size array instead of slice

3. Given the partial Sudoku board below and the code snippet, what will be the output after calling solveSudoku(board)?

board := [][]int{
  {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},
}
solveSudoku(board)
fmt.Println(board)

medium

A. Runtime error due to invalid index

B. Same board with zeros unchanged

C. Partial board with some zeros replaced incorrectly

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

Solution

1. Step 1: Understand solveSudoku function

   It uses backtracking to fill all zeros with valid numbers to complete the Sudoku.

2. Step 2: Check expected output

   The function fills all empty cells correctly, so the printed board is the fully solved Sudoku as in [[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]].

3. Final Answer:

   Fully solved Sudoku board with no zeros -> Option D

4. Quick Check:

   Backtracking solves all zeros = [[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]] [OK]

Hint: Backtracking fills all zeros to complete board [OK]

Common Mistakes:

• Expecting zeros to remain after solve
• Thinking partial fill is output
• Assuming runtime error without index issues

4. Identify the bug in this Go code snippet for Sudoku backtracking solver:

func solve(board [][]int) bool {
  for r := 0; r < 9; r++ {
    for c := 0; c < 9; c++ {
      if board[r][c] == 0 {
        for num := 1; num <= 9; num++ {
          if isValid(board, r, c, num) {
            board[r][c] = num
            if solve(board) {
              return true
            }
            board[r][c] = 0
          }
        }
        return false
      }
    }
  }
  return true
}

medium

A. No bug; code is correct

B. Missing return false if no number fits in a cell

C. Not resetting cell to zero after backtracking

D. Incorrect loop ranges for rows and columns

Solution

1. Step 1: Analyze backtracking logic

   The code tries numbers 1-9 in empty cells, recurses, and resets cell if no solution found.

2. Step 2: Check for missing returns or resets

   It returns false if no number fits, resets cell to zero after backtracking, and loops are correct.

3. Final Answer:

   No bug; code is correct -> Option A

4. Quick Check:

   Backtracking code with proper returns and resets = No bug; code is correct [OK]

Hint: Check if all backtracking steps have return and reset [OK]

Common Mistakes:

• Forgetting to reset cell to zero after failed try
• Missing return false after trying all numbers
• Using wrong loop limits for rows or columns

5. How can you optimize the Sudoku solver to reduce the number of checks during backtracking?

hard

A. Increase board size to 16x16 for more options

B. Use additional data structures to track used numbers in rows, columns, and boxes

C. Only fill cells in the first row and ignore others

D. Try numbers in random order without checking validity

Solution

1. Step 1: Understand optimization needs

   Backtracking checks validity repeatedly; tracking used numbers speeds up validity checks.

2. Step 2: Evaluate options

   Use additional data structures to track used numbers in rows, columns, and boxes uses extra data structures (like arrays or maps) to quickly check if a number is used in row, column, or box, reducing repeated scans.

3. Final Answer:

   Use additional data structures to track used numbers in rows, columns, and boxes -> Option B

4. Quick Check:

   Tracking usage reduces checks = Use additional data structures to track used numbers in rows, columns, and boxes [OK]

Hint: Track used numbers to avoid repeated scanning [OK]

Common Mistakes:

• Trying numbers randomly without checks
• Ignoring cells outside first row
• Increasing board size which complicates solving