Sudoku Solver Using Backtracking in DSA Go

Mental Model

Try filling empty cells one by one with numbers that follow Sudoku rules, and backtrack if stuck.

Analogy: Like solving a maze by choosing paths step-by-step and going back when hitting a dead end.

5 3 _ | _ 7 _ | _ _ _
6 _ _ | 1 9 5 | _ _ _
_ 9 8 | _ _ _ | _ 6 _
------+-------+------
8 _ _ | _ 6 _ | _ _ 3
4 _ _ | 8 _ 3 | _ _ 1
7 _ _ | _ 2 _ | _ _ 6
------+-------+------
_ 6 _ | _ _ _ | 2 8 _
_ _ _ | 4 1 9 | _ _ 5
_ _ _ | _ 8 _ | _ 7 9

Dry Run Walkthrough

Input: Partially filled 9x9 Sudoku board with empty cells as 0

Goal: Fill all empty cells so that each row, column, and 3x3 box contains numbers 1 to 9 without repetition

Step 1: Find first empty cell at row 0, column 2 and try number 1

5 3 [1] | _ 7 _ | _ _ _
6 _ _ | 1 9 5 | _ _ _
_ 9 8 | _ _ _ | _ 6 _
------+-------+------
8 _ _ | _ 6 _ | _ _ 3
4 _ _ | 8 _ 3 | _ _ 1
7 _ _ | _ 2 _ | _ _ 6
------+-------+------
_ 6 _ | _ _ _ | 2 8 _
_ _ _ | 4 1 9 | _ _ 5
_ _ _ | _ 8 _ | _ 7 9

Why: Try smallest number to fill empty cell following Sudoku rules

Step 2: Placing 1 leads to dead end later, backtrack and try number 2 at same cell

5 3 [2] | _ 7 _ | _ _ _
6 _ _ | 1 9 5 | _ _ _
_ 9 8 | _ _ _ | _ 6 _
------+-------+------
8 _ _ | _ 6 _ | _ _ 3
4 _ _ | 8 _ 3 | _ _ 1
7 _ _ | _ 2 _ | _ _ 6
------+-------+------
_ 6 _ | _ _ _ | 2 8 _
_ _ _ | 4 1 9 | _ _ 5
_ _ _ | _ 8 _ | _ 7 9

Why: Previous number didn't lead to solution, try next

Step 3: Placing 2 also leads to dead end later, backtrack and try number 4 at same cell

5 3 [4] | _ 7 _ | _ _ _
6 _ _ | 1 9 5 | _ _ _
_ 9 8 | _ _ _ | _ 6 _
------+-------+------
8 _ _ | _ 6 _ | _ _ 3
4 _ _ | 8 _ 3 | _ _ 1
7 _ _ | _ 2 _ | _ _ 6
------+-------+------
_ 6 _ | _ _ _ | 2 8 _
_ _ _ | 4 1 9 | _ _ 5
_ _ _ | _ 8 _ | _ 7 9

Why: Found valid number that leads to solution, proceed to next empty cell

Step 4: Continue filling cells similarly, backtracking when no number fits

Board gradually fills with valid numbers, backtracking corrects wrong guesses

Why: Backtracking ensures all possibilities are explored to find solution

Result:

Fully filled Sudoku board with all rules satisfied:
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

Annotated Code

DSA Go

package main

import "fmt"

const N = 9

func isSafe(board [N][N]int, row, col, num int) bool {
	// Check row for num
	for x := 0; x < N; x++ {
		if board[row][x] == num {
			return false
		}
	}
	// Check column for num
	for x := 0; x < N; x++ {
		if board[x][col] == num {
			return false
		}
	}
	// Check 3x3 box for num
	startRow := row - row%3
	startCol := col - col%3
	for i := 0; i < 3; i++ {
		for j := 0; j < 3; j++ {
			if board[startRow+i][startCol+j] == num {
				return false
			}
		}
	}
	return true
}

func solveSudoku(board *[N][N]int) bool {
	for row := 0; row < N; row++ {
		for col := 0; col < N; col++ {
			if board[row][col] == 0 {
				for num := 1; num <= 9; num++ {
					if isSafe(*board, row, col, num) {
						board[row][col] = num // place num
						if solveSudoku(board) {
							return true // solved
						}
						board[row][col] = 0 // backtrack
					}
				}
				return false // no valid num found
			}
		}
	}
	return true // all cells filled
}

func printBoard(board [N][N]int) {
	for i := 0; i < N; i++ {
		for j := 0; j < N; j++ {
			fmt.Printf("%d ", board[i][j])
			if (j+1)%3 == 0 && j != N-1 {
				fmt.Print("| ")
			}
		}
		fmt.Println()
		if (i+1)%3 == 0 && i != N-1 {
			fmt.Println("------+-------+------")
		}
	}
}

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

	if solveSudoku(&board) {
		printBoard(board)
	} else {
		fmt.Println("No solution exists")
	}
}

for x := 0; x < N; x++ { if board[row][x] == num { return false } }

Check if num already exists in the current row

for x := 0; x < N; x++ { if board[x][col] == num { return false } }

Check if num already exists in the current column

for i := 0; i < 3; i++ { for j := 0; j < 3; j++ { if board[startRow+i][startCol+j] == num { return false } } }

Check if num already exists in the 3x3 box

for row := 0; row < N; row++ { for col := 0; col < N; col++ { if board[row][col] == 0 {

Find the next empty cell to fill

for num := 1; num <= 9; num++ { if isSafe(*board, row, col, num) { board[row][col] = num

Try numbers 1 to 9 and place if safe

if solveSudoku(board) { return true }

Recursively solve rest of board after placing number

board[row][col] = 0

Backtrack by resetting cell if no number leads to solution

return true

Return true when all cells are filled successfully

Output

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 

Complexity Analysis

Time: O(9^(N*N)) because in worst case each empty cell tries 9 numbers recursively

Space: O(N*N) due to recursion stack and board storage

vs Alternative: Backtracking is more efficient than brute force guessing all combinations without checks, but still exponential in worst case

Edge Cases

Empty board (all zeros)

Solver tries all possibilities, may take longer but still finds solution

DSA Go

if board[row][col] == 0 {

Already solved board

Solver quickly returns true without changes

DSA Go

return true

No solution board (contradictory numbers)

Solver backtracks fully and returns false

DSA Go

return false

When to Use This Pattern

When you see a problem requiring filling a grid with constraints and trial/error, reach for backtracking because it tries options stepwise and undoes wrong choices.

Common Mistakes

Mistake: Not checking 3x3 box constraints leading to invalid solutions
Fix: Add check for 3x3 box in isSafe function

Mistake: Not resetting cell to 0 when backtracking
Fix: Set board[row][col] = 0 after recursive call fails

Summary

It fills empty Sudoku cells with valid numbers using trial and error with backtracking.

Use it when you need to solve puzzles or problems with constraints and multiple choices.

The key insight is to try a choice, move forward, and undo if it leads to a dead end.

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