Solving Sudoku Puzzles with Go
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:
Find the first unfilled cell:
Locate all of the neighbouring cells (those in the same row, column or 3x3 subgrid):
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:
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:
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
}
💡 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
}
💡 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.
💡 💡 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()
}
💡 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
}
💡 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.
💡 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:
- Check that there is exactly one (non-program name) command-line argument (the filename for the puzzle)
- Read this file using
ioutil.ReadFile - Parse the file contents with our
ParseGridfunction - Solve the grid by calling the
Solvemethod - 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.
💡 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.