Why does DFS work when trying to find all valid words in a Boggle board

Question

I was solving the Boggle game programmatically and noticed that Depth First Search can be used to find all valid combinations of letters in a board. A Boggle board is described here.

Say we have a 4x4 board. For each character on the board, use DFS to find all paths in the board (the only rule is you can't use a single character more than once). Why does DFS work for this when a Boggle board isn't really a graph? Also, what other types of problems can DFS be applied to that are similar to this usage?

Answer 1

You can apply DFS or other graph algorithms because you basically play on a grid graph with diagonals as well.

Put your letters instead of the dots and you have your graph. Now why DFS would work here?

When you create a word in this game - you connect adjacent vertices and thus creating a path on the graph. So here is an approach which you can start with (and improve on).

1. Create a set of all words in English alphabet and a reasonable length of a word (let's assume that words are not longer than N chars)
2. Start iterating from the vertices and from each vertex invoke DFS that runs till the length N. For each of the words (that are bigger than 3 in the rules) check if it is in the dictionary and if it is - save them somewhere.

You can see that in my part of the graph you can easily find the word TORUS.

Why does it make sense to use DFS and not BFS? A couple of reasons are:

• easier to implement
• way smaller space complexity

What is the complexity of my algorithm Assume that you have a a grid n * m and the longest word has a length d. Because in my algorithm you implement DFS from all the vertices and complexity of DFS is O(b^d) where an average branch is a little bit smaller than 8 (may be even smaller than 7 because you can't have loops here). The search in the set id O(1). So the complexity is m * n * 8^d.

How can you improve it? There is little sense in trying to search the word TLRSOU because there are no words in English alphabet that start with TLR. So a better idea is to store words in a trie and terminate fast the branches that do not makes sense.

Answer 2

That's because it is (or can be) represented by a graph. Boggle words are made from adjacent letters that run horizontally, vertically, or diagonally. So you can make a graph of connections between letters, by following this rule. Additionally, DFS will not visit a node twice, because it keeps a list of nodes already visited. So it satisfies the other rule that a letter can be used only once.

DFS (and BFS, too), will eventually discover every path through the graph, so you can compare the list of paths so generated with a dictionary of valid words to determine the total number of valid words from a single Boggle board.

The most well-known use of DFS is of course for pathfinding - almost any space can be mapped into a graph and then the shortest or longest path found. DFS can be good for finding the radius of a graph, and thus the centre-most node. This can be useful for things like flood-fill algorithms, where you want to fill the interior of an irregular shape quickly, as the edge expansion will happen the fastest when started from the center of the graph.