Sudoku with Go
Mihalis Tsoukalos reveals how to write Go programs that check whether a Sudoku puzzle is correctly solved or not.
Mihalis Tsoukalos reveals how to write Go programs that check whether a Sudoku puzzle is correctly solved or not.
Struggling with your Sudoku puzzles? Then we’re here to make the life easier, although you’ll have to do some Go programming along the way, so… Although the difficulty of a Sudoku puzzle depends on how many numbers you have when you are solving it, this tutorial won’t be dealing with that aspect of designing Sudoku puzzles.
We’ll be coding two versions of the Go program, but both versions read the Sudoku board from a text file. The main difference between the two will be the way they access the elements of the Go slice that stores the Sudoku puzzle. Our final step will be benchmarking each to find out which one is faster. Finally, you’ll see how increasing the size of an array or a slice affects the performance of a program.
What is Sudoku?
Sudoku is a game of numbers. Although the game contains numbers, it’s not about mathematics but about constraints and logic. Each Sudoku puzzle occupies a 9x9 grid that’s also divided into a 3x3 grid – each element of this 3x3 grid (box) is a puzzle on its own with a 3x3 grid that contains nine numbers.
The permitted numbers on a Sudoku puzzle with a 9x9 board can range either from one to nine or from zero to eight. All Sudoku puzzles used in this tutorial will expect numbers from one to nine, but generally speaking you can use any nine numbers you want. However, if you’re going to use different numbers, you’ll need to make changes to the Go code in this tutorial.
The first check that needs to be performed is whether each one of these nine boxes contains all numbers from one to nine. This means that each one of these numbers should appear only once and that all nine numbers should be present. Additionally, there are two more checks that need to be performed, which have to do with whether each column and each row of the Sudoku board contains all the available numbers without duplicates. Although most Sudoku evaluations fail at the first test, there’s a possibility that they might pass the first test and fail in the other two.
Because we’re trying to solve the problem using a computer, we’ll have to perform all these tests and either stop as soon as one of the test fails or continue until all tests are successful. In the first case the Sudoku puzzle is incorrectly solved whereas in the second case the Sudoku puzzle is correctly solved.
Importing puzzles
We’ll need to figure out a way to import Sudoku puzzle as a file. Generally speaking, using files for such operations is versatile and enables the easy transfer of Sudoku puzzles between different computers.
As a Sudoku array has nine rows and nine columns, you’re going to read 81 numbers from one to nine. However, any error checking of the numbers will be carried out at a later stage because the importFile() function, which will be responsible for reading the plain text file with the Sudoku numbers in the forthcoming Go programs, should be as generic as possible.
The only thing that the importFile() function will check is whether it reads valid integer numbers or not. Put simply, importFile() will accept negative integers or integers bigger than nine, but it won’t accept the value “a”, which isn’t a number or a float. The only other test that importFile() will perform is making sure that all the lines in the input file have the same number of integers. The first line of the input text file is the one that
specifies the number of columns that should exist in each input line.
For reasons of simplicity, the loadFile.go Go file will only contain the implementation of importFile() so that you can test its validity before using it in another program. The implementation of the importFile()
function with all the checks can be seen in the screenshot ( left). What does this code do? First, the importFile() function takes a single argument and returns two variables: a slice that will store the contents of the input file and an error variable. If there’s no error, the value of the error variable will be nil – otherwise it’ll contain the error message. In the latter case, the value of the slice variable will be nil. The following if statement is used for checking whether or not all the rows of the slice have the same number of integers: if len(temp) != len(mySlice[0])
This code checks the number of elements in the current value of the temp slice and compares it against the number of elements in the first row of the mySlice slice. This means that the first line of the input text file specifies the number of elements that you expect to see in every other line of the input text file. If there’s a difference between these two values, the importFile()
function will return nil as the return value for the slice as well as a error variable with a custom error message!
Verifying puzzles
The first version of the program will be saved as sudoku.go. The following code from sudoku.go shows the for loops involved in accessing all the elements of the Go slice. Note that between these for loops there’s additional Go code that’s not shown here: for i := 0; i <= 2; i++ { for j := 0; j <= 2; j++ { for k := 0; k <= 2; k++ { for m := 0; m <= 2; m++ {
As you can see, to access all the elements of a Sudoku puzzle, sudoku.go uses four for loops. Although using four for loops for a 9x9 array might not be a performance issue, it would definitely be a problem if we had to work with a much bigger array. Accessing the elements isn’t enough – we need to perform two more checks in the validPuzzle() function: if val > 0 && val < 10 { if mySlice[val-1] == 1 { fmt.Println(“Value appeared two times!”) return false
} else { mySlice[val-1] = 1 }
}
So, if a value in a box appears more than once, the Sudoku puzzle is invalid, which means that the program must end immediately. Moreover, if a value is greater than 10, equal to 10, smaller than 0 or equal to 0, then
we also have an invalid value, which will also end the checking process immediately. These two requirements also make sudoku.go a little faster in case we’re dealing with an incorrectly solved Sudoku puzzle.
The final version of sudoku.go will contain the improved version of validPuzzle() and can be seen in the screenshot at the bottom of page 89.
Improving the solution
Although the previous solution works, it might be possible to optimise it a little – this section will show you how. The general idea here is that in order to be faster we might need to access all the elements of the slice in a different way. The presented solution will use two for loops for accessing all the items of the slice, which would have made a big impact if we had to work with slices with more than 50 columns and 50 rows.
The logic of faster.go that enables you to access all the elements of the Sudoku puzzle can be found in the following Go code: for i := 0; i <= 8; i++ {
for j := 0; j <= 8; j++ {
Note that the main logic behind faster.go is the same as in sudoku.go – the only difference between these two implementations is the way each program accesses the items of the slice that represents the elements of a Sudoku puzzle. The screenshot at the top of page 89 shows the Go code of validPuzzle() as found in faster. go. Once again the implementation of importFile() can seen in the screenshot on page 88. The implementation of validPuzzle() in faster.go is smaller and more elegant than the one found in sudoku.go.
The next two sections will benchmark the two solutions in order to find out whether there is any performance gain when you’re using two for loops instead of four to access all the elements of a Go slice.
Algorithm benchmarking
We’re going to compare the performance of sudoku.go and faster.go in two different ways. The first way is the simpler of the two and includes the use of the time utility. The next section uses a more sophisticated method.
The screenshot ( belowleft) shows the output of both sudoku.go and faster.go when using time. Unfortunately, for such small tasks, it’s difficult to quantify the performance difference between sudoko. go and faster.go using time. The output of time would have been more accurate if we were testing sudoku.go and faster.go multiple times using a large sample of Sudoku puzzles – Go can help you with this, so in the next section you’ll see the Go way of writing more intelligent benchmarks with the help of Go benchmark functions.
Sometimes the Go compiler can optimise the given code behind the scenes. Because slices are popular data structures, their access method is usually one of the first things a compiler tries to improve.
Benchmarks in Go
Go enables you to write benchmarks to compare the performance of different function implementations, so in this section we’re going to write some Go benchmarks to compare the implementations of the validPuzzle() function of sudoku.go and faster.go.
The Go code for benchmarking the two functions will be the same. However, we’ll need to create two new files: one for sudoku.go and another one for faster.go, which will be called sudoku_test.go and faster_test. go, respectively.
The important Go code of sudoku_test.go and faster_test.go, which has to do with the implementation of the benchmark function, is the following:
func BenchmarkValidPuzzle(b *testing.B) {
benchmark_validPuzzle(b, “./OK.txt”) }
func BenchmarkInValidPuzzles(b *testing.B) { benchmark_validPuzzle(b, “./noOK1.txt”) benchmark_validPuzzle(b, “./noOK2.txt”) }
The BenchmarkValidPuzzle() function checks a valid Sudoku puzzle whereas BenchmarkInValidPuzzles() processes two invalid Sudoku puzzles. The screenshot ( above) shows the benchmarking results for both sudoku.go and faster.go. Each benchmark is executed in two ways: first, the regular one and, second, using the -benchmem parameter that displays information about the memory usage of each benchmark function.
So, what do the benchmarking results tell us? First of all, they reveal that the performance of both faster.go and sudoku.go is almost identical. This mainly has to do with the fact that we’re working with a 9x9 slice, which is very small. Additionally, as both Go programs have to access the same amount of elements, it’s logical that they require the same amount of time to do that.
So, why the need for having two solutions? First, the solution in faster.go is much more elegant than the implementation of sudoku.go mainly because there are fewer for loops involved; and second, it’s always good to try to make things to work a little faster!
Bigger slices of pie
The final section of this tutorial will benchmark a Go program that accesses bigger slices without performing any computations. The slice will be populated with randomly generated numbers from one to nine. This slice can have a variable number of rows and columns – however, if no command line argument is given to the program, the slice will have 1,002 rows and 1,002 columns that will be accessed in boxes (3x3 grids).
The name of the Go program that will include the implementation will be big.go while the benchmark functions will be included in big_test.go. Please note that the Go code that enables the program to access all the elements of the slice is similar to the way the validPuzzle() function in faster.go accesses all the elements of the slice.
The big_test.go contains three benchmark functions. The first one uses a slice with 1,002 rows and 1,002 columns, the second one a 102x102 slice and the last one a 9x9 slice. The Go code of the last one is as follows: func Benchmark _9_ access Puzzle(b*t est ing.B ){ var r bool sl := createSlice(9) for i := 0; i < b.N; i++ {
r = accessPuzzle(sl, 9) } result = r }
The reason for storing the result of accessPuzzle() in a variable named r and using another global variable named result afterwards is not straightforward. Suffice
to say that this technique is used for preventing the compiler from performing any optimisations that will exclude the function that you want to measure because its results are never used. This also happened in faster_ test.go and sudoku_test.go. This is a very common technique when writing benchmark functions in Go.
The benchmark results of big_test.go can be seen in the screenshot ( below). Please ignore the “no tests to run” warning in the output because it refers to the unit tests that we didn’t write – newer versions of Go don’t display that warning. As you can see, the number of elements in a slice or an array makes a big difference in the performance of a program, which accesses all the elements of the slice or array.
Please feel free to look at big.go – it will enable you to understand it in more detail. And then, when you’ve grasped the various concepts, start solving Sudoku puzzles and give your brain a bit of a workout!