Sudoku Solver GUI

As a kid, sudoku was one of those adult puzzles I hated even coming into contact with because it simply frustrated me to no end. Fast forward a decade or so, and I still don't have the patience to solve any sudoku puzzle thats bigger than a 3x3 grid. That's exactly why I decided that my first major CS project would be an interactive tool that could solve Sudoku puzzles for me, so that I could at least pretend I knew how to solve them.

I completed this project very soon after taking my first Intro to Python class, which gave me enough familiarity with Python basics that I felt confident enough teaching myself how to code recursively and create a program which found the optimal solution in the fastest way possible. It's not perfect, as there are modern Sudoku solvers which can figure out the solution quicker than mine, but it is still a fairly effective program that does generate the correct solution. Without further ado, let's dive right in!

The GUI

This program is pretty easy to understand. By clicking on a square, you can enter a value between 1 and 9. If you need to change the value of a square that's already filled, just click and type the new value. If you want to remove a value, use the backspace key. I've ensured that the program only accepts valid input, so any attempts to disrupt it won't work. Once your board is set up, solving it is as simple as pressing a "solve" button. Here is an image of the initial GUI:

Here is my program solving the apparent "hardest Sudoku board in the world" according to Finnish mathematician Arto Inkala:

One of the most interesting things about the GUI is that you can actually see the program run through possibilities in real time and backtrack itself, which was made possible using a recursive method that I will explain below. If you would like to run this yourself, you can find all the code at https://github.com/pranavgudise/SudokuSolver.git.

The Code

Background and Methodology

Before we jump into the method itself, I want to give some background on sudoku boards which I did not actually know of until I was in the process of making the methods for this project. Before the algorithm begins, the program has to find the an optimal orientation of the board. Sudoku boards are unique in that they can be flipped and be the same board. However, depending on the backtracking algorithm used, the time-to-solve can be made drastically lower. This is because some boards are difficult for normal backtracking methods that solve the board based on the orientation that was given initially. To combat this issue, I created the program such that the first thing it does is find the orientation of the board, which has the most given points near the start (top left corner) of the board. This was done by finding which quadrant (1 is top left, 2 is top right, 3 is bottom left, 4 is bottom right), has the most filled-in squares. This makes it so that the program will have to test less possibilities, as it can get points with limited possibilities near the start of the board (algorithm goes left to right, top to bottom). The program is also capable of mirroring the board if it makes more static points closer to the start.

The Algorithm

So how does the algorithm function? To begin, the algorithm has three main parameters:

1. Original Board - The starting point for the iteration

2. Possibility Board - The starting possibilities of all cells, as derived from the Original board

3. Truth board, a board which is full of boolean values. True signifies that the cell is a given value, False indicates it is one the algorithm must fill in. The cell the function is currently on is marked with 'x,y' coordinates

It then follows a few steps as so (based off a recursive function shown below):

1. It will first establish a possibility board, which in essence lists every possible number a space on the board can be

2. To make the code more efficient, the possibility board can be cleaned. This can be done by using the static cells provided in the puzzle. Using these cells, several possibilities from the cells can be removed.

3. The algorithm then starts at the first non-static cell in the playing board, and extracts all of the cells possibilities from the possibility board. This list of possibilities is referred to as the cache of possibilities for that iteration or frame of that function.

4. The algorithm will pick the first entry in the cache (index 0), and add it to the board. This limits the possibilities for the rest of the board, and thus the possibility board will be updated.

5. This new board and the possibility board are then sent as arguments for the next iteration of this recursive function.

6. This will keep happening until a cell in the possibility board has no values left in its possibility cache, meaning the combinations chosen have made solving the board impossible. When this occurs the function returns false, and returns to the previous iteration. It will then try the next value in its possibility cache, repeating the same process as above.

7. This goes on until the board is completely solved.

The center of this backtracking algorithm is this recursive function:

def solve (self, original_board, possibility_board, truth_board, x,y):

So as to not clutter the page and bore you all, I'm not going to paste the rest of the code here. Of course, if you would like to see the function and the rest of the code in its entirety, you can find it at the Github repository above.

Possible Improvements

So, here's the thing about those backtracking algorithms – they basically go through every possible scenario on the board until they crack the code. Let's say you're dealing with a 3-digit combo lock. You start with 1 and work your way up, like trying 111, then 112, and so on until you hit 999. Now, imagine the actual combo is 999 – in that case, this algorithm is gonna take forever, way longer than usual.

To make things better, you could try different ways to solve the board, such as mimicking how a human would do it, or tweaking where you begin. As of right now, I don't have the Python capabilities to make such improvements, but as I continue learning more advanced Python techniques I will tweak the program to make it more and more optimized.

Conclusion

As a first major Python project, I'm pretty happy with how this turned out. I was also completing this project concurrently with my internship projects, lined here and here, so this side project took far longer than it could have if I was working solely on it. The project helped me understand recursive programming much quicker than I would have in an academic context, and forced me to think outside the box when it came to optimizing my code. It also forced me to consider where I could improve and implement such improvements if I was capable of doing so, one of which being the interactive GUI which replaced an initial iteration which made users change the code itself. Overall, this project helped introduce me to the world of CS projects in a way which I found interactive and enriching!