Building a Sudoku Solver and Generator in Python (3/3)

Finishing the Generator

When we play a sudoku 98% of the time we expect there to be only one solution, hence we need to generate sudokus which only have one solution so we can mark it right or wrong. For this we need two helper functions and one main function which is called during the generation of the board. The general idea is that we find the different empty positions on the board, and on each position solve the sudoku board and check to see how many solutions there are in total.

Firstly, we will create two helper methods, similar to how we did things for the solver, which will allow us to get a list of all the possible solutions to a given sudoku board

This is the solve method which is used to find the number of solutions to a given sudoku board, it takes in two arguments which corelate to a starting row and column, from there the sudoku is solved using our traditional solve method. This is so a sudoku can be solved from multiple empty spaces on the board.

The next method is to find the first empty space it comes across, but with a twist of course (otherwise why would we make another method?):

This method takes in a board as a parameter, which might feel weird since we have been working with the board attribute until now, as well as an integer. In the method a variable is incremented as each empty cell is found, however if the variable is equivalent to the integer passed in as the second argument, the row and column for the current empty cell are returned inside a tuple.

The next method we will code is the main method which returns the number of solutions to a particular sudoku board:

This is the main, public method which can be called to find the number of solutions to the current board. The variable _z is firstly set to the number of empty cells on the board and a for loop is created to iterate through _z many times. During each iteration, a deepcopy of the current object is created. This is so we can edit a copy of the board object it without affecting the main object. Using this board copy the two helper functions are called and the solution to the board is appended to a list of solutions. In the end a list of a set is created of the list of solutions, this is to remove any duplicate solutions from the list.

Finishing it all off

To finish everything off, we need to create one last method which will generate a sudoku board with cells erased, as well as the solution to that board:

This public method takes in a fully populated board and a difficulty as arguments. Another deepcopy is made, this time of the populated board. There are 3 levels of difficulty and each level depicts how many squares, out of 81, are removed from the board. The more squares removed, the harder it will be but also the longer it will take to generate the board.

Firstly, over 3 while loops, 12 squares are erased from the full board. Then while the current value of counter is less than the number of squares to remove, the program will continue to remove random squares. The counter will only be incremented if there is one solution to the board, otherwise the square which was selected to be erased will return to its original value. Once we have reached a state where there is only one solution to the sudoku and there have been enough cells removed, the question board and the solution board (the fully populated board) are both returned.

Of course we can package this function into another method which only takes in the difficulty as a parameter and calls this main function, as well as the method which generates a random complete board. These are then both returned in the code format:

Final Thoughts

So this concluded my 3-part tutorial on how to make a solving and generating sudoku engine, here is a quick example on how you can use it within your own scripts:

If you liked this tutorial, have any questions or advice, then please feel free to leave a comment on here, I’ll be sure to answer them.

Thank you for reading! 💖