This weekend I decided to take the golang challenge #8 which is to implement a sudoku solver. Sudoku is a fairly straight forward puzzle. Given a 9x9 matrix, with some positions in the matrix filled out, your task is to solve the remainder of the matrix with the following rules:
- Each position in the matrix must contain 1-9
- Rows in the matrix must have unique numbers
- Columns in the matrix must have unique numbers
- “Unit Squares” consisting of 3x3 sub matrices must have unique numbers
The challenge specified the “input” format of a puzzle to be solved as below:
You can see from the above input sample, the input consists of single digit
unsigned integers, underscores, spaces and newline/linefeed ascii characters.
The required output of the application is the filled in completed puzzle, OR something informing the user that the puzzle isn’t solvable.
Of course, I started this challenge with the inputs/outputs. I figured, what better way to have some data to play with, if I am able to correctly parse the stdin input and write to the stdout output. This brought me to create a custom scanner in golang.
bufio package in the stdlib for golang is pretty neat, as it will allow
the implementer the ability to make custom
Split functions in order to create
your own scanner. Below is my puzzleScanSplit function that I feed into the
bufio scanner, to parse and validate the input is correct:
In the above code, you can see we are basically extending the
split function for the
bufio.Scanner and performing validation checks on the
input, for example, making sure there is either a number or underscore on even
characters, as well as making sure spaces are in the right place, and the row
length is correct.
This function is used in ParsePuzzle to create a new puzzle from an
which in our applications case is
os.Stdin, but awesomely, for unit tests, we
strings.NewReaders as our
io.Reader of choice.
io.Reader in golang is an interface, so I felt like this ParsePuzzle signature
would be really flexible. In this snipit you can see we are actually creating a
in the above we are using our scanner with our custom splitter on the reader, and validating the number of rows is correct. We are then taking the ascii value from the scanner, and converting it into it’s uint8 representation. Underscores are replaced with unit8 0 values.
Part of the requirement was to output a fully populated solution, so to those
ends I went about making a
Dump(io.Writer) method on the Puzzle struct as
seen here. What I really enjoy about golang is what interfaces bring
to the table. Since I am taking a writer as my function input, I could care
less about it’s implementation, I know for sure it will have a
which I can use to write to it. Much like for the inputs, I am able to use
os.Stdout in the application, and in unit tests I can use
any number of things that implement the writer interface. Pretty sweet.
So, now for the actual solving of the sudoku…. well I am partial to backtracking, what can I say, I do it a lot ;)
Backtracking is a means to solve puzzles where you make guesses, and see how they will pan out in the long run. As you can see the implementation of a simple sudoku solver is literally the smallest segment of code in the entire project.
Walking through this code, we perform the following steps:
- Iterate over all the rows
- Iterate over all the columns
- Iterate over all the possible values, if the position we are on is blank
- Check if that possible value is allowable ( check row, column, unit square for uniqueness)
- If allowable, start this whole process over again, with that position filled in
- If no possible values are allowed, this is a dead branch, return to previous caller
- Iterate over all the columns
Backtracking is merely a depth first traversal of a tree, but what I love about recursion, is that the application stack (the function calls) builds the tree, and the logic within the function tells you which branches you can skip, and prune.
My solver works for solving sudoku. Below is what I have been getting when running benchmark tests for the solve on a simple sudoku puzzle:
here is the source code of this implementation.