Sudoku Solver - Part 1

Hi,

Now I would like to post a series of tutorials on "Sudoku Solver" .

Actually I started this a few months ago, but got stuck at final part, more specifically, the OCR part. But after a little hacks, I could find a simple method for OCR using kNN. Hope you have read that article  !!!

In this post, I will tell you what exactly I did to develop a "Sudoku Solver".

What exactly it does?

This project on successful completion, accept an image of Sudoku as input, and returns a solved Sudoku back.

See a demonstration below:

Output of sudoku solver

Input Image.

How to accomplish this :

It can be done implementing the methods given in image below :

We will deal with each of one of the steps above:

1. Reading the Image : It is our normal image reading in OpenCV
2. Image Pre-processing : It includes noise removal, brightness/contrast adjustment, thresholding etc. 
3. Find Sudoku Square & Corners : Here we find outer border of Sudoku square and its corners.
4. Image Transformation : Here we reshape irregular Sudoku in input image to a perfect square.
5. Recognize the digit (OCR) : Recognizes the digits in input image and place them in correct position
6. Solve the Sudoku : Here, real solving of Sudoku take place. 
7. Project back the Result : We project the solved Sudoku to image as shown in demo.

In some steps, we take some practical assumptions. One, I would like to tell you now :

The biggest square in the image should be Sudoku Square. In short, image should be taken close to Sudoku, as you can see in the input image of demo. ( Reason, I will tell in upcoming posts).

That is all the theory about this. From next post onwards, we get into practicals on how to implement this.

Waiting for your feedback,

ARK.

Inspired by
1 - Google Goggles Android Application
2 - C++ implementation of Sudoku Solver at Aishack.in
And more...