Search⌘ K
Home
Courses
Decode the Coding Interview in Go: Real-World Examples

Sudoku Solver

Explore how to implement a Sudoku solver in Go by filling empty cells with digits 1 through 9, ensuring no duplicates in rows, columns, or 3x3 boxes. Understand the use of backtracking and constraint programming to efficiently find solutions, and analyze the time and space complexity of this approach.

We'll cover the following...

Description

Write a program to solve Sudoku by filling the empty cells. We will be given a 2D array representing a Sudoku puzzle. For a correct solution each of the digits 1-9 must only occur once in each:

  • Row
  • Column
  • Nine 3x3 sub-boxes of the grid

Let us take a look at an example:

To solve the puzzle, we will only fill the empty cells. Empty cells are represented by a ‘.’. The array will be passed by reference, so we will not need to return it after solving the puzzle.

Coding exercise

Go (1.16.5)
package main
import (
  "fmt"
  "encoding/json"
)
func SolveSudoku(board [][]byte){
  
}
Sudoku solver

Solution

While solving Sudoku, we will have to take care of two things. First, we place a number at an empty place. The number must not be present in that row, column, or sub-box. So, we will use constrained programming to keep track of which number we can place in a box and which not. Second, let us assume that we have filled a few empty places but, the choice of numbers was not optimal, ...