So I was looking into the “Boggle Board” question which is posted on several programming interview sites. The question is pretty straight forward even if you dont know the game “boggle” which it is based on. You have a nxm matrix of letters and the aim of the game is to make words from those letters. From any arbitraty starting letter you are allowed to travel from letter to letter in any direction including diagonals with the restriction that you cant use the same letter twice.
The interview quetion usually asks candidates to to determine, given a 4x4 boggle board, whether a given word is in the board.
The problem seems deceptively simple but the requirement that you mustnt revisit a letter means that any kind of recursive solution is going to have to keep track of a whole bunch of state and get messy really quickly.
Graph Search
The simplicity of a graph search based solution becomes apparent if you solve the meaty part of the problem first.
To solve this problem with a graph search algorithm we need the letters in a graph. Lets create a node object that we can build a graph out of:
We would create a Node \* for each letter in the boggle board and then link it to the nodes that letter is adjacent to. There is now no need to store the Nodes in an array matrix that represents the board or anything like that as all the information about the board we need is encapsulated in these two pieces of data. Now assuming we can get the board represented in a bunch of Node objects all in an NSSet the algorithm for searching through them is relatively simple.
We take each Node in turn and do a depth first search on its neighbours for a match for the next letter in the word we are checking for.
For the depthFirstSearch function we need to do a few things.
1. Keep track of visited Nodes so we don’t visit the same one twice
2. Keep track of depth so we know our position in the word
3. Recursively search through the adjacent nodes
1234567891011121314151617181920212223
BOOLdepthFirstSearch(Node*node,NSString*word,NSIntegerdepth,NSMutableSet*visitedNodes){unicharnodeLetter=[node.lettercharacterAtIndex:0];unicharwordLetter=[wordcharacterAtIndex:depth];[visitedNodesaddObject:node];if(nodeLetter==wordLetter){//if we have a match and have letters left keep searching//else we are at the end of the word so return YESif(depth<word.length-1){for(Node*adjacentNodeinnode.adjacentNodes){if([visitedNodescontainsObject:adjacentNode])continue;BOOLfound=depthFirstSearch(adjacentNode,word,depth+1,visitedNodes);if(found)returnfound;}}elsereturnYES;}[visitedNodesremoveObject:node];returnNO;}
And thats it. Two simple functions achieve the objectives of the questions in 30 lines of code. For some interviewers this may be enough as this is considered to be the hard part of the question.
Going Further
There are several directions you could take this to make it more fully formed. For example, given a matrix of arrays could we build the graph? Also if were keeping the graph around it might make sense to make a graph object and make the search a method on a graph instance along with a graph generation method on the class. Ive tied it all together in a excerpt you can actually paste and run into an xcode command line app.