AR Sudoku Solver
The AR Sudoku Solver is a tech demo that uses a camera and some image processing algorithms to find sudoku grids, solve them and project the results back into the picture. I did some back-of-the-envelope calculations in 2007 that showed that my desktop at the time should be able to do that as fast as the web-cam delivers the pictures. In the following I have implemented it in Active Oberon and got the expected frame-rate without using special SIMD instructions.
Recently I have ported the code to C and added an Android wrapper. The current version reaches about 5fps on a Nexus One or Nexus S.
The program expects the grid to be freestanding, flat and not manually filled. Best results are achieved in good lightning conditions. The solver does not try to solve grids with less than 20 symbols (not restricted to numbers). All symbols must appear at least once.
Video of the Active Oberon Version running on Windows
Now as an Android application in the Android Market.
Tested DevicesSo far I got the feedback that the program works on the following devices:
- Samsung Galaxy S
- HTC Desire HD
- HTC Desire
- Samsung Galaxy S2
- Samsung Nexus S (2.3)
- HTC Wildfire
- Samsung Galaxy Tab
- Samsung Galaxy Ace
- HTC Nexus One
- LG Optimus One
- The camera picture is red
This is normal as long as the solver did not detect a valid sudoku grid.
- Make sure the sudoku grid is completely in the view.
- Try tapping the screen with one finger to auto-focus (if supported by the device).
- Make sure the sudoku grid is flat.
- Make sure the lightning conditions are good.
- Can it be faster ?
Yes. There are at least the following weak points:
- The program does not make use of SIMD instructions
- The writing of the solution is done very stupidly (just wanted to finally see the results and then it was "good enough for now(tm)"
- The program only asks for the next frame once it processed the current frame. Depending on the camera driver, this causes up to 50ms delay
- Potentially HW acceleration could be used for the 3d acceleration