Solving Sudoku using a naked twin strategy.
Recently, I started studying Artificial Intelligence as I wanted to improve my knowledge in the domain of Machine learning. While I was studying Convolution Neural Network models and Genetic Algorithms, I thought of solving the Sudoku puzzle using the Genetic Algorithm.
Without digging deep about it on the internet, I decided to find a solution on my own. I had this impression that with the Genetic Algorithm, sudoku can be solved as the solution will converge towards minima if a proper fitness function is selected. I knew that if I read any solution on the internet, then I will not be able to think of any different solutions.
My initial understanding was to solve the problem with the below steps.
- Generate population for the empty positions on sudoku by identifying the possible values. If there’s no value possible pick a random value
For example, for the position (0,2) in the below matrix, the list of possible values is [1,2,4], so pick any value from the list, say 1 , and assign to the position.
Continue the same way until we assign all the empty fields. During the assignment, it may happen that list of possible values will be empty for some positions as we might place wrong values at some positions. For those cases, we will randomly assign a value.
2. A fitness function will assign a score to each of the filled positions based on if the row, column, and 3x3 matrix are correct or not. For example (2,0) is incorrect as the column value conflicts at (2,6). so the score will be 1.
The lower the score, the better it is.
3. Then in the selection and mutation step, we convert the score to a probability and generate another sample based on the probability distribution.
I had the feeling that it should work and slowly the population should converge toward a solution where the score will reduce to zero.
But…
The approach was failing to solve the puzzle all the time. sometimes is was failing for the same given puzzle.
Reason for failure
I found that after a point the population converges towards the wrong solution. It happens because the sudoku solution has multiple false minimum points. what that means is, sometimes, when you fill cells and add a value, It may be possible that most of the rows/cols/3x3 matrix is satisfied but only one position has conflict. In this case, the population will converge to the point because the score on each individual cell will be higher.
If you have solved sudoku puzzles in newspapers, you might have faced a similar problem even when we try to solve them manually. It feels like the value we added is correct, but in the end, we find one cell where conflict occurs.
Code: https://github.com/anandpathak/GA-sudoku/blob/master/ga_solve_sudoku.py
So, what’s next? how do we solve it?
Backtracking and graph coloring
One naive approach to solve a sudoku is to use graph coloring and backtracking techniques. The problem with this approach would be the time complexity will be very high as it needs to go through the complete search space.
Think it, in the way that, we are on a land full of mountains where we can not see the peak of the mountains and we are asked to find the mountain with the highest peak. In this scenario, one simple approach would be to climb up to mountains and then exclude those mountains which are smaller and process only those whose peak is still unclear. This is a typical Backtracking technique and it takes a lot of effort, and that’s why simple backtracking for solving Sudoku will be a costly operation.
Another option would be to identify some parameter which can judge the height of the mountain. For example, we can have an assumption that the mountain with a larger base generally has a higher peak and we can climb mountains with the larger base first if this constraint holds true, then the highest peak mountain can be found in the minimum iteration. In this approach, we are just adding constraints to the problem statement and it may reduce the search space.
Naked Twin strategy
I was not aware of the constraint which can be applied to Sudoku so I had to take help from the internet and there I found a strategy Naked Twin which reduces the search space for the problem.
Naked twin is a very simple concept, it says that if two connected position has the same set of two values, then all the other linked missing values should not have those value, so we can eliminate it from the list of possible values for those linked position. You can get a better understanding here
To understand the impact of the naked twin strategy I wrote some code to generate the sudoku using graph coloring and then convert it into a puzzle by removing values, and passed the problem to two algorithms
- Backtracking with graph coloring strategy.
- Backtracking with constrains propagation where naked twin and single fields removal was added as constraints.
To understand the impact of both these solution I ran the problem for multiple iterations and generated stats which explain the impact of naked twin on the problem.
In the graph, you can see that Y-axis shows the time duration, and X-axis shows the number of missing fields in the problem Matrix.
The first graph only shows the case where the missing value is in the range of 20–45. It can be seen that there is a huge difference between simple backtracking and Backtracking with a naked twin strategy. This is because the problem statement in this range has a lot of conditions where twin pairs exist and that reduces the search space marginally.
On the other hand, if you look at the last two bars of the 2nd Graph, then there is no difference between Backtracking and Backtracking with Constraint propagation. This is because when the number of missing value increases, chances of getting naked twin pair reduces, so the constraints do not reduce the sample space.
In case when the number of missing values is very less then also there is no much difference between the algorithm performance. The reason is that the sample size is very small and both algorithms run very quickly due to low search space.
you can find the code here https://github.com/anandpathak/GA-sudoku.
