This past weekend I visited with some friends and we played Boggle. One of my friends who played is really good a word-based games. She trounced all of us horribly, to the point that we only played the game once because it just wasn't fun for the rest of us.
But it did get me thinking about how I would go about writing the most efficient Boggle solver I could in Python. as a mental exercise. I know that Boggle solvers exist out there, but I wanted to try to think the program out for fun.
First thing to do is to store a list of words efficiently. I think a trie would work really well here. Not only does it minimize memory usage, but I think with the approach I have in mind for finding words it will also be fast once the trie is built.
With the list of possible words in an easy-to-search form, the board now needs to be traversed. With the rules as they are, the letters can be viewed as a graph. Starting at any letter, you keep a list of letters seen that match potential words according to the trie. As the graph is traversed, you color each visited node so that you don't reuse the letter. Each completed word you find you record and then continue the traversal, following each node.
When a dead-end is reached you just back up, uncoloring the nodes you just tried. Since a list is being kept of visited (and thus colored) nodes, backing up a node is a constant operation by just uncoloring the last visited node and then looking at the end of the list. And since we are dealing with letters that means you can keep the edges in a sorted list, making it easy to keep track of what the next edge to traverse is. That saves on bookkeeping by keeping track of what edges have already been looked at (although generators could easily get around this by having a parallel list that holds on to generators that generates neighbors for each node, thus getting around any sort cost or having to worry about searching a list for the next item or making a linked list that knows something about what the next node to look at would be).
Probably someday I will get around to actually implementing these ideas for fun.
