Tammo 80

I just released the first version of my first iOS app SnapSolve. It is an app that solves Ruzzle or Boggle: it finds all the words in the 4×4 letter grid. There are already many such apps, but the new thing about SnapSolve is the input: you take a picture of the game, and the letters are automatically detected.

Making this game took me a lot of time, since I had to learn XCode, Objective C, C++, OpenCV and had to come up with an actual algorithm to do the letter detection. In the end I resorted to Python + OpenCV to do prototype the algorithm, so three programming languages were involved. Just as I was submitting the app to Apple for review, a blog appeared about just the thing I was making. I’ll try to illustrate the algorithms I developed in the style of the Megafauna blog. Actually, both our algorithms were inspired by SudokuGrab.

My algorithm consists of

1. Scale the image to 360×480
2. Detect if it’s Ruzzle or Boggle
3. Adaptive threshold
4. Find all contours
5. Select contours that have a reasonable size (could be a letter)
6. From the centers of all these contours, select the 16 that are on a 4×4 rectangular grid
7. Recognize the score modifiers (only for Ruzzle)
8. Recognize the letters: for every of the 16 letters:
   1. Draw the letter on a 30×30 image
   2. Overlay it with all (26 x 4 = 104) reference letters, find the letter with the largest overlap
9. Find all the words using a trie
10. Sort the words by score

Here are some pictures that show what’s going on: