Solving Sudoku Puzzles with Go

August 12, 2019
go tutorial

This tutorial was written for a Cambridge Gophers Meetup. In the tutorial, we implement a Go program to solve Sudoku puzzles. The tutorial is suitable for relative newcomers to Go; if you are completely new to the language, you should start with A Tour of Go or this more comprehensive tutorial.

The tutorial is split into two parts. The first part outlines the algorithm we will implement. If you are already familiar with Go, you can just read this and dive straight into your own implementation. If you want a more gentle introduction, continue reading to the second part where we guide you through the implementation.

If you get stuck at any point, or want to compare your approach with mine, you can find my implementation on Github go-sudoku-tutorial.

Part I: The Algorithm

If you are not familiar with Sudoku, you can familiarize yourself with the rules here.

We start with a partially-completed 9x9 grid:

Initial Grid

Find the first unfilled cell:

First Unfilled

Locate all of the neighbouring cells (those in the same row, column or 3x3 subgrid):

Related Cells

The neighbouring cells contain the values {1,2,4,5,6,9}, so the possible values for our unfilled cell are the set difference {1,2,3,4,5,6,7,8,9} \ {1,2,4,5,6,9} = {3,7,8}. We construct the 3 grids with the unfilled cell set to each of these values in turn:

Child 1 Child 2 Child 3

We can now do the same thing with each of these child grids: find the first unfilled cell, and construct the child grids for each possbile value of that cell. You can see that we are building a tree of grids:

Tree

As we progress deeper into the tree, we will eventually end up at a grid with no unfilled cells, or a grid with no possible (legal) values for an unfilled cell. In the first case, we have found a solution and can stop our search and return the solution. In the second case, we have to abandon this search path and try the next option.

Each time we fill a cell, the tree gets one row deeper. If we start with a grid with n empty cells, we have to traverse n rows deep into the tree before we will find a solution; we will never find a completed grid in a shallower part of the tree. This tells us that we should do a depth-first search to find the solution.

Your program should take a path to a text representation of a grid, parse the grid, find the solution using a depth-first search, and print the solution to the screen.

Here are some puzzles to practise on: easy, medium, hard, evil.

Once you have solved these puzzles, you could adapt your program to solve Project Euler Problem 96.

Part II: Implementation

This tutorial assumes you already have the Go tools installed on your system. If not, follow the instructions in the Getting Started guide and make sure you can run the hello world program before returning here.

Start by creating a directory for this project in your Go Workspace:

mkdir $HOME/go/src/sudoku

Create a file called sudoku.go in this directory. We will do all of our work in the main package, so this file should start out like:

package main

import (
    "fmt"
)

func main() {
    fmt.Println("I don't do much yet")
}

Change into the project directory and make sure you can run this:

cd $HOME/go/src/sudoku
go run sudoku.go

Representing the Grid

We will represent a grid as an array of 81 integers in row-major order. This means the first 9 elements of the array represent the first row of the grid, the next 9 elements the second row, etc. If we number the rows and columns from 0-8, with the top left-hand corner of the grid being row 0, column 0, then we can compute an element’s index into the array as follows:

ix = col + row*9

Conversely, given an index into the array, we can compute the row and column as follows:

col = ix % 9
row = ix / 9

For convenience and clarity of our code, we will define a type for the grid:

type Grid [81]int

We will use the value 0 to represent an unfilled cell, and the values 1-9 to represent themselves. We can construct an empty grid either with a var declaration:

var G Grid

or as a struct literal:

G := Grid{}

Note that Go does not allow us to store nil values in an array of integers. If we construct an “empty” array, it will automatically be filled with the zero value for the type - in this case 0, which is just what we want for an empty cell.

Exercise

Create a file called grid.go in your working directory. Define the Grid type and create methods to retrieve and set the value of an element at a given row and column. You can start with this skeleton:

package main

type Grid [81]int

// ElementAt returns the element at the specified row and column of
// the grid. It returns 0 if the cell is empty.
func (g Grid) ElementAt(row, col int) int {
    // implement this
}

// WithElementAt returns a new grid with the element at the specified
// row and column set to the given value.
func (g Grid) WithElementAt(row, col int, val int) Grid {
    // implement this
}

:bulb: In Go, function arguments and method receivers are passed by value, not by reference. This means it is safe to mutate the value g passed as the receiver above. If our receiver was a pointer instead (of type *Grid), we would have to take more care. Learn more here.

Testing

Let’s write some unit tests for these methods. Test files are named after the source file with the suffix _test added, so create a file grid_test.go in your working directory containing:

package main

import "testing"

func TestElementAt(t *testing.T) {
    G := Grid{} // an empty grid
    for row := 0; row < 9; row ++ {
        for col := 0; col < 9; col++ {
            v := G.ElementAt(row,col)
            if v != 0 {
                t.Errorf("ElementAt(%d, %d) = %d, expected 0", row, col, v)
            }
        }
    }
}

Run go test in the working directory to run the tests. For more verbose output, run go test -v.

Exercise

Add some tests for the WithElementAt method.

What happens if you try to access an element outside the bounds of the grid? Can you test this?

Parsing a Grid From a File

We have provided a few Sudoku puzzles in a simple text format; for example:

010020706
700913040
380004001
000007010
500109003
090500000
200300094
040762005
105090070

We would like our program to take the name of a file as a command-line argument, read the contents of the file, and parse it, returning a Grid data structure or an error if the file was unreadable or its contents could not be parsed.

To make our code easier to test, we will split the parsing of a grid into two functions: one that reads the data from a file, and one that parses the data. In fact we don’t need to implement the first of these functions ourselves, we can use the ioutil.ReadFile function from the standard library.

Exercise

Add the following two tests to grid_test.go:

// TestParseGrid checks that we can parse a valid grid
func TestParseGrid(t *testing.T) {
    data := []byte(`010020706
700913040
380004001
000007010
500109003
090500000
200300094
040762005
105090070`)
    G, err := ParseGrid(data)
    if err != nil {
        t.Errorf("Unexpected error parsing grid: %v", err)
    }
    // Check that row 2 is as expected
    row := 2
    expected := []int{3, 8, 0, 0, 0, 4, 0, 0, 1}
    for col, want := range expected {
        got := G.ElementAt(row, col)
        if got != want {
            t.Errorf("ElementAt(%d,%d) = %d, expected %d", row, col, got, want)
        }
    }
}

// TestParseGridError checks that ParseGrid returns an error when the
// input is malformed
func TestParseGridError(t *testing.T) {
    data := []byte(`01002070
700913040
380004001
000007010
500109003
090500000
200300094
040762005
105090070`)
    _, err := ParseGrid(data)
    if err == nil {
        t.Errorf("ParseGrid() did not return an expected error")
    }
}

Now add ParseGrid to grid.go to make these tests pass:

func ParseGrid(data []byte) (Grid, error) {
    // implement this
}

:bulb: The data here is an array of ASCII bytes. As the ASCII values for the digits 0-9 are contiguous, we can skip over unwanted characters in the input (such as whitespace) simply by checking that the byte value, int(x), is in the expected range.

:bulb: :bulb: We can get the integer value for an ASCII digit by calculating int(x) - int('0').

Printing the Grid

If we try printing our grid with fmt.Println we’ll get Go’s standard representation of an int array:

[0 1 0 0 2 0 7 0 6 7 0 0 9 1 3 0 4 0 3 8 0 0 0 4 0 0 1 0 0 0 0 0 7 0 1 0 5 0 0 1 0 9 0 0 3 0 9 0 5 0 0 0 0 0 2 0 0 3 0 0 0 9 4 0 4 0 7 6 2 0 0 5 1 0 5 0 9 0 0 7 0]

We can override this behaviour by implementing the Stringer interface for our Grid data type. This interface is defined in the fmt package like so:

type Stringer interface {
    String() string
}

Unlike languages like Java, where we have to declare the interfaces implemented by our types, we can simply implement a method on our Grid data type with the correct signature, and hey presto!

Add the following method to grid.go:

func (g Grid) String() string {
    var sb strings.Builder
    for r := 0; r < 9; r++ {
        fmt.Fprintf(&sb, "%d %d %d | %d %d %d | %d %d %d\n",
            g.ElementAt(r, 0), g.ElementAt(r, 1), g.ElementAt(r, 2),
            g.ElementAt(r, 3), g.ElementAt(r, 4), g.ElementAt(r, 5),
            g.ElementAt(r, 6), g.ElementAt(r, 7), g.ElementAt(r, 8))
        if r == 2 || r == 5 {
            sb.WriteString("------+-------+------\n")
        }
    }
    return sb.String()
}

:bulb: You’ll also have to add strings to the list of imports at the top of the file.

Now when we call fmt.Println(G), we get:

0 1 0 | 0 2 0 | 7 0 6
7 0 0 | 9 1 3 | 0 4 0
3 8 0 | 0 0 4 | 0 0 1
------+-------+------
0 0 0 | 0 0 7 | 0 1 0
5 0 0 | 1 0 9 | 0 0 3
0 9 0 | 5 0 0 | 0 0 0
------+-------+------
2 0 0 | 3 0 0 | 0 9 4
0 4 0 | 7 6 2 | 0 0 5
1 0 5 | 0 9 0 | 0 7 0

Excursion: Sets of Integers

In our algorithm description, we get the candidate values for an empty cell by computing the set difference of the set of integers 1-9 minus the set of integers that appear in neighbouring cells (the same row, column or subgrid as the target cell). The core Go language does not include a set data type. An efficient implementation of sparse integer sets is available in the intsets package, but as we are only dealing with small sets (the digits 1-9) we can implement our own, simpler, solution.

For the small sets that we will be dealing with, we can simply store the elements in a slice and check membership with a linear search.

Exercise

Create a file intset.go in your working directory and define the type for IntSet and the methods we will need:

package main

type IntSet []int

// Contains returns true if x is in the set, otherwise false
func (s *IntSet) Contains(x int) bool {
    // implement this
}

// Insert adds x to the set if it is not already present
func (s *IntSet) Insert(x int) {
    // implement this
}

:bulb: Note that we are defining these methods on a pointer to the slice. This is because we want some of the methods to modify the underlying slice.

:bulb: If you are not familiar with slices in Go, you might want to read this article before tackling the exercise.

Create a file set_test.go in your working directory and implement unit tests for the Insert and Contains functions.

Other Approaches

While our slice representation works well for small sets, we would need a more efficient data structure if we were dealing with larger sets. One approach is to keep the elements in sorted order and use a binary search to check membership (see sort.SearchInts). This increases the cost of insertion but speeds up retrieval. Another approach would be to store the elements as keys in a hash map, and use presence in the map to indicate membership of the set. In this case, the value doesn’t matter, and you’ll often see map[int]bool or map[int]struct{} used. The intsets package uses yet another approach, a bitmap.

Back to the Grid

Now that we have our set data structure, we can implement a method to return the neighbours of a given cell. This should return the set of values that appear in the same row, column and subgrid of the target cell. We also need a function to find the first empty cell in the grid.

Exercise

Add these methods to grid.go:

// Neighbours returns the values of the cells in the same row, column, or subgrid
// as the target cell.
func (g Grid) Neighbours(row, col int) IntSet {
    // implement this
}

// FirstEmptyCell returns the array index of the first empty cell in the
// grid, or -1 if there are no unfilled cells
func (g Grid) FirstEmptyCell() int {
    // implement this
}

We can build on the Neighbours function to find candidate values for the empty cell:

func (g Grid) Candidates(row, col int) []int {
    neighbours := g.Neighbours(row, col)
    var candidates []int
    for _, v := range []int{1,2,3,4,5,6,7,8,9} {
        if ! neighbours.Contains(v) {
            candidates = append(candidates, v)
        }
    }
    return candidates
}

Don’t forget to add unit tests for these three new methods.

A recursive solution

We now have all the building blocks for a recursive depth-first search to solve our first Sudoku!

func (g Grid) Solve() (Grid, error) {
    i := g.FirstEmptyCell()
    if i == -1 {
        // No unfilled cells: we have found a solution!
        return g, nil
    }
    row := i / 9
    col := i % 9
    candidates := g.Candidates(row, col)
    // Try each of the candidates in turn
    for _, v := range candidates {
        result, err := g.WithElementAt(row, col, v).Solve()
        if err == nil {
            return result, nil
        }
    }
    // There were no valid candidates
    return g, fmt.Errorf("No solutions found")
}

Extension Exercise (Optional)

Implement Solve using an iterative depth-first search instead of the recursive method above. See the Wikipedia article cited earlier for some pseudocode that might help.

Wrapping It All Up

The final thing we need to do is to flesh out the main function that we started out with in sudoku.go. This function needs to:

  1. Check that there is exactly one (non-program name) command-line argument (the filename for the puzzle)
  2. Read this file using ioutil.ReadFile
  3. Parse the file contents with our ParseGrid function
  4. Solve the grid by calling the Solve method
  5. Print the solution (if found) or an error

Exercise

Implement the body of the main function in sudoku.go to do all of the above. Don’t forget about error handling.

:bulb: See this article for information on accessing command-line arguments.

You can now build an executable command-line program to solve Sudoku puzzles:

go build

Download some of the test grids to try it out: easy, medium, hard, evil.

You can run it by:

./sudoku easy.txt

Congratulations if you made it this far! I hope you enjoyed the tutorial.

Hosting Private Go Modules on GitLab

Jumping through hoops to access Go modules in private GitLab repositories
go gitlab

Go Concurrency

Go mutex vs atomic increment.
go