Sudoku Solver
Solving Sudoku With Python3 And Backtracking
Hi everyone, today we’re going to be creating a Sudoku solver using python 3. In this blog post, I will be going through the game theory and algorithms needed so that you can beat any Sudoku board with ease.
Sudoku is a puzzle game played on a 9x9 board, where the objective is to fill in each square with the numbers 1 through 9. The rules of the game are simple, there can’t be any duplicated numbers in any column, row or subgrid. Subgrids are an internal 3x3 grid inside of the 9x9 board. Below is a depiction of a Sudoku board with the first subgrid coloured green.
The rules are minimal, but these puzzles can be challenging as there’s only one solution for valid Sudoku boards.
Building Sudoku Puzzles
First, we will build the game for generating puzzles to test our solver.
To build the game, we’re going to take a two-step approach. Our first step will be to fill out the complete board with the solution to ensure it is solvable. Then once we know the puzzle is solvable, we will apply a mask.
To ensure we generate unique new boards, we will utilize the random module supplied in the python standard library. Using this library, we will pick random choices from a list of possible values for each square, ensuring we follow the rules.
We will iterate through the game board row by row to create the mask selecting a random set of indexes to keep. As described in the 2012 paper “There is no 16-Clue Sudoku: Solving the Sudoku Minimum Number of Clues Problem”, we know that 17 is the minimum amount of clues needed for creating unique solutions.
Creating unique solutions is critical, as having a non-unique solution would cause the puzzle to be invalid. Since we do not currently have a solver, we cannot validate that our masking function created a unique solution. Because of this, we take advantage of the 17 clues minimum rule and ensure we give more than 17 clues. By doing this, we increase the probability we create a unique solution.
For the sake of this blog, we are using 45 clues since, after testing (I used the solver we’re building to verify), I’ve found it gives a unique solution around 82% of the time.
Simple Solution
Now that we can generate puzzles, we need to solve them. A simple solution to solving these puzzles is a pure brute-force approach. To do this, we will utilize recursion and try out all possible combinations of values. Since there are 6,670,903,752,021,072,936,960 unique possible solutions to the Sudoku board will need to shrink the search space by exploiting the rules of the game.
To exploit the rules, we can utilize memorization and save what values are placed in the current row, current column and current subgrid. This way, we don’t need to try out all combinations of 1 through 9 and instead can search numbers that are not yet used.
Get Ben Bellerose’s stories in your inbox
Join Medium for free to get updates from this writer.
To memorize what’s already in the current row, current column and current subgrid, we can store their values in dictionaries of sets (dictionaries and sets are O(1) for lookups since they use hashes) using their respective index as the key for quick access. Determining the index of the column and row is easy, but finding the index of the subgrid is more tricky. To determine the index of the subgrid, we can use the following equation.
To help speed things up even further, we can use early stopping and return the first viable solution upon finding it. Early stopping will help speed up computation as we no longer need to try out more combinations.
This approach does get the job done by successfully solving the problem. However, it’s not very computationally efficient, and we can do better than this.
Backtrack Solution
A more elegant approach to this problem would be to use a backtracking tree search. We can use backtracking tree search here since we can view the possible combinations as a tree (graph data structure).
Backtracking tree search is an optimized form of tree search where instead of re-starting your search at the trunk of the tree, you prune that incorrect node and go back up the tree and continue down the next option. This way, you save computation by keeping options you know are correct. An example of a possible backtracking path is shown in the diagram below.
With our backtracking algorithm, we still utilize recursion, memorization, and early stopping like our brute force method, except now we pay more attention to the branches (edges) of the tree (graph) and search more efficiently.
Thanks
And there you have it, we have successfully created our Sudoku solver. You can check a full version of the code on my GitHub here. As you might have guessed, we could have used the backtracking algorithm when building our Sudoku game to make it more efficient, and I did in the code on my Github.
Thanks for reading. If you liked this, consider subscribing to my account to be notified of my most recent posts.
