Sudoku Solving Implementations

A lot of tutorials on solving Sudoku puzzles using backtracking are typically implemented in Python, and the often are similar the code provided below:

def solve_sudoku(board):
  # Find the next empty cell
  row, col = find_empty_cell(board)
  if row == -1:  # If there are no empty cells left, the puzzle is solved
    return True

  # Try each possible value for the empty cell
  for num in range(1, 10):
    if is_valid_move(board, row, col, num):
      # Place the number in the empty cell
      board[row][col] = num

      # Recursively solve the puzzle
      if solve_sudoku(board):
        return True

      # If the puzzle cannot be solved with this number, remove it
      board[row][col] = 0

  # If none of the possible numbers work, backtrack
  return False

While this code isn't that bad, you can mess it a little, specially with a lot of comments and a function call with 4 parameters, as seen here:

is_valid_move(board, row, col, num)

And when you check the implementation, you have to read the comments AND the code, as illustrated below:

def is_valid_move(board, row, col, num):
  # Check if the number is already in the row
  for i in range(9):
    if board[row][i] == num:
      return False

  # Check if the number is already in the column
  for i in range(9):
    if board[i][col] == num:
      return False

  # Check if the number is already in the 3x3 box
  box_row = (row // 3) * 3
  box_col = (col // 3) * 3
  for i in range(box_row, box_row + 3):
    for j in range(box_col, box_col + 3):
      if board[i][j] == num:
        return False

  return True

This code contains an excess of comments, so, it's a perfect situation to improve it's readability using Golang. We're going to make this code easy to understand, trust me.

(Actually, if you wanna check this solution written in python, I highly recommend you to visit the last session, the references and check the links).

---

Go implementation

I made a big effort to make a code that is easy to READ. The primary objective was to understand the logic behind python algorithm's that I have found and translate them into Go in a more comprehensible manner.

It wasn't a very easy task, because the presence of numerous indices like i and j ,some variables rows and columns, which can difficult the process to understand the solving algorithm.

So, I divided the solution in parts, trying to implement every single part of the algorithm in a separate function/struct. Thus, the final code resembles spoken english, and that's really good, because this facilitates the compreehension for other developers and teammates.

After the final implementation I got these structs:

• Sudoku Solver → Responsible for solving the sudoku puzzle

• Sudoku → Represents the sudoku board and facilitate printing

• Board → A type that doesn't have any attached methods

• Cell → Represents a sudoku cell which store a number between 1 and 9 (inclusive) and the row/column position whitin the board

That can be visualized like this:

Let's compare the first solve function that have been written in Python with this one rewritten in Go:

// Solves the sudoku
func (solver *SudokuSolver) Solve() bool {
    s := solver.sudoku
    availableCell := solver.findEmptyCell()

    if availableCell.IsNotFound() {
        // Finished
        return true
    }

    cellMinValue := 1
    cellMaxValue := 9
    for i := cellMinValue; i <= cellMaxValue; i++ {
        availableCell.Number = i
        isValidInRow := solver.isCellValidInTheRow(availableCell)
        isValidInCol := solver.isCellValidInTheColumn(availableCell)
        isValidInBox := solver.isCellValidInTheBox(availableCell)

        isAValidCell := isValidInRow && isValidInCol && isValidInBox
        if isAValidCell {
            s.board[availableCell.Row][availableCell.Col] = availableCell
            if solver.Solve() {
                // Finished
                return true
            }
            // If not solve, then backtrack and try again with the next value
            solver.backtrack(availableCell)
        }
    }

    // Invalid sudoku
    return false
}

This Go implementation presents enhanced readability compared to the Python version.

And checking the other function implementations, you can see some improvements in readability:

// Check if some cell in board is empty (has value 0)
func (solver *SudokuSolver) findEmptyCell() cell {
    s := solver.sudoku
    for row := 0; row < s.size; row++ {
        for col := 0; col < s.size; col++ {
            cell := s.board[row][col]
            if cell.IsEmpty() {
                return cell
            }
        }
    }
    return newNotFoundCell()
}

// Return the cell to their original state, with default cell value
func (solver *SudokuSolver) backtrack(cell cell) {
    solver.sudoku.board[cell.Row][cell.Col] = newCell(cell.Row, cell.Col, defaultCellValue)
}

// Iterates over the rows to check if the cell is valid in that position
func (solver *SudokuSolver) isCellValidInTheRow(cell cell) bool {
    s := solver.sudoku
    for i := 0; i < s.size; i++ {
        currentCell := s.board[cell.Row][i]
        if currentCell.Number == cell.Number {
            return false
        }
    }
    return true
}

// Iterates over the columns to check if the cell is valid in that position
func (solver *SudokuSolver) isCellValidInTheColumn(cell cell) bool {
    s := solver.sudoku
    for i := 0; i < s.size; i++ {
        currentCell := s.board[i][cell.Col]
        if currentCell.Number == cell.Number {
            return false
        }
    }
    return true
}

// Iterates over the current box to check if the cell is valid in that position
func (solver *SudokuSolver) isCellValidInTheBox(cell cell) bool {
    s := solver.sudoku
    boxRowStart := int(math.Floor(float64(cell.Row/3)) * 3)
    boxColStart := int(math.Floor(float64(cell.Col/3)) * 3)
    boxRowEnd := boxRowStart + 3
    boxColEnd := boxColStart + 3

    for row := boxRowStart; row < boxRowEnd; row++ {
        for col := boxColStart; col < boxColEnd; col++ {
            currentCell := s.board[row][col]
            isTheSameNumber := currentCell.Number == cell.Number
            isTheSamePosition := currentCell.Row == cell.Row && currentCell.Col == cell.Col
            if isTheSameNumber && !isTheSamePosition {
                return false
            }
        }
    }
    return true
}

This reimplementation of Sudoku solving algorithm, reduced the comments and chage it to descriptive function names, enhancing readability and maintainability.

Moreover, utilizing functions over comments facilitates testing (It's VERY EASY TO TEST, really!), contributing to an easier understanding of the algorithm.

If you don't trust me, I also included some tests in the project. You can run the tests and see by yourself that is very easy to test the functions.

Also, th tests helped me to understand the whole solving algorithm, so I'm sure it will help you too.

If you'd like to explore the entire codebase and run the tests, you can access it here: golang-sudoku-solver.

---

Conclusions

I hope this tutorial taught you 2 things:

1. Function Decomposition: Splitting the code into functions with good names allows for the removal of redundant comments.

2. Responsibility Separation: It's beneficial to divide the code into distinct "concepts," each with its own responsibilities. For example, the Sudoku Solver handles all the logic required to solve the puzzle, while the Sudoku manages the current state of the Sudoku and facilitates board printing.

   This responsability separation leads to cleaner and more organized code.

---

References

Python Sudoku Solver Tutorial with Backtracking p.1 (youtube.com)

(3) Python Sudoku Solver Tutorial with Backtracking p.2 - YouTube

Python — Sudoku Solver. Sudoku is a popular logic puzzle that… | by TechwithJulles | Medium