Showing posts with label sudoku. Show all posts
Showing posts with label sudoku. Show all posts

Wednesday, 27 May 2015

Backtracking algorithm is a great tool.

So I wanted to solve the SUDOKU I just recognized from the image I fed in MATLAB and I tried various logic but nothing worked better than "Backtracking". You can find a great explanation of this on YouTube or  http://www.geeksforgeeks.org/backtracking-set-3-n-queen-problem/  .
Basically, a function is made to recur and return values as true or false if the consistency is maintained or not respectively.

Unlike N-Queen problem where you can output simultaneously, you might find need a global variable that stores the ANSWER matrix of SUDOKU if no empty boxes are possible; or else returning values and stepping out of recurring functions might result in losing of the solved matrix.
I could solve a 9x9 SUDOKU in 3 seconds. My program needs optimization.

Will keep posted on program optimization and better image processing techniques because the current one carries several cons.

Friday, 22 May 2015

Glitch in the "Bounding Box" method.

Regarding the last post. The method I posted had a major drawback.
I will explain with the help of an example.

I tried to feed my code a real sudoku problem. And it so happened that my OCR results storing array had a number "95126".

This was because it considered the less spaced numbers as a single number and hence stored in a single cell. This was a havoc for me; but I found an alternative. I will post that soon,
Keep smiling. :)

Found a solution to storing characters recognized from MATLAB in an array in a program to solve Sudoku.

The key were bounding boxes.
I found out the elements recognized having same bounding box row coordinates and hence stored their column coordinates in same row of an array and changed row of array when it didn't meet my condition of same row location.
This way I got an array of elements of my sudoku puzzle sorted row-wise.

Here's the trick for storing it column-wise.
I made a scale of pixels showing distance between a block and first block. You can find out prcatically using impixelinfo how many pixel difference corresponds to number of blocks.
Like in my case 150 pixels corresponded to center to center of two adjacent boxes. Hence I named a variable to store "what-multiple-of-150" is the non-empty character containing pixel.

This way you can sort it column-wise and hence get a complete Sudoku puzzle from page to matrix using basic knowledge of MATLAB.

P.S. This method has major drawbacks. I will post the alternative I found soon. Thank you.  

Wednesday, 20 May 2015

Stuck. Need help.

I am making a sudoku solver using MATLAB. So far I completed cropping my sudoku puzzle from image and even extracting numbers accurately. But the problem is the numbers are extracted in text file of OCR regardless of position of where they are. Need help to store my recognised characters in a matrix to further process for solution.