Solving Sudokus with backtracking in Python

Sudokus is something that has always caught my attention and, when I learnt about backtracking during my degree in computer engineering, in the artificial intelligence subjects, I came up with the idea of solving sudokus using this method.

It is a very fun problem to solve, so today I want to tell you about these two concepts: what a sudoku is and what backtracking is. In addition, we are going to create a program to solve it using Python.

What is a soduku?

Sudoku is what is known as a pastime, a logic game or puzzle with a mathematical basis, which is generally quite popular (there are thousands of apps). The problem consists of solving a grid (or vector/matrix) of 9x9 squares, which is divided into 3x3 subgrids, rows and columns. The objective is to fill the grid (the 9x9=81 squares) with the numbers from 1 to 9 according to the following rules:

• No numbers may be repeated in the same row.
• No numbers may be repeated in the same column.
• No numbers may be repeated in the same 3x3 sub-grid.

A game, which usually has a time meter so you know how fast (or slow) you solve it, is given a set of numbers that are already given and your goal is to fill in the whole grid using logic and deduction. It's a bit like a simple chess game, allowing you to develop different types of thinking by exploring solutions, discarding paths from the decision tree and choosing the best potential solutions.

What is backtracking?

Backtracking is a technique used in computer science to solve problems that have a set of constraints. The strategy consists of exploring the tree of solutions and, when we are on a path that does not meet the constraints (it is invalid), we discard it, return to the previous state and continue. The good thing about this technique is that it allows us to prune the solution tree avoiding exploring invalid branches, which reduces the execution time.

Whenever I talk about this kind of problems I always like to mention the big O notation, because an algorithm, no matter how inefficient it is, can be very fast when the input is small, but very slow when the input grows just a little bit. Therefore, depending on our problem, we will have to evaluate which option is better.

Backtracking will allow us to try brute-force solutions in our sudoku, and those options that do not satisfy the sudoku constraints will discard multiple branches of the solution tree.

If we apply combinatorics we have that in a soduku there are 81 squares, and we have to fill them with 9 groups of numbers in the range 1 to 9] without repeating. This gives us that a group can be arranged in 9! ways, and we have to choose 9 groups, so we have 9!^2 possible solutions of which most of them will not meet the constraints.

The good thing about backtracking is that it allows us to discard many of these solutions without having to explore them completely, and on the other hand, we are talking about a relatively small number of solutions, so a computer should be able to explore them fairly quickly. There are other problems that are much more complex and cannot be calculated as quickly as this one, but we can talk about that in another post.

Solving a sudoku with programming

The first thing we have to do is to think about how we are going to model the data structure in order to be able to do the backtracking. The idea is as follows:

We start at the first position of the sudoku. For each position, we check if the box is already given or if we have to fill it in. If we have to fill it, we try the first number (1) and check if it is valid or not. If it is not valid, we increment and check if it is valid. If we reach 9, then we have reached a branch of the solution tree that is not valid and we have to backtrack to the previous position, clearing the current cell and incrementing the previous cell. If it is valid, we move to the next cell and repeat.

This would be our algorithm. The data structure can be a matrix, an array... whatever is easier. In my case I think I'm going to go for an array as it makes the calculations simpler.

So, the program will consist of several stages:

1. Read the file with the sudoku data. There are sudokus with different levels of difficulty, so we will always start with a simple one.
2. We start with the algorithm by testing solutions.
3. We validate the row, column and the 3x3 submatrix.
4. We repeat until the program finishes (if we have made a mistake it will remain in a loop).

The truth is that the idea is simple and the next thing you can do is try to solve it yourself, see the code in the following GitHub repository or watch the youtube video at the beginning of the video where I build the solution live.