## Friday, June 1, 2012

### 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.