Sudoku Solver in Go: A Beginner’s Guide and Optimization Techniques

The game of Sudoku has always been a popular pastime for many. Whether you’re an absolute novice or a seasoned veteran, the challenge of filling out a 9x9 grid with digits so that each column, each row, and each of the nine 3x3 subgrids contains all of the digits from 1 to 9, is an appealing task. Today, we’re going to see how we can automate this process in Golang, and how we can optimize it using memoization techniques.

A Basic Sudoku Solver in Golang

Let’s start with a basic approach. First, we need to represent our Sudoku grid in Go. A two-dimensional slice of integers fits the bill:

type SudokuGrid [9][9]int

Backtracking Algorithm

The simplest approach to solving Sudoku programmatically is to use a backtracking algorithm. Backtracking is a trial and error based methodology used for problem solving. Let’s implement a basic backtracking algorithm in Go:

func solveSudoku(grid *SudokuGrid) bool {
  for i := 0; i < 9; i++ {
    for j := 0; j < 9; j++ {
      if grid[i][j] == 0 {
        for num := 1; num <= 9; num++ {
          if isValid(grid, i, j, num) {
            grid[i][j] = num

            if solveSudoku(grid) {
              return true
            } else {
              // Undo current cell for backtracking
              grid[i][j] = 0
            }
          }
        }
        return false
      }
    }
  }
  return true
}

The solveSudoku function works by iterating through each cell in the grid, filling in empty cells (those that contain a zero), and checking if the number being inserted is valid for that cell. If the number is valid, the function recursively tries to solve the rest of the grid. If it can’t, it backtracks by setting the cell back to zero and tries the next number.

The isValid function checks if a given number is valid for a particular cell:

func isValid(grid *SudokuGrid, row, col, num int) bool {
  // Check the line
  for i := 0; i < 9; i++ {
    if grid[row][i] == num {
      return false
    }
  }

  // Check the column
  for i := 0; i < 9; i++ {
    if grid[i][col] == num {
      return false
    }
  }

  // Check the box
  startRow, startCol := row-row%3, col-col%3
  for i := 0; i < 3; i++ {
    for j := 0; j < 3; j++ {
      if grid[i+startRow][j+startCol] == num {
        return false
      }
    }
  }
  
  return true
}

Optimizing Sudoku Solver with Memoization

The standard backtracking approach works fine, but it can be slow, especially for larger or more complex Sudoku puzzles. One way to speed up the backtracking algorithm is by using memoization, a technique that stores the results of expensive function calls and reusing them when the same inputs occur again.

In our case, we can store the validity of each number for each cell in three maps, one for the rows, one for the columns, and one for the boxes.

Let’s define our memoization maps:

type SudokuGrid [9][9]int
type MemoizationMap [9][9][10]bool

var rowsUsed, colsUsed, boxesUsed MemoizationMap

We need to initialize our maps at the beginning of our program. We’ll go through our Sudoku grid and for each cell that is not empty, we’ll set the corresponding entry in our maps:

func initializeMemoizationMaps(grid *SudokuGrid) {
  for i := 0; i < 9; i++ {
    for j := 0; j < 9; j++ {
      num := grid[i][j]
      if num != 0 {
        idx := (i/3)*3 + j/3
        rowsUsed[i][j][num] = true
        colsUsed[i][j][num] = true
        boxesUsed[idx][j][num] = true
      }
    }
  }
}

Now, we can modify our solveSudoku and isValid functions to make use of our memoization maps:

func solveSudoku(grid *SudokuGrid) bool {
  for i := 0; i < 9; i++ {
    for j := 0; j < 9; j++ {
      if grid[i][j] == 0 {
        for num := 1; num <= 9; num++ {
          if isValid(i, j, num) {
            placeNumber(grid, i, j, num)

            if solveSudoku(grid) {
              return true
            } else {
              removeNumber(grid, i, j, num)
            }
          }
        }
        return false
      }
    }
  }
  return true
}

func isValid(row, col, num int) bool {
  idx := (row / 3) * 3 + col / 3
  return !rowsUsed[row][num] && !colsUsed[col][num] && !boxesUsed[idx][num]
}

func placeNumber(grid *SudokuGrid, row, col, num int) {
  idx := (row / 3) * 3 + col / 3

  grid[row][col] = num
  rowsUsed[row][num] = true
  colsUsed[col][num] = true
  boxesUsed[idx][num] = true
}

func removeNumber(grid *SudokuGrid, row, col, num int) {
  idx := (row / 3) * 3 + col / 3

  grid[row][col] = 0
  rowsUsed[row][num] = false
  colsUsed[col][num] = false
  boxesUsed[idx][num] = false
}

With this new approach, instead of repeatedly checking the validity of a number in a certain cell, we are directly accessing the stored value in constant time, leading to a substantial speed up in our program.

While both these approaches solve the Sudoku puzzle, using memoization significantly speeds up the process. Remember that while memoization uses more memory, it can drastically cut down the time complexity of our algorithm.