Solve Sudoku from an Image
Don't waste your time, Here’s what you are looking for, Git-hub link
What is the best way to learn something new?
Think of a project and dive right into it. I’ll figure out stuff and learn on the run.
That is exactly what I had in mind. I sat in front of my lap with full optimism and enthusiasm. Okay, What do I have to do?… Solve sudoku from an image.
Quickly googled what is required for it. Well, I’m not that noob that I didn't know coding. I made a list of tasks to do and began.
Steps Involved
- Extracting Sudoku from the image
- Converting the sudoku to numbers
- Completing the sudoku using BackTracking Algorithm
A.Extracting sudoku from the image
A.1. Pre-processing of the image
Gaussian blur is done to remove the noise in the image. Kernel size of (9,9).
Adaptive Threshold is done so that the algorithm decides a threshold based on the pixel values of the neighboring pixels.The threshold value is a Gaussian-weighted sum of the neighborhood values minus the constant C.
Read more about adaptive threshold
Inversion of colors is performed using Bit-wise NOT operation. Dilation of lines is done to increase the thickness of the lines. This concludes the pre-processing of the image.
A.2 Finding corners of the largest rectangle
In order to separate the Sudoku box apart from the extra junk that is of no use to us, we need to find the corners of the largest rectangle. In order to do so, we use the findContours() function to determine all the contours of the image and find the largest area among them.
Once the largest area of contours are determined, the combination of the X and Y coordinates from the contour will give the four corners of the rectangle.
Bottom-right point has the largest (x + y) value. Top-left has the smallest (x + y) value. The bottom-left point has the smallest (x — y) value. The top-right point has the largest (x — y) value.
A.3 Cropping the image
Crop the image to the square having the sudoku. We describe the square with the distance calculated from the corner points. Then warp the image to that distance after comparing values. Finally, crop the image using transformation.
A.4. Split the image into 81 cells and infer it
B.Extracting numbers from the squares
In order to extract the digits from the squares, we need to split the sudoku into 81 individual pieces.
We must then center the digit, Run a CNN model of trained datasets to predict the exact number from the picture.
I first built and trained a Convolutional Neural Network (CNN) on the MNIST handwritten digits data-set. The MNIST data-set is a data-set of 70,000 28X28 pixels images of handwritten digits.In my case there is some error in prediction, you can use a better model for better accuracy.
Nevertheless, once this is done, lets solve the Sudoku puzzle
Sudoku can be solved by using a simple backtracking algorithm. All you need to do is this:
- Find empty cells
- Fill numbers to check if it satisfies all the conditions of a Sudoku puzzle
- Go back and change the number if you get caught violating a condition
GUI and Flow
The user interface was built on tkinter, the flow of the program is as follows
And there we have it….
The git-hub link has all the necessary files, code and model for you to understand. Feel free to pull or clone the repository to make it better. Do make changes and Enjoy learning in the process.
