Home > Applied Algorithms, Arrays, Graph, Tree > Boggle Solver

Boggle Solver

A facebook recruiter asked me to write the code for this particular problem. While I was able to suggest the algorithm correctly, I messed up my code. So here is the problem statement:

Given a 4×4 array with randomly selected letters in it and a dictionary of valid words, find which words can be made from this array by starting from any of the 16 letters and moving in any direction (the only constraint being that you cannot come to a node twice while making a word)

The first thing you should see here that this is clearly a Graph problem. The second noticeable aspect is that the maximum length of a word from such an array (with the constraint) can be 16 and the minimum length can be 1.

Since you have to look for all possible combinations starting from every point, Depth First Search comes to mind (why not Breadth First Search? Think about it). What you should do is apply DFS starting at each of the 16 nodes in the array. At every step, you add the newly formed word to a data structure meant to store strings (not allowing duplicates).

Once you have this data structure ready with you, all you need to do is search for each word in the dictionary that you have been provided. 🙂

Clear enough?

PS: Please code the DFS in the 4×4 array. It is not as simple as you assume it to be. 🙂

PPS: Does anyone have a better solution?

Advertisements
  1. sanjoydas
    April 7, 2012 at 8:38 pm

    I think you can solve this by building a trie (well, not exactly) from the 4×4 matrix. This can be done elegantly, using only 16 nodes, and the constraint of not revisiting a node can be fixed by passing around a set of nodes already visited.

    I think this solution is close to optimal, since you’re not generating any extra strings. It can be optimized further by intelligently handling duplicate neighboring characters.

    http://pastebin.com/LnvzVmLd

    Moreover, it might be possible, with some effort, to bypass the creation of the trie altogether, and use the matrix itself as a trie.

    • April 7, 2012 at 8:46 pm

      Yes, I can use a trie. But a dictionary can have millions of words. And searching each of them in a trie is not efficient.

      • sanjoydas
        April 7, 2012 at 8:50 pm

        Right, I didn’t consider that. Linearly going through the dictionary is very stupid. Anyways, fun problem. 🙂

  2. August 5, 2014 at 10:33 pm

    My Approach : I assume the dictionary of words is a trie . so basically when you run dfs from each of the nodes you simultaneously traverse the reached node (of dfs) in the trie and if any of them end up as a valid string(leaf node in trie) , you increment the match_count . If you want the matching string too , then during the build of trie you can maintain pointer(s) to the string to which it points (assume dictionary of words are in an array).

    My Question : For this quesstion we would need to find all possible paths frm node A to node B right ? how is this handled ? will running dfs from every node do this?

    • December 5, 2014 at 10:49 am

      I agree with your approach of maintaining the Dictionary as a trie. It is essentially what I suggested, except that you can do away with storing all the combinations. However, why do you need the pointer to string from the trie nodes that you mentioned?

      And of course, DFS from each node will cover all possible paths. There is nothing that you have to search for. The DFS simply implies covering all paths in a DFS-like manner. Apologies if I confused you.

  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: