Sudoku Solver Using Backtracking in DSA Go - Deep Dive

Overview - Sudoku Solver Using Backtracking

What is it?

Sudoku Solver using backtracking is a method to fill a 9x9 grid with numbers so that each row, column, and 3x3 box contains all digits from 1 to 9 without repetition. It tries numbers one by one in empty cells and backtracks if a number causes a conflict. This process continues until the entire grid is correctly filled. It is a classic example of a problem solved by exploring possibilities and undoing wrong choices.

Why it matters

Without backtracking, solving Sudoku puzzles programmatically would be very hard because there are many possible number placements. Backtracking efficiently explores these possibilities and finds a solution or proves none exists. This technique is widely used in puzzles, games, and problems where trial and error with undoing steps is needed. It teaches how to systematically search through options and handle constraints.

Where it fits

Before learning this, you should understand arrays, loops, and basic recursion. After this, you can explore more complex constraint satisfaction problems, optimization algorithms, or advanced search techniques like heuristic pruning or dancing links.

Mental Model

Core Idea

Backtracking tries placing numbers step-by-step, and if a conflict arises, it goes back to change previous choices until the puzzle is solved.

Think of it like...

Imagine trying to find your way through a maze by choosing paths. If you hit a dead end, you backtrack to the last junction and try a different path until you find the exit.

┌─────────────┐
│ 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 │
└─────────────┘

Try number → Check validity → Place or backtrack

Build-Up - 7 Steps

1

Foundation

Understanding Sudoku Rules

Concept: Learn the basic rules of Sudoku: each row, column, and 3x3 box must contain digits 1 to 9 without repeats.

Sudoku is a 9x9 grid divided into nine 3x3 boxes. The goal is to fill empty cells with numbers 1-9 so that no number repeats in any row, column, or box. This rule ensures a unique solution for a valid puzzle.

Result

You know what constraints any number placement must satisfy.

Understanding these rules is essential because the solver must check these constraints before placing any number.

2

Foundation

Representing Sudoku in Code

Concept: Use a 2D array to represent the Sudoku grid, with zeros for empty cells.

In Go, declare a 9x9 integer array. Each element holds a number 0-9, where 0 means empty. This structure allows easy access to rows, columns, and boxes by indices.

Result

You have a clear data structure to hold the puzzle state.

Choosing the right data structure simplifies checking constraints and updating the puzzle during solving.

3

Intermediate

Checking Valid Number Placement

🤔Before reading on: Do you think checking a number's validity requires scanning the entire grid or just parts of it? Commit to your answer.

Concept: Implement a function to check if placing a number in a cell breaks Sudoku rules by scanning only the relevant row, column, and box.

To check if a number can be placed at (row, col): - Check the entire row for duplicates. - Check the entire column for duplicates. - Check the 3x3 box containing (row, col) for duplicates. If none found, placement is valid.

Result

You can verify if a number fits in a cell without breaking rules.

Limiting checks to row, column, and box avoids unnecessary work and keeps the solver efficient.

4

Intermediate

Implementing Backtracking Algorithm

🤔Before reading on: Do you think backtracking tries all numbers in order or picks numbers randomly? Commit to your answer.

Concept: Use recursion to try numbers 1-9 in empty cells, backtracking when no number fits.

Algorithm steps: 1. Find the next empty cell. 2. For numbers 1 to 9: a. Check if placing the number is valid. b. If valid, place the number and recurse to solve the rest. c. If recursion returns false, remove the number (backtrack) and try next. 3. If no empty cells remain, puzzle is solved.

Result

The solver fills the grid correctly or reports no solution.

Backtracking systematically explores all possibilities, undoing wrong choices to find a valid solution.

5

Intermediate

Optimizing Backtracking with Early Checks

🤔Before reading on: Do you think checking constraints after placing a number or before placing it is better? Commit to your answer.

Concept: Check constraints before placing numbers to avoid unnecessary recursion.

By verifying if a number is valid before placing it, the algorithm avoids deeper recursive calls that would fail. This early pruning reduces the search space and speeds up solving.

Result

The solver runs faster by skipping invalid paths early.

Early validation prevents wasted work and is key to efficient backtracking.

6

Advanced

Handling Multiple Solutions and No Solution Cases

🤔Before reading on: Do you think the backtracking solver always finds one solution or can it find all? Commit to your answer.

Concept: Modify the solver to detect if multiple solutions exist or if no solution is possible.

To find all solutions, continue searching after finding one by backtracking further. To detect no solution, return false if no valid number fits an empty cell. This helps in puzzle validation and difficulty assessment.

Result

You can identify puzzles with unique, multiple, or no solutions.

Understanding solution uniqueness is important for puzzle design and solver reliability.

7

Expert

Advanced Techniques: Heuristics and Constraint Propagation

🤔Before reading on: Do you think trying numbers in order is always best, or can smarter choices improve solving? Commit to your answer.

Concept: Use heuristics like choosing the cell with fewest options first and propagate constraints to reduce search space.

Heuristics: - Minimum Remaining Value (MRV): pick the empty cell with the fewest valid numbers. - Forward Checking: after placing a number, update possible values for neighbors. These reduce backtracking steps drastically. Constraint propagation techniques like AC-3 can also be applied for advanced pruning.

Result

The solver becomes much faster and can handle harder puzzles efficiently.

Smart choices and constraint updates transform backtracking from brute force to practical solving.

Under the Hood

Backtracking works by recursively trying choices and undoing them if they lead to dead ends. Internally, the algorithm maintains the current puzzle state in memory. Each recursive call attempts to fill one empty cell. If no valid number fits, the call returns false, triggering backtracking to the previous call where alternative numbers are tried. This depth-first search explores the solution space systematically.

Why designed this way?

Backtracking was chosen because Sudoku is a constraint satisfaction problem with many possible states. Exhaustive search without backtracking would be inefficient. Backtracking balances completeness and efficiency by pruning invalid paths early. Alternatives like brute force are too slow, and more complex algorithms require deeper domain knowledge.

┌───────────────┐
│ Start solving │
└──────┬────────┘
       │
       ▼
┌───────────────┐
│ Find empty cell│
└──────┬────────┘
       │
       ▼
┌─────────────────────────┐
│ Try number 1 to 9 in cell│
└──────┬────────┬──────────┘
       │        │
       ▼        ▼
┌───────────┐  ┌───────────────┐
│ Valid?    │  │ Invalid → try │
│ Yes →    │  │ next number    │
│ place &  │  └───────────────┘
│ recurse  │
└────┬─────┘
     │
     ▼
┌───────────────┐
│ Solved?       │
│ Yes → return  │
│ No → backtrack│
└───────────────┘

Myth Busters - 4 Common Misconceptions

Quick: Does backtracking always try numbers in random order? Commit to yes or no.

Common Belief: Backtracking tries numbers randomly to find a solution faster.

Reality: Backtracking usually tries numbers in a fixed order (1 to 9) unless heuristics are added.

Why it matters: Assuming randomness can lead to misunderstanding solver behavior and performance tuning.

Quick: Can backtracking solve any Sudoku puzzle instantly? Commit to yes or no.

Common Belief: Backtracking instantly solves all Sudoku puzzles regardless of difficulty.

Reality: Backtracking can be slow on very hard puzzles without heuristics or optimizations.

Why it matters: Expecting instant results can cause frustration and overlook the need for algorithm improvements.

Quick: Is it enough to check only rows and columns for validity? Commit to yes or no.

Common Belief: Checking rows and columns is enough to ensure Sudoku rules are followed.

Reality: The 3x3 box constraint must also be checked to avoid invalid solutions.

Why it matters: Ignoring box checks leads to incorrect solutions that break Sudoku rules.

Quick: Does backtracking always find all solutions by default? Commit to yes or no.

Common Belief: Backtracking automatically finds all possible solutions to a Sudoku puzzle.

Reality: Standard backtracking stops after finding the first valid solution unless modified.

Why it matters: Misunderstanding this can cause incorrect assumptions about puzzle uniqueness.

Expert Zone

1

Choosing the next empty cell with the fewest valid options (MRV heuristic) drastically reduces search time.

2

Constraint propagation after each placement can prune impossible values early, preventing deep backtracking.

3

Implementing iterative deepening or hybrid algorithms can improve performance on extremely hard puzzles.

When NOT to use

Backtracking is inefficient for very large or complex constraint problems where specialized algorithms like Dancing Links or SAT solvers perform better.

Production Patterns

In production, Sudoku solvers often combine backtracking with heuristics and caching. They may also validate puzzles for uniqueness and generate puzzles by reverse-solving.

Connections

Depth-First Search (DFS)

Backtracking is a form of DFS applied to constraint problems.

Understanding DFS helps grasp how backtracking explores solution spaces by going deep and backtracking on failure.

Constraint Satisfaction Problems (CSP)

Sudoku solving is a classic example of CSP where variables must satisfy constraints.

Knowing CSP theory helps in applying advanced techniques like constraint propagation and heuristics.

Decision Trees in Psychology

Backtracking mirrors decision-making processes where choices are explored and reversed upon failure.

Recognizing this connection shows how algorithms model human problem-solving strategies.

Common Pitfalls

#1 Not checking the 3x3 box constraints when placing numbers.

Wrong approach:

func isValid(board [][]int, row, col, num int) bool {
for i := 0; i < 9; i++ {
if board[row][i] == num || board[i][col] == num {
return false
}
}
return true // Missing box check
}

Correct approach:

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

Root cause:

Misunderstanding Sudoku rules or overlooking the box constraint.

#2 Not backtracking properly after a failed recursive call.

Wrong approach:

func solve(board [][]int) bool {
row, col := findEmpty(board)
if row == -1 {
return true
}
for num := 1; num <= 9; num++ {
if isValid(board, row, col, num) {
board[row][col] = num
if solve(board) {
return true
}
// Missing backtrack step here
}
}
return false
}

Correct approach:

func solve(board [][]int) bool {
row, col := findEmpty(board)
if row == -1 {
return true
}
for num := 1; num <= 9; num++ {
if isValid(board, row, col, num) {
board[row][col] = num
if solve(board) {
return true
}
board[row][col] = 0 // Backtrack
}
}
return false
}

Root cause:

Forgetting to undo the number placement when recursion fails.

#3 Trying to solve without identifying empty cells correctly.

Wrong approach:

func findEmpty(board [][]int) (int, int) {
return 0, 0 // Always returns first cell, ignoring emptiness
}

Correct approach:

func findEmpty(board [][]int) (int, int) {
for r := 0; r < 9; r++ {
for c := 0; c < 9; c++ {
if board[r][c] == 0 {
return r, c
}
}
}
return -1, -1
}

Root cause:

Not scanning the board properly to find empty cells.

Key Takeaways

Backtracking solves Sudoku by trying numbers step-by-step and undoing wrong choices to find a valid solution.

Checking constraints for rows, columns, and 3x3 boxes before placing numbers is essential to maintain puzzle rules.

Optimizations like choosing cells with fewer options first and constraint propagation greatly improve solver efficiency.

Backtracking can find one or all solutions depending on implementation, but standard versions stop after the first solution.

Understanding backtracking in Sudoku builds a foundation for solving many other constraint satisfaction problems.

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