The Sudoku Image Solver is a Flask web app that uses image processing (blob, line, and corner detection), a convolution neural net, and candidate elimination algorithms to interpret and solve a sudoku puzzle passed to it as a picture.
The app was deployed on google app engine. Link: http://sudoku-image-solver.appspot.com/ I've since removed it due to monthly server fees. You can access a demo video of the website in the project files.
- Run using Python 3.6 or 3.7
- See "requirements.txt" for a list of packages to install
1. Open a terminal or Anaconda Prompt and navigate to the downloaded project directory
2. Type and enter "pip install -r requirements.txt" to install the required packages
3. Enter "python main.py" to run the application
4. Wait a few seconds then type "http://localhost:5000/" in your web browser and the application will appear.
There were dozens of methods required to process the images and extract the digit grids. An abbreviated summary is given below:
- Cleaned image using an edge detection kernel and OpenCV’s Kernel Adaptive Threshold
- Located the puzzle grid by iterating through the image pixels and using OpenCV’s floodFill function. I judged the puzzle to be the “blob” the highest squared area in the picture
- Straightened the puzzle within the image using OpenCV’s HoughLines on the grid
- Stretched the grid to the edges using OpenCV’s getPerspectiveTransform function. The 4 corners parameters were found using OpenCV’s cornerHarris function while filtering for the outermost.
- Removed the grid lines by setting the locations of the grid mask, found during the floodfill step, to the 10th percentile of the image color values
- Divided the image into 81 cells (9X9) then used OpenCV’s flood fill again to find the digit within each cell
- Created digit images by again iterating through pixels with OpenCV’s flood fill function and setting several thresholds (bounding size, length, width, coordinates, etc…) for separating digits from noise
- Centered the digit images within the cell by finding its bounding box and rolling pixels across the cell until it was in the middle
- Predicted the digit values using a CNN from Kera’s Tensorflow. The training was a combination of the MNIST dataset and 3000+ self-made examples. The MNIST data was useful, even though it was handwritten digits, because it provided a degree of translational learning and therefore better accuracy
The Sudoku puzzles are solved through the process of elimination. Each cell has a set of 9 possible values (ie. candidates). The program loops through each one of the cells and eliminates candidates using a variety of methods extrapolated from Sudoku's basic rules. Names and descriptions of these candidate elimination algorithms are shown below. The solution for each cell is found when there is only 1 remaining candidate. The program continues looping through the puzzle and applying the algorithms until all cells are filled.
- Naked Single: When a cell has only 1 remaining candidate, that digit is the cells solution
- Hidden Single: When a cell contains a candidate number than is not available for any other cell within its row, column, or block, then that number is the cell's solution
- Naked Pair: When two cells in a row column or a block have the same pair of remaining candidates (Ex:[2,4] [2,4]), all other instances of those candidates within the same row, block, or column can be eliminated
- Hidden Pair: When 2 cells with the same row, column, or block each have and are the only cells that have 2 specific candidates (Ex:[1,2,4] [1,2,5]), then all other candidates can be eliminated for those 3 cells
- Pointing Pair: When a candate appears 2 or 3 times within a block and only in a single row or column, all other instances of the candidate within that row or column, and outside the quadrant, can be eliminated
- Naked Triple: When 3 cells in a row, column, or quadrant share the same set of 3 remaining candidates between them (Ex:[1,2] [2,3] [3,2]), then all other instances of those 3 candidates can be eliminated from the row, column, or block