Ya I really suck at Sudoku and despite my inability to complete a Sudoku puzzle, I decided to create a program that could solve any Sudoku puzzle, so by extension I also have the ability to solve any sudoku puzzle.

This program was done right after I had just completed my 0 or 1 Digit detector. As such, I was feeling better about creating half-decent GUI’s in Python, though I am still a ways off being fully competent. Either way let’s take a better look at my Sudoku solver!

The Program

This program is fairly self-explanatory, you click on a square to input a value that can range from 1-9, to edit the value of an already assigned square, just click and type in your new value or backspace if you want it to be blank. I designed my program to only allow users to input valid boards (so don’t even try of trying to break it). Then once you have your board loaded in, it’s as simple as pressing solve! I will have some images of the program below.

⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀Figure 1: Default start screen of program

⠀⠀ The cool thing about this program is that you can actually see the board go through its backtracking routine! This means you can see it going through the various possibilities right in front of you, which I thought was really cool. Moreover, below you will also find the result of running the “hardest sudoku board” (or the hardest board according to Finnish mathematician Arto Inkala) through my algorithm.

⠀⠀Figure 2: The “hardest Sudoku board"⠀⠀⠀ ⠀ Figure 3: “Hardest” Sudoku board solution

I would put a gif to show the process, but the quality would be abysmal, so I encourage you to try it out yourself. If you want to access this project, it is available on a Github repo available here. If you wish to use git, execute the following in bash:

git clone https://github.com/LangLazy/SudokuSolverGUI

Improvements

Now the potential issue with backtracking algorithms, is that it essentially is systematically trying all of the possible board states until it finds the answer. An example would be if you were trying to find the value of a 3 digit combination lock. If you were going to start with the first digit being 1 and move on in that order, you would first guess 111, then 112, and so on. This means you would guess 999 last. Now notice if the value of the lock were to be 999, your algorithm would take a very long time (compared to the average). The same can be said for my backtracking algorithm. I’ll spoil it for you now, my algorithm goes from the bottom right corner to the top left corner. So this means if you wanted to abuse this property, all you would have to do is pick large numbers (like 9,8, etc) for the solution to those spots. By doing so, you would increase the number of trials by orders of magnitude as combinatorics would tell you, as my algorithm would have to check 1,2,3… and all of their possibilities before even making it to the higher values, thus taking more time.

Now if you wanted to improve this, you could use various other methods of solving the board, such as mimicking a human, optimizing the starting position, etc. I have no idea when I’ll get time to implement these needed upgrades but I guess time will tell.