I've always been a huge fan of sudoku puzzles in their many iterations, so it was kind of a no-brainer for me to try to solve them 'once and for all'.

I remember the first time I saw a sudoku puzzle. It was in a newspaper I was looking at while I was at the table with my parents and the 'not-quite-math, but math' aspect of it just clicked with me. Having to logically determine which number goes where based solely on known information and following a set of rules resonated with my interest in programming, logic, mathematics, and, to an extent, gaming. It was a more refined Minesweeper that didn't feel unfair or require any guessing. It was also cool to see multiple kinds of sudokus, from the vanilla 9x9 with 3x3 regions, to those with not jigsaw shaped regions, some with diagonals and some with additional 3x3 regions (hyper-sudoku). There were even some that had variations on size or some where it was two or more connected puzzles.

Doing all these sudoku puzzles also opened up my puzzle worldview. Normally I only knew of the typical crosswords and logic puzzles, but there were so many others! Specifically sudoku introduced me to puzzles such as nonograms (picross), kenken, and Japanese puzzles created by Nikoli. I spent much time trying all sorts of puzzles, which was great for my brain, but horrible for my time management.

Getting back to the subject of the matter. In 2016 when I was looking for a project to use to teach myself Python I figured why not try to create a program that solved sudoku puzzles. I figured I was pretty good at doing them myself (other than some of the harder ones), so how hard could it be to write a program to do it? Boy was I almost wrong. There are a lot of way where we take for granted the way our brains work, and translating that into an algorithm is not always light work. But at the end of the day, I was able to put together a somewhat crude solution that represented a sudoku puzzle as a grid and did a whole bunch of work to solve them using lots of arrays and loops.

Fast forward to 2021 and I thought it was about time for me to update my old program. I knew I could do better both in terms of the structure and the logic. I first took to abstracting the problem. In my original iteration the program was technically one file with a class, but in my new version I decided to actually separate the files and create more classes. I went from just having a class that represents a sudoku cell, to also having a class for a sudoku region (a collection of cells) and a sudoku puzzle (a collection of regions) with each class having functions that do the appropriate work. I had a big "A ha!" moment when I was on a walk with my wife, son, and dog (one of many of these moments during walks) where I realized that sudoku columns and rows are just regions with specific meaning and they function just as the 3x3 grids, jigsaw shapes, or diagonals do. This also made me realize that generally most sudoku solving techniques are relegated to one region and and looking at the potential options for each cell.

There are many other things I can talk about, such as brainstorming ways to make the program require less computing time and space (thinking of you, Big-O) or adding additional solving techniques (currently it only does hidden singles and naked singles and pairs), but those stories might come at another time, as this post is getting long enough. For now, I'll keep hacking away at this 'problem' and doing more puzzles.

(Image Note: Bridging the gap between physical and digital sudoku)

Image credit:

"Nixie sudoku" by TeaWithBuzz is licensed under CC BY-NC-SA 2.0