Sudoku grid and digits detection

Nowadays, Sudoku solvers are literally everywhere. However, they are often tedious to use as one need to enter manually all the digits. Therefore, this project seeks to automate such task by detecting Sudoku grids, along with their digits, within pictures.

The grid detection is performed with Computer Vision techniques using the OpenCV tools, while the digit recognition/classification is implemented as a Convolutional Neural Network based on PyTorch framework.

For the training of the latter, the QMNIST dataset is used. However, it is augmented with blank images as well as printed digits (printed_digits.csv) generated with 445 fonts.

Dependencies

If you plan to run the scripts of this repository, you will need to install several Python packages including torch, torchvision, opencv, scipy, etc. and their dependencies.

To do so safely, one should create a new environement :

virtualenv ~/sudoku -p python3
source ~/sudoku/bin/activate
pip install -r requirements.txt -y

or with the conda package manager

conda env create -f environment.yml
conda activate sudoku

Usage

First, you'll need to train the network, which is automatically performed by the model.py script.

python python/model.py

Then, you can either use the functions of digits.py at your convenience, or use it as-is.

For example, for the empty_0042.jpg image :

python python/digits.py resources/images/empty/empty_0042.jpg

4 0 0 8 0 2 0 0 6
0 6 0 0 1 0 0 9 0
0 3 8 0 0 0 1 7 0
0 0 0 1 2 7 0 0 0
7 0 0 3 0 4 0 0 1
0 0 0 5 8 9 0 0 0
0 7 4 0 0 0 2 1 0
0 2 0 0 3 0 0 6 0
9 0 0 2 0 8 0 0 5

Predictions are not always perfect, there might be digits that are miss-classified.

It should be noted that the whole neural network is loaded each time the script is called, which takes more time than the actual detection. To amortize this cost, prefer calling the script with several input images.

python python/digits.py <image0> <image1> <image2> ...

You can also use the flag -v to display the intermediate processing steps.

Annotated Sudoku grid database

This repository also contains Sudoku grid pictures, each with an associated .dat file reprensenting the digits in the grid.

resources/
└─ images/
   ├─ blurry/
   ├─ empty/
   ├─ filled/
   ├─ generated/
   └─ handwritten/

Each directory contains a different kind of pictures. The images from empty/, blurry/ and filled/, come from the repository wichtounet/sudoku_dataset.

Grids from the handwritten/ folder are not solvable grids. However, they can be used for Sudoku grid/digits detection.

Random Sudoku grid generator

The script generator.py generates random sudoku grids in jpg format.

Grids are generated by solver.py and have only one solution.

The graphics are produced with the pycairo Python library.

Install pycairo

Because it depends on the cairo C library, the installation of pycairo isn't the same for each platform.

• Ubuntu/Debian

  1. Install pkg-config and cairo.

     sudo apt install libcairo2-dev pkg-config python3-dev

  2. Install pycairo using pip.

     pip install pycairo

• macOS

  1. Install pkg-config and cairo.

     brew install cairo pkg-config

  2. Fix path according to stackoverflow.com.

     export LDFLAGS="-L/usr/local/opt/libffi/lib"
     export PKG_CONFIG_PATH="/usr/local/opt/libffi/lib/pkgconfig"

  3. Install pycairo using pip.

     pip install pycairo

• Windows

  1. Install it using conda.

     conda install pycairo