Solve Sudoku 9x9 with Computer Vision and a Constraint Satisfaction Algorithm in Python
This is a program in Python 2.7 to solve a Sudoku 9×9 of the Android application “Sudoku” of genina.com.
It’s a program in python 2.7 to solve a sudoku of the Android application “Sudoku” of genina.com. A screenshot of the game is taken (a 720×1280 image is obtained), then the number found in each of the 81 squares is obtained using KNN and KMeans algorithms, once each element is determined, the sudoku is solved using a constraint satisfaction algorithm with backtracking.
How this work?
- Preprocessing
Each box is extracted from the sudoku individually and saved sequentially as photo # .png (where # goes from 0 to 80). 80×75 images are obtained.
Go to my github: https://github.com/cabustillo13/Resolvedor-de-Sudoku to access the code and images.
I create a library only for preprocessing and image transformation called “Funciones.py”. That library contain: Image rotate function, a function to crop top stripe image, a function to Trim box / square, a function to save an image, and a function to crop image edges.
2. Image transformation
Trim the edges of each box, in case there are any black borders that you can infer in our analysis. 56×51 images are obtained.
3. Test KNN and K Means algorithm performance to see which one best suits this problem of number classification using computer vision
A KNN and KMeans algorithm is proposed and all the images in the Test folders are evaluated, and thus determine their performance of the percentage of predictions. In the end KNN was chosen because it has higher performance.
Description of some of our functions in this code block:
def extraccion: This function performs the individual processing of each box analyzes, filtering, segmentation and extraction of characteristics.
class Element: A class was created for all the indicators in the image.
def analisis_de_datos(): Training data base.
def analisis_de_prueba():Test Data Base
def knn(): KNN algorithm.
def entrenamiento_kmeans(): KMeans algorithm.
def kmeans(): Test Data Base.
KNN Performance - Curse of dimensionality
KMeans Performance
Conclusion: I chose KNN because it has a better performance.
4. KNN Classification
Analyze what number is in the box. In this case, Canny’s algorithm is used to determine if there is any number or if it is an empty cell. Then through the KNN algorithm it is determined what number is in the box. For the extraction of characteristics, the moments of Hu: 1 and 2 were used, a Gaussian filter for the filtration and unsupervised thresholding.
In this partof the code, we choose which image we are going to analyze.
Vector.txt
Vector.txt contains all the elements extracted from the screenshot (where the boxes were scrolled from left to right, from top to bottom). According to Rendimiento.py, the KNN algorithm presented a 97% performance with respect to all the images analyzed in the Test. In case of any error in the recognition of the numbers there is the option to manually change a prediction of the box in the vector.txt.
5. Now solve the sudoku!
A restriction satisfaction algorithm with backtracking is presented to solve the sudoku I take as reference the github: jorditorresBCN /Sudoku to make this.
Results
Go to my github: https://github.com/cabustillo13/Resolvedor-de-Sudoku to access the code and images.
Thanks for reading! I hope you enjoy playing sudoku!