loading...
Cover image for Critique My Code: Sudoku Solver in Go

Critique My Code: Sudoku Solver in Go

mas profile image Sam P Updated on ・3 min read

Brief Introduction: I'm Sam, and I'm a young software developer from the UK. My main expertise is with Java, however recently I've been expanding my horizons with other languages, like JavaScript (using NodeJS specifically) and Go. I've read articles here before but haven't actually posted anything up until this point, and I thought this would be a good story/exercise to share.

A few years ago (I would have been 11 or 12 at the time) when I had just started really getting into programming with Python, I remember my dad telling me about a challenge by a computing club in Oxford where the goal was to write a program to solve a Sudoku puzzle in the quickest time possible. Being younger, I was amazed at the prospect that some people were able to write programs to do (what I perceived to be) such complex tasks. I specifically remember thinking "I hope I can do that one day".

Jump ahead a few years, and I read this great post about writing a Sudoku solving algorithm by @aspittel (many thanks for the inspiration!)

This reminded me of my past dream to be able to write such a program, and realising I was now several years more proficient in software development, I decided to give it a go for the fun of it (and partly because my dad said that it was a very complex task and he'd be very surprised if I could do it - it's always great to prove a parent wrong!). I decided to write it in Go because it was the most recent language I'd familiarised myself with, and I hadn't yet attempted a project like this using it.

A few days later - and much to my dad's amazement - and I had a working solver in front of me. You can find it on my GitHub (along with other cool projects that you should totally check out 😉), and please go ahead and critique my approach (whether it be the code or the algorithm itself) as you please. As I said, I'm relatively new to Go, so there'll definitely be a few things I could improve!

GitHub logo Mas281 / SudokuSolver-Go

A sudoku solving algorithm implementation in Go

Sudoku Solver

A sudoku solver written in Go
Uses a combination of process of elimination and recursive backtracking




It can solve the vast majority of puzzles in the range of 1-20 milliseconds, with slightly harder puzzles taking up to ~3 seconds (the longest I've found it ever take for any puzzle is 11 seconds, with a devilishly difficult Sudoku I found from an old book of Sudoku puzzles I found lying around). Feel welcome to go get the project and play around with it yourself to see if you can find a puzzle that takes any longer.

To my own surprise, I didn't find the challenge of making the program as difficult as I anticipated it would be. Sure, there were a few hitches (and maybe an hour or two cursing at pointers), but overall I felt like I had achieved my goal pretty well.

If anyone's interested in the technical side of my approach (since it combines both the process of elimination and recursive backtracking), I'd be happy to explain 😃

Thanks very much for reading my first post, I hope it was interesting for you!

Edit: Brief explanation of the method

Firstly, all unsolved cells are iterated through, and a check if performed to find all the possible values the cell could occupy (this is done by checking the row, column, and box of the cell). If there is only one possible value, the cell's number is set to this and the cell is considered solved. This really only tends to happen on easier difficulty puzzles.

If, during the iteration, any cells are successfully solved during this method, another iteration is run afterwards to see if any further cells can be solved using the new values we accumulated from the first iteration. This continues until an iteration passes where no cells get solved (this whole step is skipped if no cells are solved during the first iteration).

The second and final stage is where backtracking comes in to play to solve the rest of the cells for us. I won't go into massive detail here, but it's effectively just a type of brute-force search. If you'd like to read specifically about it, I'd encourage you to read the previously linked article or the section on this Wikipedia page.

Discussion

pic
Editor guide
 

I hate reading i/j and x/y loops, they don't mean anything, I suggest using meaningful names like "column, row".

Is no need to profile your code using start/end timings, there are many other ways (go profilers or a simple bash utilities like time go run ...) that don't require 'polutting the business logic'.

This is for Solve, getUnsolved, getNewUnsolved functions:

//for ...
if i == index {
                solved = append(solved[:j], solved[j + 1:]...)
                continue cellLoop
            }

In go is preferred to keep the "happy line" to the left and use quick exits, something like:

//for ...
if i != index {
continue 
}
                solved = append(solved[:j], solved[j + 1:]...)
                continue cellLoop

There is an optimal way to solve Sudokus, a smarter brute force using the Dancing Links method , although is more complicated to understand and code. There are also implementations on GitHub in C# and Java I think.

 

Thanks for your criticisms, I'll definitely take them into account. I agree with you that some of the loops aren't the most meaningful, and I'll clean that up (the i/j naming for the index in the loops is a habit I've carried over from Java where it's idiomatic).

I'll also make sure to check out that more optimal algorithm.

 

Glad I could help, I love doing Go reviews, it helps me become a better dev.

Whenever you need a PR review just ping me, I'm a rookie to but I'll try my best.

PS: you can use the #reviews channel from the Gopher slack server too

 

This post makes me so happy. 😄

I don't have a lot to offer on the Go critique but I'm excited to read the responses.

Big props to @aspittel for the inspiration.

 

I don't know go, but the first file I saw was this:

func newCell(puzzle *Puzzle, value, row, column int) Cell {
    return Cell{
        puzzle:         puzzle,
        value:          value,
        x:              row,
        y:              column,
        possibleValues: []int{1, 2, 3, 4, 5, 6, 7, 8, 9},
    }
}

and my first thought was, why are the co-ordinates sometimes x and y and sometimes row and column... especially when x normally denotes the columnar position? Does it not matter for the purposes of the solution whether the board is rotated 90 degrees or is this going to cause problems later in the code?

 

I do see what you mean here - I think that specific case is the result of the method parameter names being the wrong way round. It doesn't affect the solving but I'll be sure to fix it in the next commit. Thanks for catching this!

 

I did not look too deeply into the code, but two things jumped out to me.

1) Allocating memory inside (tight) loops should be avoided.
You're creating a lot of Cell objects and arrays for each iteration, try to revise it that you have (most of) the memory and objects you need up front. This goes hand in hand with…

2) By making the Cell type the primary actor of the solving algorithm, each Cell has to recreate its own vision of the world (i.e. the puzzle) from the inside out. If you move the controlling code from the data element to the data container, you can avoid a lot of redundant work. The container knows about all the cells and their layout, best to use that knowledge on that level of abstraction instead of ignoring that information and recreating it for each element. (This is a pretty common OOP-originated performance counter-pattern)

I made a simple implementation and an optimized version of it in a webpage and also put the code in a Gist, check it out and please let me know if this was useful to you. It's JavaScript but hopefully still understandable.

Gist: gist.github.com/zenmumbler/96dcc5e...
Page: zenmumbler.net/suso/

 

Thank you. You present some very valid criticisms and I'll try and iron them out soon.

 

Criticisms - Cynicisms:

  1. Please format the error messages according to the Error style guide. Error strings should not start with a capital letter because they'll often be prefixed before printing. github.com/golang/go/wiki/Errors
  2. The trySolve method name is confusing. A better name will be isSolvable or canBeSolved as it returns a boolean.
  3. The trySolveRecursive method checks what the trySolvedoes in the beginning so you have code duplication.
  4. dev.to/thisleenoble/why-sudoku-are...
 

Thanks for the feedback!

I wasn't aware of the error message convention and I'll make sure to fix that up and adhere to it in future.

Regarding your other comments, I definitely agree the method naming there could be improved, and I'm also going to do a bit of refactoring to avoid the bit of duplication you mentioned.

 

Funny enough I started working on a similar project, an end-to-end sudoku solver on the web. Since I only developed with react, I decided to learn more and set the complete project from the ground up by creating my own webpack/Babel project and using vanilla JS without any helper libraries.

Currently got the core working where the user can input the numbers (and clear them again), but still have to start working on the actual solving algorithm. It's already live here: engineercoding.github.io/SudokuSol... (intentionally not usable on mobile)

Already learnt a tonne, but always open to pointers :)

 

Nice work, I really like the design and how user-friendly it is!

 

I really wanted to do a proper code review with comments or even a PR for you to see a diff. Maybe I will still find some time for it.
Try to avoid counters in foreach. You’re not quite right that this is java way. This is the way you were taught programming. And its not quite right. “One or more - use for” - use it to print 10 lines to console. Don’t use it to iterate over collections. Use foreach (golang has it and you are using it too)

Nested loop is a code smell - at least extract inner loop to separate method.

In general, use power of method name semantics - each time you comment a block of code explaining its purpose - extract a method!)

Naming is hard. Instead of giving methods fancy names, that dont reflect reality, if you cant find a good name at once - be honest. Give your method an awkward name. It will be both an indication of a questionable design and TODO to refactor it, so that these few lines truly deserve a nice short name.

Mid to long term advice - read Clean Code )

 

Thanks for all this, I really do appreciate the feedback, and I'll make sure to take this into account!

 

Great job! I've recently wrote a bot to play a two play version of Sudoku called Sudoku Scramble. The challenge I faced was to make the bot (Woody) play like a human. You can check him out in Sudoku Scramble available on iOS and Android. Www.81monkeys.com

 

Thanks!
I'll take a look at your project, it looks very interesting

 

Ah this is so cool!!! Awesome job!

 

Thanks! And thanks again for the idea :)

 

Hi, interesting project, I'm not a go developer but I'll check it out deeper.
I regret that you don't comment your technique, not the code juste the technique employed. I have to understand the code to understand the logic :) (I don't know how to solve this thing ahah).

I think I'll make it in C to work my Go skills.

Thanks for sharing!

 

Thanks for your comment. I've gone ahead and added a short section to the end of the article with an explanation of the method :)

 

Nice project! I read through and had a couple of points to share:

  • Instead of defining Print, define a String() string method on Puzzle. This will implement the standard interface Stringer and you can then fmt.Println(puzzle) and that will call String() on the puzzle struct.

  • Instead of having a debug field consider implementing a logger with a Debug function and remove the debug field from the Puzzle

  • Since this isn't a main package I'd expect it to be an importable library complete with godocs on exported types. I think this is good reading.

  • I didn't spend too long figuring it out, but I'm guessing the runtime is quite high. Probably will never matter on a 9x9 sudoku grid, but what happens when you move to base 16 and have a 15x15 sudoku grid?:) This question is mostly food for thought, nothing really actionable here unless you were interested in calculating the runtime and trying to optimize.

  • Read more go code! Try reading the standard library for good patterns to follow!

Also I applaud you for sharing your code and asking for feedback. That is not easy to do!

 

Hi Sam thanks for your post and I might have a look at your code. This really reminded me of my own project:
This should not be an advertisement for my blog... I think you might be interested:
opensourc.es/blog/sudoku

Using Constraint Programming for solving sudokus in Python.