After a little pacing, I came up with this solution for part 1 of the sudoku solver.
(can’t remember where I got the image – national championship, philadelphia). First, we convert the image into black/white.
Then we remove all the black dots which don’t have another black dot to the top/right/bottom/left. That cleans it up just a little, but every little helps.
Now, we extract every grouping of black pixels, using the flood fill algorithm. Discard any with less than, say, 300 black pixels in total (too small to be the frame we’re looking for). Here are clips of the remaining images:
One cool thing about a square is that in a cropped image of the square (cropped close to the edge of it), the ratio of width/height of the image is almost exactly 1:1. This is true even if you rotate the image (around the Z axis). The ratio can change if the square is tilted back or turned in some way, but we will assume that someone photoing a sudoku grid will be facing it square.
So, from those images, we choose the one which is closest in ratio to 1:1. to do this, just divide width by height. if the number is less than 1, divide height by width. If the number is greater than, say, 1.1, discard the image. In this case, there’s just one image remaining:
In the case I’ve presented, there was just one image remaining. I had one more trick up my sleeve in case there was more than one, and that was to choose the image which had the lowest ratio of black to white pixels.
Anyway – now we have the grid, so I’ll get to the number recognition next.
The plan for this one is that, if you’re doing a sudoku puzzle in the pub or on the train, and you get stuck, you just take a snapshot of the puzzle with your camera-phone, send the photo to a certain mobile number, and a few seconds later the solution is sent back as an SMS message. The solution costs you something small – 50 cents, maybe.
How it works is that the photo gets sent via SMS to a PHP server, which manipulates the photo in a small number of steps:
Find the corners of the puzzle.
Extract the numbers and identify them.
Also identify whether the numbers were printed or hand-written.
Solve the puzzle with the printed numbers.
In the above, the only difficult step is actually the first one. I’m still trying to figure that one out. I think it will involve a bit of maths, which should be interesting.
For identifying the numbers, you just need a small neural net. This is much easier than full-blown OCR, because in OCR, you have the additional problem of trying to identify what is a letter, what’s a word, and what’s empty space. In the Sudoku puzzle, though, there is a well-defined grid, and a certainty that each square contains just one number to be identified.
Identifying whether a number was handwritten or printed should also be easy – the colour of the figure will give it away. The colour of the puzzle frame will match the printed numbers, but will be slightly off from the hand-written figures. Of course, it won’t be as simple as that in practice, but that’s what I’ll be testing first.