Sudoku Solver Using Backtracking in DSA Go - Execution Trace

Concept Flow - Sudoku Solver Using Backtracking

Start at first empty cell

↓

Try number 1 to 9

↓

Is number valid?

No→Try next number

Yes↓

Place number

↓

Move to next empty cell

↓

All cells filled?

Yes→Solved

No↓

Backtrack if stuck

↓

Remove number, try next

↩Back to Try number 1 to 9

The solver tries numbers 1 to 9 in each empty cell, checks validity, places a number if valid, moves forward, and backtracks if stuck until the puzzle is solved.

Execution Sample

DSA Go

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
}

This code tries to fill empty cells (0) with numbers 1-9, checking validity, recursing forward, and backtracking if needed.

Execution Table

Step	Operation	Cell (row,col)	Number Tried	Valid?	Action	Board State Snapshot
1	Find empty cell	(0,0)	-	-	Empty cell found	[0 0 3 ...] (row 0 snapshot)
2	Try number	(0,0)	1	No	Try next number	[0 0 3 ...]
3	Try number	(0,0)	2	No	Try next number	[0 0 3 ...]
4	Try number	(0,0)	3	Yes	Place number 3	[3 0 3 ...]
5	Recurse solve	-	-	-	Move to next empty cell	[3 0 3 ...]
6	Find empty cell	(0,1)	-	-	Empty cell found	[3 0 3 ...]
7	Try number	(0,1)	1	Yes	Place number 1	[3 1 3 ...]
8	Recurse solve	-	-	-	Move to next empty cell	[3 1 3 ...]
9	Find empty cell	(0,2)	-	-	Cell already filled	[3 1 3 ...]
10	Find empty cell	(0,3)	-	-	Empty cell found	[3 1 3 0 ...]
11	Try number	(0,3)	1	No	Try next number	[3 1 3 0 ...]
12	Try number	(0,3)	2	Yes	Place number 2	[3 1 3 2 ...]
13	Recurse solve	-	-	-	Move to next empty cell	[3 1 3 2 ...]
14	Backtrack	(0,3)	No valid number	-	Remove number, backtrack	[3 1 3 0 ...]
15	Try number	(0,1)	2	No	Try next number	[3 0 3 ...]
16	Try number	(0,1)	3	No	Try next number	[3 0 3 ...]
17	Try number	(0,1)	4	Yes	Place number 4	[3 4 3 ...]
18	Recurse solve	-	-	-	Move forward	[3 4 3 ...]
...	...	...	...	...	...	...
N	All cells filled	-	-	-	Puzzle solved	[Full solved board]

💡 All cells filled with valid numbers, puzzle solved.

Variable Tracker

Variable	Start	After Step 4	After Step 7	After Step 12	After Step 14	Final
board[0][0]	0	3	3	3	3	3
board[0][1]	0	0	1	1	0	4
board[0][3]	0	0	0	2	0	5
current cell	(0,0)	(0,0)	(0,1)	(0,3)	(0,3)	last cell
number tried	-	3	1	2	-	-

Key Moments - 3 Insights

Why do we backtrack and remove a number from a cell?

When no valid number can be placed in the current empty cell (see Step 14), we remove the last placed number and try the next possible number in the previous cell to explore other options.

How do we know when the puzzle is solved?

When the solver finds no empty cells left to fill (Step N), it means all cells are filled with valid numbers, so the puzzle is solved.

Why do we try numbers 1 to 9 in each empty cell?

Because Sudoku rules allow numbers 1 through 9 in each cell, and we must check each to find a valid placement (see Steps 2-4).

Visual Quiz - 3 Questions

Look at the execution table, what number was placed in cell (0,0) at Step 4?

A 2

B 1

C 3

D 0

💡 Hint

Check the 'Number Tried' and 'Action' columns at Step 4 in the execution table.

At which step does the solver backtrack and remove a number from cell (0,3)?

A Step 12

B Step 14

C Step 7

D Step 10

💡 Hint

Look for the 'Backtrack' operation in the execution table.

If the number 1 was valid at cell (0,1), what would happen next according to the execution flow?

A The solver places 1 and moves to the next empty cell

B The solver backtracks immediately

C The solver tries number 2 in the same cell

D The solver stops solving

💡 Hint

Refer to Steps 7 and 8 where a valid number leads to placement and recursion.

Concept Snapshot

Sudoku Solver Using Backtracking:
- Find first empty cell (value 0)
- Try numbers 1 to 9 in that cell
- Check if number placement is valid
- If valid, place number and recurse to next cell
- If stuck, backtrack by removing number and trying next
- Repeat until all cells filled
- Backtracking ensures all possibilities explored

Full Transcript

The Sudoku solver uses backtracking to fill empty cells one by one. It starts at the first empty cell and tries numbers 1 through 9. For each number, it checks if placing it is valid according to Sudoku rules. If valid, it places the number and moves to the next empty cell recursively. If no number fits, it backtracks by removing the last placed number and tries the next possible number. This process repeats until all cells are filled correctly, solving the puzzle.

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