AI Sudoku Solver

Sudoku is a puzzle in which players insert the numbers one to nine into a grid consisting of nine squares subdivided into a further nine smaller squares in such a way that every number appears once in each horizontal line, vertical line, and square.

Table of Content

1. AI Sudoku Solver
2. Approach
3. Conclusion

AI Sudoku Solver

Using OpenCV, Deep Learning, and Backtracking Algorithm, We can solve the sudoku puzzle. First, build the Character Recognition model that can extract digits from a Sudoku grid image and then work on a backtracking approach to solve it. Deep Learning-based AI_Sudoku_Solver architecture uses OpenCV (opencv==4.2.0) and Python (python==3.7). The model Convolution Neural Network(CNN) uses Keras (keras==2.3.1) on Tensorflow for Digit Recognition.

Approach

Here, we can divide the process into 3 parts :

1. Looking for a sudoku puzzle in the image.
2. Extracting numbers from sudoku.
3. Solving the Sudoku using backtracking.

Looking for a sudoku puzzle in the image: In this part, we’ll be focusing on how to extract the sudoku grid i.e. our Region of Interest (ROI) from the input image.

1. Converting the input image to a binary image: This step involves converting the input image to a greyscale image, applying a gaussian blur to the grey-scale image, followed by thresholding, bitwise_not, and dilating the image.
2. Detecting the largest polygon in the image: This step involves finding the contours and selecting the largest contour. Now from the largest contour, selecting the extreme most points and would be the 4 corners. The function cv2.findContours returns all the contours it finds in the image. After sorting the returned contours from the image by area, the largest contour can easily be selected.
3. Cropping and Warping the largest contour:
   The approach is simple since we have the coordinates of the 4 corners, we can use warping, which gives a better perspective of the image.

Extracting numbers from sudoku: Extracting the smaller grids, Since we already know that a sudoku grid has 81 similar dimensional cells (9 rows and 9 columns). We can simply iterate over the row length and column length of the image, and pass each cell to CNN Model for digit Recognition. Please go through this article for more details of Digit Recognition using CNN.

After extracting digit, our Sudoku grid will look like…

Solving the Sudoku using backtracking: Now that we have converted the image into an array, we just need to make a function that can fill up the blank spaces effectively given the rules of sudoku.

Let’s understand how backtracking works through an example using a 3x3 sudoku. Suppose we’ve to solve the grid given the constraints-

Each column has unique numbers from 1 to ’n’ or empty spaces.

Each column has unique numbers from 1 to ’n’ or empty spaces.

1. We need to fill 5 spaces, let’s start by iterating over the blank spaces from left to right and top to bottom.

2. Let’s put 1 in the first encountered space and check if all the constraints are satisfied.
Seems 1 is good here as it is unique in its row and column.

3. Moving on to the next grid, we again start by keeping 1 but as we can see that it is not unique in the column so we check for 2 and 2 satisfies all the constraints

4. For the 3rd empty grid, we can see none of the 3 numbers 1,2,3 satisfy the constraints.

5. To fix this, we take a step back and increment the number in the last grid we filled and make sure that the constraints are satisfied. Now we proceed with the next grig again and we can see that 2 fits in it.

6. Similarly, we fill the remaining grids and reach the optimal solution.

Now that we’ve understood how backtracking works, let’s make a function using the constraints used while solving a 9x9 sudoku and test it on the array we obtained from the previous step.

Conclusion

In this article, we learned

1. The Concept of Contours and Warping.
2. The Deep Learning Model for Digit Recognition.
3. Backtracking Algorithm.

References

1. Sudoku Solver
2. Digit Recognition
3. Backtracking Algorithm
4. Medium Article

The code is available at https://github.com/Devashi-Choudhary/AI_Sudoku_Solver. For any questions or doubts, feel free to contact me directly at github.com/Devashi-Choudhary.

Find me on LinkedIn: https://www.linkedin.com/in/devashi-choudhary-84677b109/

Thanks!