Sudoku Solver using Python OpenCV and TensorFlow

By ALBINUS B

The Python program allows the user to capture a sudoku puzzle and then returns its solution. OpenCV and TensorFlow are used for image processing and predicting the digits in the puzzle.

This Python source code is simple. let's start with the rules.

Rules of Sudoku:

The classic Sudoku game involves a grid of 81 squares. The grid is divided into nine blocks, each one containing nine squares. The rules of the game are simple: each of the nine blocks has to contain all the numbers 1-9 within its squares. Each number can only appear once in a row, column, or box.

NOTE: I use a 9x9 sudoku puzzle

Phase 1: Capture the image and pre-process it

First, webcam = cv2.VideoCapture(0) is initialized and the webcam.read() is called within a while loop to give an output video. Click ‘s’ to save or click ‘q’ to exit. For sake of simplicity, the image is saved when ‘s’ is pressed.  

Second, the saved image is read. we apply Gaussian blur with a kernel size (height, width) of 9 to the image. Note that kernel sizes must be positive and odd and the kernel must be square. Then we use an adaptive threshold using 11 nearest neighbor pixels.

Third, we need to separate an image into some regions (or their contours), the process is called segmentation. 

 

Phase 2: we train the MNIST dataset model

I trained a convolution neural network of a sequential model. Nine layers are added to the model with softmax activation as the last layer. The model is trained for 10 epochs with 99.5% accuracy(the model is saved as ‘OH-HO2.h5’).

 

Phase 3: find the corners of the puzzle

The largest contours are found from the preprocessed image. This gives the biggest polygon which is the whole sudoku board alone. There are several ways we can achieve this. I've defined a module booba which contains the ‘warpimage’ function. the height and width are processed here and then the ‘warpPerspective’ function from OpenCV is used to warp the original image

After warping the image we again process it.

Phase 4: splitting the warped images into individual cells

It’s basically measuring the height and width of the warped image and dividing them by 9 to get the height and width of the individual cell (as all the cells have the same size in the puzzle). contours are used to find the non-empty cells and then it is passed to 'predictdigit' function.

 

Phase5: Predicting and Solving using backtracking

We pass the split images to predict function after some processing and store the predictions in a numpy array. An option is provided to correct the wrong predictions. The array is then passed to the ‘solve’ function in 'backt' module which uses a backtracking algorithm to solve the puzzle and display the solution. (NOTE: If any prediction is not correct then the solution won't be found or the wrong solution might be given).