Sudoku Solver

Hello World of Computer Vision and Machine Learning

Table of Contents

• About the Project
  • Tech Stack
  • File Structure
• Getting Started
  • Prerequisites
  • Installation
• Usage
• Results
• To Do
• Troubleshooting
• Contributors
• Resources
• License

About The Project

Solve sudoku puzzle using computer vision and machine learning. Currently(v1.0) solves sudoku from image and overlays missing digits on it

---

Steps followed in this process:

1. Preprocess image (resize, grayscale, blur, threshold, dilation/opening)

Original	Resized	GrayScale	Gaussian Blur	Adaptive Threshold	Negate	Dilation

2. Draw external contours.

External Contours

Current method assumes that the sudoku has largest contour in given image

3. Infer corners of largest contour(sudoku puzzle) and Perspective transformation based on corners

Corners	Transform

4. Infer grid from transformed image.

Grid

Current method just divides the transformed image into number of cells in sudoku puzzle i.e 81

5. Extract digits from cell by finding largest connected pixel structure in mid part of cell. Scale and centre each digit, so that it becomes apt for prediction using neural network

Extracted Digits

6. Classify Digits using trained model
7. Solve the grid using backtracking algorithm
8. Draw the numbers on black background, inverse transform it and add it to original image

Missing Digits	Solution

Tech Stack

• OpenCV
• Tensorflow-Keras

File Structure

.
├── run.py                  # Driver code
├── utils                   # helper classes
│   ├── img_processing.py   # helper functions for image processing
│   ├── classify_digit.py   # helper functions for digit classification
│   └── solve_sudoku.py     # helper functions to solve partially filled sudoku
├── test_imgs               # images for testing
├── assets                  # for readme
├── digit_classifier        # codes to train digit classifier
├── LICENSE
└── README.md 

Getting Started

Prerequisites

Tested on -

• Tensorflow v2.2.0
• OpenCV v4.1.0
• numpy v1.18.5
• scipy v1.4.1
• tabulate v0.8.7

Installation

1. Clone the repo

git clone https://github.com/saharshleo/sudokuSolver.git

2. Download the pretrained model from releases v1.0
3. Extract the model inside sudokuSolver/models/

Usage

cd /path/to/sudokuSolver

python run.py

For viewing the journey of image

python run.py --show True

Results

To Do

• v1.0 Solve using Image processing and Machine learning
• v1.1 Training on own data since model trained on mnist dataset did not gave acceptable results
• v1.2 Solving on video stream
• v1.3 Robust method for infering grid
• v1.4 Different approach for extracting digits robust to lighting variations
• v1.5 Able to recognize rotated sudoku's
• v2.0 GUI game

Troubleshooting

• Changing parameters like --process, --resize, --margin can prove to be effective for some images and models

Dilation for test_imgs/sudoku5.jpg

Corners Dilation	Infered Grid

Opening for test_imgs/sudoku5.jpg

Corners Opening	Infered Grid

Contributors

• Saharsh Jain

Resources

• Nesh Patel's Sudoku Solver
• Backtracking for solving
• Floodfill
• Image Processing
• Corners from points
• Conulutional network for digit classification

License

Describe your License for your project.