Building a Sudoku Solver and Generator in Python (2/3)
Creating the Solver
Welcome back to part 2 of this 3 part tutorial, in this section we will create the solver for our sudoku engine, so let’s get straight into the code. But, firstly we need to create two methods which will aid the main solving method.
Here we iterate through the board and return the row and column in a tuple of the index position of the first empty square we come across, if there is no square then False is returned otherwise.
Next we will create a method which can check and tell us if a number can be inputted in a certain cell or not:
This method has two required parameters being a number which is trying to be inputted into a space, which is the second parameter and is a tuple containing a row and column index. The method will first check to see if the number which is trying to be placed in a space appears at all in the same row or column, if it does then that number cannot be placed there and False is returned. Next an internal box 3x3 box is checked and if the number already occurs in the box then False is returned. If nothing is returned so far then the space where we are trying to place the number is deemed valid and True is returned.
Finally, to create the solver we need to think about how we will solve any sudoku board, I created some pseudocode to represent the solving algorithm:
After converting this into python, we get:
In this method we will create the solving algorithm which will harness the power of recursion to implement a backtracking solution to complete sudoku puzzles. Firstly, any empty cells are searched for, if there are no empty cells then True is returned as the function has reached its base case, otherwise the function continues.
A for loop then increments the variable n from 1 to 9 inclusive, during each iteration it is checked to see if n can fit in the current empty space, found by the findSpaces method earlier. If it can then that space is populated with the value n and the solve function is recursively called until a base case is reached, which occurs when either there are no more spaces left on the board or no number can fit in the empty space. If the later occurs then False is returned and the board is not returned, instead the space which was previously populated by the value n, is reset to 0 and the for loop continues.
We can also create another method which converts the solved board into a code which can be easily printed out and stored:
Getting started with Generation
To generate a sudoku board which can be filled out as a question, we first need to create a board which is filled of numbers which are fully valid (follow the sudoku rules). To do this we can use a simple little trick and some more recursion to generate a fully populated board. The trick we will use speeds up our generation time by a small amount, but something is better than nothing right? This is how it works:
In this diagram you can see 3 internal boxes in one diagonal line, the contents of the pink box do not interfere with the contents of the blue and green boxes, and vice versa. To start with the generation process we can create a method which generates a fully populated board:
In the method above we go through each of the 3 internal boxes and populate it with a number 1–9, whilst making sure the number cannot be repicked randomly by removing it from our temporary list of numbers. At the end, the private generateCont method is called, this is so it can fill in the rest of the 54 empty cells on the board. This is what that function looks like:
This method is also recursive since it calls itself during the process of generating a populated board and follows a very similar principle to the solve method. It works by iterating through the board and choosing a random number, and if the current cell is an empty one then it will try and place the number there if it is allowed and then check to see if the board is still solvable. If it is solvable then it will move onto the next cell, otherwise it will reset the value of the cell.
Final Thoughts
This was part 2 of the 3 part sudoku solver and generator tutorial, in the next part we will finish off our generator by making sure that only one solution exists for each sudoku created. Make sure to comment any queries and thoughts you have below.
Click here for part 3.
Thank you for reading part 2! 💖
