Google Goggles Does Sudoku
Another installment from the amazing file: an iPhone app that looks at and then solves Sudoku.
http://www.cnet.com/how-to/how-to-beat-sudoku-puzzles-using-google-goggles/
Image recognition software aside, the interesting mathematical idea here is how one would create a computer program that can solve an arbitrary Sudoku puzzle. It doesn’t seem like a particularly challenging task, but finding an efficient method may be a challenging problem. After all, I imagine some strategies are better than others.
Experienced Sudoku solvers probably have a general algorithm they follow, but I imagine that intuition (guessing?) plays a role at some point. Can you program that in somehow?
2 Comments
Alan · January 17, 2011 at 4:23 pm
I saw this quite a while ago and downloaded Google Goggles. There is supposed to be a compatible version fore the iPod Touch, but sadly, it’s for the iPhone only. I’d love to test it out. I wonder how the program approaches solving the Soduku puzzle. Just i focus on one 3×3 box and fetch data from other Soduku puzzles via the web to attempt to brute-force a solution or does it have some sort of general formula to figuring out the answers and then guess&checking in the end? Since it’s a computer program, it can carry out tons of queries in mere seconds, so I wouldn’t be surprised if it was a guess&check type of approach.
Nikita Zolotykh · January 20, 2011 at 7:55 pm
It’s a phone application, and phones tend to be less powerful than computers, so I’m not really sure if it would brute force a solution like that. However, the program probably sends the “scanned” sudoku to a computer server via internet and the server solves it (most likely by brute forcing), and then sends it back on the phone (that’s how the WolframAlpha app works).
And, would the program be able to solve sudokus like this? http://www.sudoku-tips.com/blog/uploaded_images/Crazy_Puzzle1-715950.JPG