visual sudoku solver « Kae Verens

visual sudoku solver

by kae verens on Feb.02, 2009, under javascript, neural networks, php, programming

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.

Actually solving the puzzle is simple – I’ve already written a javascript sudoku solver, so it’s just a matter of porting it to PHP.

5 Comments for this entry

Mr Sudoku
February 18th, 2009 on 6:16 pm
Sounds very interesting how are you going to solve the technology to read the image and translate the pixels into numbers?
For a soduko solver engine check out this!

http://vbaexcel.eu/vba-macro-code/sudoku-solver
Kae Verens
February 18th, 2009 on 7:56 pm
I was hoping to write an OCR solution myself, but my neural net training scripts were not working out. I think I may need to use something like Tesseract.

Interesting – I can’t get your script to run, myself (in Linux, using Open Office), but at a glance, it looks similar to how my JavaScript solver works.
MJ
February 27th, 2009 on 5:15 pm
An interesting project, but as you can see from this video it has already been done.

http://www.youtube.com/watch?v=oImMJ6p6mKE
Kae Verens
February 27th, 2009 on 5:21 pm
brilliant!

well, no reason for me not to do it as well – at the very least, it’s a good programming exercise. (I am still working on this even now)
Kae Verens
February 28th, 2009 on 11:39 am
I’ve been in contact with Chris, the creator of the iphone app demonstrated in the YouTube video. he gave me some very interesting pointers. The most important hint was to use the Hough transform to identify straight lines. I’ll have a new post up soon with source-code demonstrating the whole thing.