Introduction
This post will deal from another point of view with one of the most popular games that can be played on paper, the Sudoku. The objective will be to explain an algorithm for solving it, together with the code that will allow us to solve it. We will start with a short introduction of the rules of this game, so if you already know them feel free to skip to the next section.
Sudoku Rules
The rules of this game are a priori simple:
- Starting from a board formed by 9 rows and 9 columns we must fill all the squares with numbers from 1 to 9.
- The squares must be filled in such a way that each row, block or column of the sudoku contains all the numbers from 1 to 9 without repeating.
Red: column. Green: row. Violet: block. Yellow: cell.
In addition, we will refer to the Sudoku cells as a pair of values indicating the position of their row and column respectively. Thus, when we refer to the cell (2, 8), we should refer to the cell in the second row and eighth column.
Finally, it should be noted that a well-constructed Sudoku has a unique solution. This is possible because we start from certain values in the Sudoku which allow us to complete the cells until all of them are filled.
Solving method
When faced with a Sudoku, we propose three different logical approaches to solving it. To explore them, we will start with a Sudoku and apply different techniques to solve it.
Basic Filler
Given a cell of a board, we know the 3 conditions that a number must fulfill to be a candidate to fill the cell. The number must be unique in the row, in the column and in the block.
Thus, we have a set of feasible solutions per row (F), column (C) and block (B). The intersection of these three sets will give us the set of feasible solutions for a cell. When such a set has only one element, then the only possible solution is that element, so we could cover the cell with it.
Example: Given the image above, we will look at the cell marked in red. In this cell, the workable solution sets are:
- F = {1, 2, 3, 4, 7, 8, 9}
- C = {1, 2, 3, 5, 6}
- B = {3, 4, 5, 6, 8, 9}
Thus, the intersection of the three sets will be F ∩ C ∩ B = {3}. Since the only feasible solution is 3, we fill the cell with the number 3.
Deep Filler
The above mechanics may not work to complete all Sudoku cells. In this scenario, to complete a cell, we will use the information from the cells in its same row, column or block.
We will perform this as follows: given a row/column/block, if we know that a number is feasible in a cell and it is not feasible in any other cell in its same row/column/block, then that number has to complete that cell.
Example: Continuing with the previous Sudoku, we will now complete the cell in the fourth row and first column. The feasible solution sets for the uncompleted cells in the first column are:
- (2, 1): {1, 5, 7}
- (4, 1): {4, 9}
- (5, 1): {5, 6, 9}
- (7, 1): {5, 6}
- (8, 1): {1, 5, 6, 7}
- (9, 1): {1, 5, 6}
As we can see, in the first column, the only cell that admits the number 4 as a solution is (4, 1). Since it is a requirement that all columns contain all numbers, then we fill cell (4, 1) with the number 4.
Guess Filler
Finally, we will evaluate the scenario in which it is not possible to complete any of the cells using the above methods. When this happens, we will look for the incomplete cell with the least number of feasible solutions and perform a very human solution, try one of the arbitrarily selected options.
This will allow us to continue completing the rest of the Sudoku cells. If we reach a situation where a cell cannot be completed without breaking the Sudoku rules, then we will know that the option previously taken is incorrect. In this way, we can try the different options in a cell until we reach the correct solution.
It is possible that, after having selected a value using the Guess Filler method, it may be necessary to use it again. This would result in having to explore each of the alternatives until the correct solution is reached.
Example: We have continued developing the previous sudoku until we have reached the situation we see in the image above. In this case, we cannot apply neither the Basic Filler nor the Deep Filler to complete any of the boxes. To continue advancing in the solution of the Sudoku we will do the following.
- We will look for one of the cells with a minimum of feasible solutions. In this case the cell (1, 3) has as possible solutions the set {1, 6}, being this one of the cells with a smaller number of feasible solutions.
- We will arbitrarily select one of the options and continue completing the sudoku. Let’s assume that in this case we take the number 6.
- We continue to complete the Sudoku until the end. In case we find a cell with no possible solution, we will go back to the previous board and select the other alternative.
In this case, taking the number 6 in the cell (1, 3), we arrive at the board that we can find in the image below. As we can see, the square located in the position (7, 6) has no possible solution. Thus, we discard the 6 as a possible solution of the cell (1, 3) and we will keep the 1.
Algorithm for Sudoku solving
We repeat these steps until all the cells of the Sudoku are completed:
- Basic Filler:
- We go through all the cells of the board looking for the workable solutions for each cell.
- In those cells in which the solution is formed by a single number, we will fill in those cells.
- If at least one cell has been completed, we advance to Step 4 (Checks). If none are completed we will proceed to Step 2 (Deep Filler).
- Deep Filler:
- We go through all the cells of the board again, but in this case using the feasible solutions of neighboring cells to fill in a cell.
- If at least one cell is filled, we advance to Step 4 (Checks). Otherwise, we proceed to Step 3 (Guess Filler).
- Guess Filler:
- We will start by searching for a cell with a minimum set of possible solutions.
- After that, we will make a backup copy of the board and the possible solutions of the cell.
- We will take one of the possible values of the cell.
- We advance to Step 4 (Checks).
- Checks:
- We check if the current solution is valid and, if so, we return to Step 1 (Basic Filler).
- In the scenario where the solution is invalid, there are two alternatives. If we have any backup copy of the board taken when we did backtracking, we go back to the last copy and return to Step 1 (Basic Filler). In case we do not have any backup, we conclude that the Sudoku is unsolvable and we terminate the algorithm.
Backtracking
The technique used in Step 3 of the algorithm is known as backtracking. It is often used in situations where several options must be explored to find a viable solution. In this way, we will try different solutions and backtrack when the particular branch does not lead to the desired solution.
The backtracking process is implemented through a deep search in a tree of possible solutions, where each node represents a decision and each branch represents an option. When a point is reached where there are no viable solutions on a given branch, the algorithm backtracks to the previous node and explores other branches.
Furthermore, in the proposed algorithm, we have bounded the complexity of the tree by using Basic Filler and Deep Filler to complete most of the cells. As a result, the proposed algorithm is more than twice as fast as if we only use backtracking.
Implementation
The implementation of the Sudoku Solver described in this article can be found at the following Github link.
Next steps
A possible improvement to this project would be to generalize Sudoku solving. This could be done for those dimensions where the size of the board is n x n, where n is a natural number (in the particular case of this article, n is equal to 9). Under these conditions, the numbers with which the Sudoku would be completed would range from 1 to n. Efficiency improvements could also be considered, trying to reduce the solving time of each of the Sudokus. Finally, given a Sudoku with more than one valid solution, it could be implemented to return all of them.
Conclusion
In this tour, we have explored Sudoku solving through methods such as Basic Filler, Deep Filler and Guess Filler. In addition, we have strategically broken down the process to address both simple situations and more complex cases.
Sudoku has proven to be a fertile field for the application of algorithms and logical strategies. From the Basic Filler, which searches for unique solutions in rows, columns and blocks, to the Guess Filler, which allows us to explore options, backtrack when necessary and move towards the final solution.
The combination of these methods not only demonstrates their effectiveness, but also highlights the importance of choosing specific approaches according to the complexity of the problem. By bounding the complexity of the decision tree using simpler strategies, we have achieved a more efficient and faster algorithm. In fact, the implemented methods are based on strategies that humans normally use to solve Sudoku, showing that in many cases, human intuition is a good starting point.
Ultimately, this work highlights how the intelligent application of algorithms can have a significant impact on solving complex problems. From board games to computer science, the right choice of algorithms not only shortens solving times, but also paves the way for tackling challenges efficiently and effectively.
