How to do a recursive search for a word in the Boggle game board?

Question

Can someone help me with a psuedocode or even the recursive formula that describes the recursive search for a word in the Boggle board so I can get started?

Answer 1

Assuming you have a word list available somewhere, likely stored in a Trie data structure (I've created a working Trie with comments on improving its efficiency here).

Once you have a Trie structure (a prefix tree) which allows you to search for words based on their prefixes, you would want to use a recursive method something like the following psudo-code.

char[][] gameBoard = new char[4][4];
List<String> wordList = new ArrayList<String>();
//fill in the game board with characters
//Start the word search at each letter
for(int x = 0; x < 4; x++){
    for(int y = 0; y < 4; y++){
        recursiveWordSearch(x, y, "");
    }
}
recursiveWordSearch(int x, int y, String word){
    //Concatenate gameBoard[x][y] to word.
    //Check to see if word is a valid word (check against your word list).
    //If word, add to wordList

    /*Check word list to see if any words contain current prefix. If not,
     then there's no point in continuing further (return). IE if AQZ isn't the 
     start of any word at all in the list, no reason to keep adding letters, it's
     never going to make a word.  */

    //Otherwise recursively call this method moving left/right/up/down
    recursiveWordSearch(x+1, y, word); //move right
    recursiveWordSearch(x, y+1, word); //move up
    recursiveWordSearch(x-1, y, word); //move left
    recursiveWordSearch(x, y-1, word); //move down
    /*You'll want to make sure that x-1, x+1, y-1 and y+1 are valid values before
     sending them. */


}