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!
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 getthe 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!
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.