Sudoku Solver Using Backtracking in DSA Go - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

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

DSA Go

func isInRow(board [][]int, row int, num int) bool {
    for col := 0; col < 9; col++ {
        if board[row][col] == [1] {
            return true
        }
    }
    return false
}

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

A0

Brow

Ccol

Dnum

Attempts:

3 left

💡 Hint

Common Mistakes

Using the row index instead of the number to check.

Comparing with column index instead of the number.

We check if the number 'num' is present in the given row by comparing each cell in that row to 'num'.

2fill in blank

medium

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

DSA Go

func isInCol(board [][]int, col int, num int) bool {
    for row := 0; row < 9; row++ {
        if board[row][col] == [1] {
            return true
        }
    }
    return false
}

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

Anum

Bcol

Crow

D9

Attempts:

3 left

💡 Hint

Common Mistakes

Using the column index instead of the number to check.

Comparing with row index instead of the number.

We check if the number 'num' is present in the given column by comparing each cell in that column to 'num'.

3fill in blank

hard

Fix the error in the code to check if a number is in the 3x3 box.

DSA Go

func isInBox(board [][]int, startRow int, startCol int, num int) bool {
    for row := 0; row < 3; row++ {
        for col := 0; col < 3; col++ {
            if board[startRow+row][startCol+col] == [1] {
                return true
            }
        }
    }
    return false
}

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

AstartCol

BstartRow

Cnum

Drow

Attempts:

3 left

💡 Hint

Common Mistakes

Using startRow or startCol instead of the number to check.

Comparing with loop variables instead of the number.

We check if the number 'num' is present in the 3x3 box by comparing each cell in that box to 'num'.

4fill in blank

hard

Fill both blanks to check if placing a number is valid in the Sudoku board.

DSA Go

func isValid(board [][]int, row int, col int, num int) bool {
    boxStartRow := row - row % [1]
    boxStartCol := col - col % [2]
    return !isInRow(board, row, num) && !isInCol(board, col, num) && !isInBox(board, boxStartRow, boxStartCol, num)
}

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

A3

B9

C1

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using 9 or 1 instead of 3 for box size.

Using 0 which causes wrong box calculation.

The Sudoku board is divided into 3x3 boxes, so we use 3 to find the starting row and column of the box.

5fill in blank

hard

Fill all three blanks to complete the backtracking solver function.

DSA Go

func solveSudoku(board [][]int) bool {
    for row := 0; row < 9; row++ {
        for col := 0; col < 9; col++ {
            if board[row][col] == [1] {
                for num := 1; num <= [2]; num++ {
                    if isValid(board, row, col, num) {
                        board[row][col] = num
                        if solveSudoku(board) {
                            return true
                        }
                        board[row][col] = [3]
                    }
                }
                return false
            }
        }
    }
    return true
}

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

A0

B9

D1

Attempts:

3 left

💡 Hint

Common Mistakes

Using 1 instead of 0 for empty cells.

Trying numbers beyond 9.

Resetting cell to 1 instead of 0 after backtracking.

Empty cells are marked with 0. We try numbers 1 to 9. If a number doesn't work, reset cell to 0.

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