Sudoku Solver Using Backtracking in DSA Go - Build from Scratch

Sudoku Solver Using Backtracking

📖 Scenario: You have a Sudoku puzzle that is partially filled. Your task is to write a program that fills the empty cells so that every row, column, and 3x3 box contains all digits from 1 to 9 exactly once.This is like solving a Sudoku puzzle on paper, but you will teach the computer to do it step-by-step.

🎯 Goal: Build a Sudoku solver using backtracking in Go. You will create the board, write helper functions to check if a number can be placed, implement the backtracking algorithm, and finally print the solved Sudoku board.

📋 What You'll Learn

Create a 9x9 Sudoku board with given initial numbers and zeros for empty cells

Create a function to check if placing a number in a cell is valid

Implement the backtracking function to solve the Sudoku

Print the solved Sudoku board in a readable format

💡 Why This Matters

🌍 Real World

Sudoku solvers are examples of constraint satisfaction problems. The backtracking technique is used in many real-world applications like scheduling, puzzle solving, and AI decision making.

💼 Career

Understanding backtracking and constraint checking is important for software engineers working in fields like game development, AI, and optimization problems.

1

Create the Sudoku board

Create a 9x9 two-dimensional slice of integers called board with the exact values given below. Use 0 to represent empty cells. The board should be:

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},
}

DSA Go

# Create the 9x9 Sudoku board with given values
# Your code here

Hint

Use a two-dimensional slice of integers with 9 rows and 9 columns. Use 0 for empty cells.

2

Write a function to check if a number can be placed

Add a function called isValid that takes the board, row, col, and num as parameters. It should return true if placing num at board[row][col] does not break Sudoku rules (no duplicates in the same row, column, or 3x3 box), otherwise false.

DSA Go

package main

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},
    }
}

// Write the isValid function below
// Your code here

Hint

Check the row and column for duplicates of num. Then check the 3x3 box by calculating its starting row and column.

3

Implement the backtracking solver

Add a function called solveSudoku that takes the board as a parameter and returns true if the Sudoku is solved. Use backtracking: find the first empty cell (0), try numbers 1 to 9, check if valid using isValid, place the number, and recursively call solveSudoku. If stuck, reset the cell to 0 and backtrack. Return true when the board is fully solved.

DSA Go

package main

import "fmt"

func isValid(board [][]int, row int, col int, num int) bool {
    // ... existing code ...
}

// Write the solveSudoku function below
// Your code here

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},
    }
}

Hint

Use nested loops to find empty cells. Try numbers 1 to 9. Use isValid to check. Place number and recurse. Backtrack if needed.

4

Print the solved Sudoku board

In the main function, call solveSudoku(board) to solve the puzzle. Then print the solved board row by row. Use a for loop to print each row as space-separated numbers on its own line.

DSA Go

package main

import "fmt"

func isValid(board [][]int, row int, col int, num int) bool {
    // ... existing code ...
}

func solveSudoku(board [][]int) bool {
    // ... existing code ...
}

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},
    }

    // Call solveSudoku and print the solved board
    // Your code here
}

Hint

Call solveSudoku(board). If it returns true, print each row with numbers separated by spaces. Use nested loops and fmt.Print and fmt.Println.

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