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
- Scale the image to 360×480
- Detect if it’s Ruzzle or Boggle
- Adaptive threshold
- Find all contours
- Select contours that have a reasonable size (could be a letter)
- From the centers of all these contours, select the 16 that are on a 4×4 rectangular grid
- Recognize the score modifiers (only for Ruzzle)
- Recognize the letters: for every of the 16 letters:
- Draw the letter on a 30×30 image
- Overlay it with all (26 x 4 = 104) reference letters, find the letter with the largest overlap
- Find all the words using a trie
- Sort the words by score
Here are some pictures that show what’s going on: