NXN Boggle Game

Problem: Solve the boggle game with 5X5 square. Each cell in the square is a letter (from A-Z).  The interior cells can have 8 directions (including diagonal)  as next move, the border cells have 5 or 3 directions. Start from any cell, just go with the possible directions, you will have a path. The path can only contain a cell once (you can't visit the cell you had visited). If the path represents a valid English word, output it:

Solution: Use recursion to solve this problem. Also a trie is used.

• Globally, we have a hash table for all valid words (paths) and a trie to store the dictionary
• Start from each cell, we have current_word (the path we had visited), all the visited paths (can be implemented as a hash table or a matrix).
• Start from that cell, we append the cell to the current_word. If current_word is not a visited path, we update visited path, otherwise we return.  If the path is over the maximum length (N*N), we return.
• Then check if current_word is in trie (we can have a recursive checking method), if not, we return. The use of trie here can save us time from exploring some invalid path (not a word). 
• If current_word is a valid word, we update the global hash table.
• Then we explore the all possible directions and make those recursive calls.
• For each cell (as the starting cell), we repeat the above process.