The solution for a Sudoku puzzle includes all the digits from 1 to 9 in each column and row of a 9 x 9 grid and within each 3 x 3 subgrid. As a logic puzzle, Sudoku is well-suited to automated solver algorithms that, given all the starting numbers for the puzzle, can easily determine the rest.
Sudoku puzzle solver programs typically require the user to manually input the starting numbers. Now, using a method developed by Neeramitra Reddy, an undergraduate student in the Department of Computer Science and Engineering at the National Institute of Technology Karnataka (Mangalore City, Karnatake State, India; nitk.ac.in), a stymied Sudoku player can just take a picture of the puzzle and let image processing techniques and neural networks do the rest.
Reddy has made his GUI Sudoku Solver solution freely available on Github (bit.ly/VSDSUD). The software includes a user interface for manual review in case a number is misrecognized by the image processing software. However, according to Reddy, the software only has an estimated 3% misrecognition rate on test sets.
Once a picture is taken of the puzzle, the software blurs the image using a Gaussian function to reduce noise. Adaptive gaussian thresholding sets all pixels in the image to either black or white, replacing a degree of lost detail. The program then inverts the image such that the digits and lines of the puzzle appear in white. Image dilation followed by flood filling defines the board lines. Next, a Hough Line Transform feature extraction technique detects the board’s outer edges and the software crops them out.
The image is inverted again, allowing the software to better detect the 81 cells of the Sudoku board. The solver analyzes each cell and fills with the color black any white pixels other than those that comprise the number. Now the software has a clear image of both the game board and all the numbers within the cells, which can then be translated into computer language and fed to a neural network that provides the solution.
The software can run as either a convolutional neural network or a k-nearest neighbors. The models are trained with the MNIST handwritten digits dataset (bit.ly/VSD-MNS).
