Implement a Sudoku Algorithm Without Backtracking [Beginner Python]
Most of the tutorials and algorithms relating to solving Sudoku with a program will point you to a backtracking-implementing solution. Backtracking is an algorithm that recursively tries potential solutions and removes the ones that don’t work. Now, if the purpose is to learn and practice the algorithm, Sudoku will do perfectly fine, but, in many cases, backtracking has a high complexity and tends to reek of lack of properly understanding the problem due to its brute force approach. Let’s dive into how we can do it without!
Understanding the problem
In Sudoku, we need to fill the empty squares (which in our example will be 0s) with numbers (ints) from 1 to 9 inclusively such that they do not repeat in their column, line or 3x3 sub-sections. We can achieve this by trying out different possibilities in the same spot, continuing until something breaks and then revising, but this is not my preferred method of solving the puzzle. What we can do instead is take lines, columns, or 3x3 sub-sections individually and try to see what spots can only have one possibility and complete those. Here is what I mean, using my unbelievable drawing skills:
If I try to complete the some elements on the top row, highlighted in yellow, I can see that I can determine exactly where its 3 value should be. The only possibility is in the position before last. We can repeat this process for every row, column and sub-section. That will not complete the board, but we can do it all over again as many times as necessary until we have completed every position with the only possibility that goes into it, removing the need for trial and correction. Let’s get to coding!
(I will link the source code at the end of the article and will only paste in images)
Setting up
We will use a function based approach here. The board will be kept in an matrix, which is a fancy way of saying an array of arrays or, in Python, a list of lists, where each list represents a row, and it will look something like this:
puzzle = [[8, 7, 6, 9, 0, 0, 0, 0, 0],[0, 1, 0, 0, 0, 6, 0, 0, 0],[0, 4, 0, 3, 0, 5, 8, 0, 0],[4, 0, 0, 0, 0, 0, 2, 1, 0],[0, 9, 0, 5, 0, 0, 0, 0, 0],[0, 5, 0, 0, 4, 0, 3, 0, 6],[0, 2, 9, 0, 0, 0, 0, 0, 8],[0, 0, 4, 6, 9, 0, 1, 7, 3],[0, 0, 0, 0, 0, 1, 0, 0, 4]]
But we can visualize it as below:
That is still not that great, so what we can do is write a function that takes this matrix (from now on called board) and prints it in a more readable and friendly way into the console.
I will not spend too much time on this function, but what it basically does is take the arrays and print them out with the “|” and “-” delimitations we have seen above so that it looks a little more like a real Sudoku board.
Get information about zone
By “zones” we mean row, columns, and 3x3 sub-sections (which from now on we will refer to as squares because they are tiny squares and I was not very inspired when I initially wrote the code. We will keep a list of dictionaries, where each dictionary describes a zone: what kind it is (row, col, square), how many non-zero elements it has already (we will see why in a second), and what coordinates we can find it at: if it’s a row or a col, the coordinates are the indexes where we may find it (just like any other programming language, we start counting at 0) and if it’s a square we can store where it’s top row begins and end and where it’s first col begins and ends.
Since the board is a list of lists, each representing a row, when we want to iterate rows, we can use len(board). To access a particular element we use board[row][col]. The two things missing from the explanation of this function are the generate_square_coords() function that we invoke and the fact that we don’t append a dictionary describing a zone to the list defined at first, but use another function called insert_sorted() to, as the comment says, make sure that the list called zones is sorted in descending order by how many elements (non 0s) each zone already has. Let us explore those in turn.
In here, we make another list where we append dictionaries, with the entries “row_begin”, “row_end”, “col_begin”, “col_end” that we have already seen. It will give us the coordinates for every square on the board and then we turn the list into a tuple before returning, because a tuple is immutable (we cannot change it’s elements afterwards), unlike a list, and we don’t want to accidentally have another piece of code modify those.
Note: this entire square coordinates approach tends to get a little to complex and it is a good candidate for a refactoring!
Secondly, we want to insert our zone-describing dictionaries into the zones list in a sorted way, with the ones having most elements be at the beginning of the list. Why? Because we want to start trying to fill in those first. Since they have more elements, chances are we can find what’s missing faster. The code that does that is below:
Remember that each zone-describing dictionary had a “len” field, where we stored the number of non-zero elements it had.
Recap! We can now:
- Divide the board into zones of rows, columns, and squares
- See how many elements already exist in each zone
- Arrange our zones in a list by how many elements they already have
Insert Possibilities
We have all we need now to start iterating over the board/puzzle and try to determine which positions only support one number and one number only and fill that position. So, naturally, we are going to write a function for that, but let’s first consider how that function should work. We should have the coordinates of the position we are considering (row and col indexes) as arguments. Then, we should see what are elements are on the same row, the same column, and in the same square/3x3 sub-section as the position we are considering. Based on that, we can eliminate the possibilities that go into that slot. If only one possibility is left, we insert it. The code could look something like the one below:
We should note a couple of things here. Firstly, on lines 67 and 68 we use a really nifty feature of Python called list comprehensions. They allow us to quickly generate a list based on some logic that we define between [ ]. That logic allows us to iterate over something and even make some light transformations and filtering. Line 67 is basically saying give me a list of numbers, where every number is from the generator range(1, 10). Say you want the square root of every even number from 0 to 100. You could use a list comprehension such as results = [number**2 for number in range(0, 101) if number % 2 == 0].
Secondly, there is no return here. This function modifies our puzzle variable that resides outside of it. This means that it is not a pure function and you should be careful, since this is not necessarily a recommended approach and people passionate about functional programming will freak out, but for our purposes, this will do.
Lastly, we use get_zone_elements() which we have not defined yet. That function simply has to return elements from the row, col, and square that our position is part of and can be implemented in several ways, so we will not insist here, but you can inspect the code on repl.it.
Wrapping up
We have everything we need to start solving! I suggest putting all functions mentioned above in a separate file and then importing everything into something like a ‘main.py’ where we can write the logic that uses them. What we need to do is get all the zones of our board, and get through all elements in a zone and try to insert a number if that is the only possibility. I mentioned above that doing this once will, generally, not solve the puzzle, so we should wrap all this in a for loop to repeat the logic 2 or 3 times. Here is what I have:
You can find the code here: https://repl.it/@negoitad_/ICHIGO
Feel free to try it out, play around, and refactor here and there where it doesn’t make sense to you. Please reach out if you have any questions and keep being awesome 😎
