prajwalkr/snapsudoku

Extract and solve Sudoku from an image

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:

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

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:

Final processed Sudoku Grid

Here are a few digits after processing the cells:

Here's a typical empty cell:

Predicted 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! 😄

snapsudoku's Issues

Add code to solve the Sudoku puzzle

Peter Norvig of Google has a really interesting Sudoku solver in Python that is a wonderful read. The average time to solve a random Sudoku puzzle is 0.01 seconds.

Request for contribution

I found interesting your idea and I'd like to contribute to this. Is there anything that needs improvement?

Run SnapSudoku on a smart phone

It would be cool to get SnapSudoku running on the iPhone so that you could use the camera to do the snap and immediately solve the puzzle right on the phone. It would drive Sudoku players crazy if you could walk up with your smart phone, snap a picture of their puzzle, and show them the solution. Pythonista is a Python 2.7 IDE for iOS and it currently has Python 3.5 support in beta testing. Pythonista does support NumPy and Pillow (PIL) but does not yet support OpenCV or SciPy.

Images not showing up in README.md

TypeError: a bytes-like object is required, not 'str'

python sudoku.py /test/test1.jpg
Traceback (most recent call last):
File "sudoku.py", line 42, in
snap_sudoku(image_path=sys.argv[1])
File "sudoku.py", line 32, in snap_sudoku
grid = ''.join(cell for cell in get_cells(image_path))
File "sudoku.py", line 32, in
grid = ''.join(cell for cell in get_cells(image_path))
File "sudoku.py", line 22, in get_cells
net = create_net(rel_path='/networks/net')
File "sudoku.py", line 17, in create_net
sizes, biases, wts = pickle.load(in_file)
TypeError: a bytes-like object is required, not 'str'

Train own Dataset

Hi together,

I need to solve sudokus with a streched grid.
I was not able to figure out how I can use the training function.
Could be help me how to train my own model if I replace the jpg's and dat files with the "train" folder?

Thank you for you help :)

Image type

What type of images can this process ? JPEG, PNG, BMP ?

I am thinking of making a web service with this, so would be helpful to know what type of data to transfer :)

ValueError : Too many values to unpack

This code breaks when I'm running it with OpenCV 3.1.0. Works fine with 2.4.9

Traceback (most recent call last):
  File "sudoku.py", line 41, in <module>
    Sudoku(sys.argv[1])
  File "sudoku.py", line 14, in __init__
    cells = Extractor(image_path).cells
  File "W:\SnapSudoku\scripts\sudokuExtractor.py", line 20, in __init__
    sudoku = self.cropSudoku()
  File "W:\SnapSudoku\scripts\sudokuExtractor.py", line 43, in cropSudoku
    contour = self.helpers.largestContour(self.image.copy())
  File "W:\SnapSudoku\scripts\helpers.py", line 41, in largestContour
    image, cv2.RETR_TREE, cv2.CHAIN_APPROX_SIMPLE)
ValueError: too many values to unpack

Fails to replicate result with the image from the README

Hi,

Thanks for providing this!
I might be doing something wrong here though, because after cloning your repo and installing the right packages, I tried to run it with the image provided in the README. However, I did not get the same output, but instead:

Image loaded.
Preprocessing... done.
Cropping out Sudoku... done.
Straightening image... done.
Extracting cells... done.
No solution found.  Please rescan the puzzle.

Do you know what might be the issue? What might I be doing wrong?

Too many values to unpack?

> sudo python2 sudoku.py /home/jokerowaty/SnapSudoku/test/test1.jpg
> Image loaded.
> Preprocessing... done.
> Cropping out Sudoku... done.
> Straightening image...
> Traceback (most recent call last):
>   File "sudoku.py", line 42, in <module>
>     snap_sudoku(image_path=sys.argv[1])
>   File "sudoku.py", line 32, in snap_sudoku
>     grid = ''.join(cell for cell in get_cells(image_path))
>   File "sudoku.py", line 32, in <genexpr>
>     grid = ''.join(cell for cell in get_cells(image_path))
>   File "sudoku.py", line 23, in get_cells
>     for row in Extractor(os.path.abspath(image_path)).cells:
>   File "/home/jokerowaty/SnapSudoku/scripts/sudokuExtractor.py", line 22, in __init__
>     sudoku = self.straighten(sudoku)
>   File "/home/jokerowaty/SnapSudoku/scripts/sudokuExtractor.py", line 50, in straighten
>     largest = self.helpers.largest4SideContour(sudoku.copy())
>   File "/home/jokerowaty/SnapSudoku/scripts/helpers.py", line 53, in largest4SideContour
>     image, cv2.RETR_TREE, cv2.CHAIN_APPROX_SIMPLE)
> ValueError: too many values to unpack

Any ideas? opencv2 installed, numpy installed. Python2.7.14+

We should use coala to improve the code quality and bunch of other stuff

coala analyser

cc @prajwalkr