Build Sudoku Solver Engine using Go

Introduction 🤖

We have been learning new topics with Go, and before getting into DevOps topics in our blogs, today let’s build a simple fun project and gear up your algorithms skills a little.

As you know, Sudoku is a board game where there is 81 boxes, each with a specific number between 1-9 or it can be a empty box. We have to fill those empty boxes in a way that no number is repeated in it’s row, column and in 3*3 area of board. Don’t worry, google a little about Sudoku if you don’t know what this game is in general.

We know that there is definitely a algorithm we humans use while solving a sudoku pattern in paper, and now we have to just think about that algorithm and try to write it for our computers to understand. It is going to be interesting and brainstorming, so now we should proceed into it.

Prerequisites

You should have a basic knowledge of

• Go
• Recursion (optional)

Lets Begin

Very important part of building a sudoku solver using programming languages is Recursion. Briefly I can say, Recursion is a method where a function calls itself. Let’s see an example of that,

// len returns the length of a string using Recursion.
func len(str string) int {

   // base condition where our function stops.
   if str == "" {
     return 0
   }
   // if str = "golang"
   substring := str[1:]
   // substring = "olang"

   // for each len func call, we are increasing the result int by 1 and 
   //calling the same function by reducing the string length 
   //by one character (or rune).

   return 1 + len(substring)
}

Output: len("abcde") = 5

As you can see, len function is returning 1 + (len(substring). If str is not empty then it must have a length of 1 and passing the reduced str to len again, and running until str becomes empty. When it gets empty, it returns 0 where our programme ends.

For better understanding, here is reference link to you. Learn More

Now you understand Recursion a little, so we can just head into our sudoku engine. You can see our program in running state now, go/sudoku-engine.

1. Setup Sudoku Engine Project

1. Create a new folder for your project and name it sudoku-engine.
2. Create a new file in that folder and name it main.go.
3. Run go mod init sudoku-engine in terminal to initialize your project.

2. Writing Engine Code

1. First create a parse function to convert our sudoku pattern into a 2D slice. We will use this slice to solve our sudoku pattern.

   // parseInput converts a string to 2D slice/array.
    func parseInput(input string) [][]int {
        board := [][]int{
            {0, 0, 0, 0, 0, 0, 0, 0, 0},
            {0, 0, 0, 0, 0, 0, 0, 0, 0},
            {0, 0, 0, 0, 0, 0, 0, 0, 0},
            {0, 0, 0, 0, 0, 0, 0, 0, 0},
            {0, 0, 0, 0, 0, 0, 0, 0, 0},
            {0, 0, 0, 0, 0, 0, 0, 0, 0},
            {0, 0, 0, 0, 0, 0, 0, 0, 0},
            {0, 0, 0, 0, 0, 0, 0, 0, 0},
            {0, 0, 0, 0, 0, 0, 0, 0, 0},
        } // dummy board
   
        // scanner is set up to read input string.
        scanner := bufio.NewScanner(strings.NewReader(input))
        scanner.Split(bufio.ScanRunes)
   
        // go for an iteration over the whole string of length 81.
        // if the rune is a number, then we convert it to int and add it to our board.
        for row := 0; row < 9; row++ {
            for col := 0; col < 9; col++ {
                scanner.Scan()
                tmp := scanner.Text()
                val, err := strconv.Atoi(tmp)
                if err != nil {
                    // error here
                }
                board[row][col] = val
            }
        }
   
        return board
    }
   

2. Create isSafe function to check if a number we are trying to put in a box is safe or not.

It means, if the number is already present in its row, column or 3*3 area of the board, then it is not safe to put that number in that box.

// isSafe returns true if it is possible to put n in that (row, col) position in the given board.
func isSafe(board *[][]int, row int, col int, num int) bool {
  // tasks to do
  // 1. check if num is present in row
  // 2. check if num is present in col
  // 3. check if num is present in 3*3 box

  // checking in the row
  for _, slice := range *board {
    if slice[col] == num {
      return false
    }
  }

  // checking in the col
  for _, value := range (*board)[row] {
    if value == num {
      return false
    }
  }

  // checking in the 3*3 box
  rowStart := row - row%3 // (row / 3) * 3
  colStart := col - col%3 // (col / 3) * 3
  for i := rowStart; i < rowStart+3; i++ {
    for j := colStart; j < colStart+3; j++ {
      if (*board)[i][j] == num {
        return false
      }
    }
  }

return true
}

1. Create a solve function to solve our sudoku pattern. We will use recursion and backtracking in this function to solve our sudoku pattern.

// solve the sudoku board using backtracking.
// It returns solved board if the board is solved.
func solve(board *[][]int) bool {
  // tasks to do
  // 1. find the empty cell
  // 2. try to put a number in that cell
  // 3. check if it is safe to put that number in that cell
  // 4. if it is safe then put that number in that cell and solve the rest of the board
  // 5. if it is not safe then try another number
  // 6. if all the numbers are tried and none of them is safe then return false

  row := -1
  col := -1
  isEmpty := false

  // finding the empty cell
  for r, slice := range *board {
    for c, value := range slice {
      if value == 0 {
        isEmpty = true
        row = r
        col = c
        break
      }
     if isEmpty {
      break
     } // found empty cell.
    }
  }

  if !isEmpty {
    return true
  } //base condition

  // if there is no empty cell then the board is solved
  for i := 1; i <= 9; i++ {
    // trying to put a number in that cell

    // checking if it is safe to put that number in that cell
    if isSafe(board, row, col, i) {
      // putting that number in that cell
      (*board)[row][col] = I

      // solving the rest of the board
      if !solve(board) {
        // if the board is not solved then we need to backtrack
         (*board)[row][col] = 0 // backtrack
      } else {
      // board it solved!
      return true
      }
    }
  }

// if all the numbers are tried and none of them is safe then return false
return false
}

1. Create a print function to print our solved sudoku pattern.

// display prints sudoku board on console.
func display(board [][]int) {
  for _, slice := range board {
    for _, val := range slice {
      fmt.Printf("%d, ", val)
    }
    fmt.Println()
  }
}

Whole function with input taking part in main.go,

import (
"bufio"
"fmt"
"log"
"os"
"strconv"
"strings"
)

func main() {
  fmt.Printf("Enter the name of your file containing the Sudoku Pattern :        ")

  scanner := bufio.NewScanner(os.Stdin)
  scanner.Scan()
  var file string
  file = scanner.Text()
  if !strings.Contains(file, ".text") {
    file = "pattern-1.text"
  }

  input, err := os.ReadFile(fmt.Sprintf("./inputs/%s", file))
  if err != nil {
    log.Println(err)
  }

  board := parseInput(string(input))

  fmt.Println("Defined Sudoku Pattern")
  display(board)
  fmt.Println()

  fmt.Println("Engine starts solving the pattern...")
  if solve(&board) {
  //display(board)

  file, err := os.Create(fmt.Sprintf("./outputs/%s", file))
  if err != nil {
    log.Println(err)
  }

  for _, slice := range board {
    s := ""
    for _, v := range slice {
      s= s + fmt.Sprintf("%v, ", v)
    }
    _, err = file.WriteString(fmt.Sprintf("%v\n", s))
    if err != nil {
      log.Println(err)
    }
   }
  }

  fmt.Println(fmt.Sprintf("Result is saved in \"./outouts/%v\"", file))
}

3. Performing Tests

1. Git clone this repository: github/SudokuSolver-Golang
2. Follow the steps performed in this video
   https://vimeo.com/763376424
3. Output will be:

    $ go run main.go
    3, 1, 6, 5, 7, 8, 4, 9, 2, 
    5, 2, 9, 1, 3, 4, 7, 6, 8, 
    4, 8, 7, 6, 2, 9, 5, 3, 1, 
    2, 6, 3, 4, 1, 5, 9, 8, 7, 
    9, 7, 4, 8, 6, 3, 1, 2, 5, 
    8, 5, 1, 7, 9, 2, 6, 4, 3, 
    1, 3, 8, 9, 4, 7, 2, 5, 6, 
    6, 9, 2, 3, 5, 1, 8, 7, 4, 
    7, 4, 5, 2, 8, 6, 3, 1, 9,
   

4. You can see the test here also, go/sudoku-engine

4. Issue to Solve for you

Solve a project issue now: sudoku-engine/issue#1

If you never tried open source, this is a good place to start and learn more of Git and Github.

Final Note

I hope you learned something new today. You can also contribute to this project. If you have any questions, feel free to ask me in the comments below. I will be happy to help you. It would be great if you share this article with your developer friends who are new to tech.

Follow me on: @sarkartanmay393
Direct mail me: hello@tanmaysarkar.tech