Recently had to figure out how to program a Boggle algorithm. Boggle is a simple board game I never had the pleasure of playing by itself, but have played plenty of related variations of. These kinds of algorithms are pretty interesting and I had a lot of fun programming different solutions. I’ll share 2 solutions.

Boggle is relatively simple. I never had the pleasure of playing by itself, but have played plenty of related variations of.

You have a square game board with dice of various letters that is n x n. The board gets shaken/randomized and a timer starts. The player scores points by finding valid words on the board that are longer than 3 characters, with longer words scoring more points. The rules are that letters have to be adjacent or diagonal to the last letter in the word to continue. And you can never repeat a letter you’ve already used, so while you can have multiple of the same letter, its the die itself you can’t return to.

I decided to tackle it in C++.

Visually you can treat it as snake. You pick a starting letter, you move to an adjacent letter, then another letter, and so on, without crossing back through or over your “path” of letters you’ve gobbled up. Each letter you tack onto your growing word, you want to see if its a valid word otherwise you won’t score points.

So without looking, in my opinion, there are 2 obvious ways to go about solving a given boggle board and some valid word dictionary.

1. Recursively search through every possible “word” on the board, constantly checking each substring against the dictionary. This should result in a permutation running time.
2. Recursively search through possible words on that board, but only continue to search through possible words that we know exist in the dictionary. (E.g Pretending the word “apple” is invalid, we would stop searching for the word and any other possible suffixes it could have in the dictionary if the dictionary doesn’t contain the prefix “app”) This should result in a linear running time for n-words to spell.

Solution 1 is naive. Its the most obvious and “human” solution. For each word, look it up in the dictionary. But the search space is huge. For a 6×6 board, you’re looking at 6! x 6! = 518400 lookups. Not good. But here it is none the less.

Solution 2 is better. Instead of a standard dictionary, its using what is called a trie. Or also called a prefix tree! Its quite fun actually. So the root node of the tree is empty string. The children nodes are the first letter of every possible word in the dictionary. And their children are the next possible letter of every possible word that comes after that first letter. And so on. This significantly enhances our search because now, instead of searching every word that comes up, we can quickly eliminate entire recursions if we see that the prefix doesn’t exist. Again, imagine the word “apple” doesnt exist in our world. And it comes up on the boggle board in some combination of tiles. We see the letter ‘a’ and immediately find it in our trie. We now can move onto the letter ‘p’, which does exists after the letter ‘a’ node in our tree. But (lets say) the third letter (second ‘p’) does not exist in the tree. The prefix ‘app’ doesn’t exist in our dictionary. Stop the search, and look at a different possible path.

This is different from Solution 1 because instead of stopping at ‘app’, we continue to search for ‘appl’ ‘apple’ ‘applex’ ‘applext’ ‘applextl’ or whatever other possible paths come up on the boggle board to lookup for possible words. They’re evil permutations, drastically wasting our time if we already know its impossible for the world ‘apple’ to exist, nevermind the word ‘applextl’. Here is my trie implementation, just beware of some inneficiencies I’ve identified. This search can also be identified as “depth-first”.

Now, after the trie, I figured there might be something even faster than a trie.  The trie struggles with boards around 6 size or greater. And there could be faster. The trick with the following solution is that it entirely depends on the dictionary size. A dictionary with 600,000 words apparently still pulls it off much faster than the previous 2 methods.

3. Eliminate words from the dictionary that do not exist on the board using dynamic programming. There is a writeup and code about it there that also discusses the previous two methods I just talked about, possibly clearer. The way it works is to look at the board and remove any words that dont have these letters. Boggle boards actually have different distributions of letters, especially depending on the version, but even assuming any letter can show up on the board, you can speed up the process significantly by removing words with the letters and then building potential words to cross check with your now greatly reduced dictionary. For example, when you’re iterating over all child nodes to see if your letter exists, it will only have to check against the possible letters on the board (if they exist in the path anyway)

That’s not all. You can do a bunch of other methods too. You could hash the board letters to numbers. Do further elimination of possibilities using queues of triplets or quads that each represent prefixes of a word, then do searching on each for adjacent squares. Or regex. Lots of various solution methods here.

But overall the combination of trie + elimination of potential words seems to be the best search algorithm.