Skip to content

kami83/SnapSudoku

 
 

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

70 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

SnapSudoku

Take a picture of a Sudoku and have SnapSudoku solve it for you!


TODO:

  • Improve algorithm to get better Sudoku Grid extraction, make it more robust against blurs .
  • Improve empty cell detection. Only a basic logic is used right now.

Prerequisites:

  • Python 2.7 but not Python 3

    • Download from here
  • OpenCV

    • sudo apt-get install python-opencv (preferred)
    • Install OpenCV from here
  • Numpy (1.11.0)

    • pip install numpy (preferred)
    • You can build it from source here

How to use:

git clone https://github.com/prajwalkr/SnapSudoku.git
cd SnapSudoku
python sudoku.py <path-to-input-image>

Working:

Here's a Sudoku image from a smartphone:

Input Sudoku Image

The current code gives out the following output to the Terminal:

Final result

Algorithm

  1. Basic image preprocessing - Thresholding.
  2. Crop out approx. Sudoku puzzle (Largest contour)
  3. Get the grid square vertices: (a better way of doing this is required!)
    3.1. Get the largest contour of the image.
    3.2. Get the largest bounding rectangle within the contour.
    3.3. Compute the grid corners.
  4. Do a Warp perspective on the sudoku image
  5. We will extract cells from this, by slicing the sudoku grid evenly.
  6. Digit isolation in cell is done through a series of steps:
    6.1. Extract the largest connected component in the image, giving more priority to the center pixels.
    6.2. Removing all major noise in the cell.
  7. Predict Digits using a Neural Network.

The only 3rd party libraries required are OpenCV, Numpy. The Neural Network created was trained with around 250 digits. The constants used in the training phase, the training data-set is in this repository itself.

Here are some illustrations of the different stages:

After Preprocessing:

After Preprocessing

Final processed Sudoku Grid

enter image description here

Here are a few digits after processing the cells:

Digit 3Digit 8

Here's a typical empty cell:

empty cell

Predicted Grid:

Prediction

Solved Grid:

Solved Grid

Contributors

cclauss
lakshmanaram

I'll be very happy to get new ideas to improve the accuracy and make the application better. Feel free to give a pull request! 😄

About

Extract and solve Sudoku from an image

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages

  • Python 100.0%