An Android app which finds all the valid words in a game of Boggle.
Boggle is a game which involves locating possible words in a random 4x4 grid of letters. Words can be made by constructing letters which are horizontally, vertically or diagonally adjacent.
This application is a small toy which locates all the possible words in a given grid, which is useful for verifying player's answers or simply for fun at the end of a round to see what players missed:
The algorithm works by performing a depth-first search of the letter grid and comparing each of the possibilities to a vocabulary of known words. This is optimised by storing the vocabulary in a Trie - by navigating the prefix tree and keeping track of the current node as we perform the DFS we can abandon search branches which would not yield any word matches.