I became quietly obsessed with an iOS game called WordBrain over the holidays, and thought it’d be interesting to write some code to solve it’s puzzles (you can find the result here).
The game itself is similar to a typical word search puzzle where, given a grid of letters, you have to find the words in the grid.
It differs in that words don’t have to be found in straight lines, so individual letters can be joined across diagonals, and as each word is found, it is removed from the grid and the remaining letters fall down. This means that for harder puzzles it isn’t possible to connect the letters in the last word unless you have found the preceding word(s).
Before starting, you know how long each word is and the order in which words must be found (as the 5 word puzzle below illustrates).
My solution started out as a simple word finder — finding all words of a certain length — but evolved into a more complete puzzle solver.
First, given a grid and a set of word lengths, the solver comprehensively scans the the grid for words matching against the first word’s length. It then recursively scans for the subsequent words, based on the updated grid (which is created by removing the preceding word(s)). This creates a set of potential solutions to the puzzle.
To speed up search, I created a trie dictionary to allow the solver to terminate when a non-english prefix is found.
Then, to narrow down the set of possible solutions, I used a corpus of English word frequencies to rank them by the most commonly used set of words. This tends to match the expected solution, because WordBrain uses fairly common words.
Finally, I created a Swing UI to make it easier to enter problems and view solutions.
The trie solution is significantly faster than the alternative, an in-memory set of words that didn’t allow early termination based on prefixes.
The solver itself could be slightly more space efficient, because it creates new a string through each recursive call rather than modifying a character array. However, as the search continues onto successive words, some of this copying is necessary (the updated grid, the words found in each solution, etc.).
The Swing UI isn’t particularly well written, but it does display everything required for a solution. First, potential solutions are shown next to the grid:
Next, for a particular solution, the highlighted word is shown in a decreasing shade to show the order in which letters must be selected:
Overall, this was a relatively interesting side-project, with a few things such as the trie and solution sorting which added a little depth to the implementation.
That said, I’d recommend completely ignoring this code and playing WordBrain unassisted. It’s a lot of fun!