How to solve the Boggle problem?

Boggle problem is an interesting problem. And it is not that hard if you are familiar with DFS algorithm. You can find the problem descriptions from the link below.

https://www.geeksforgeeks.org/boggle-find-possible-words-board-characters/

In this link, C++, JAVA solutions are provided. Python solution is missing. I’d like to provide a python code to solve this problem.

"""
jimmy shen
Nov 22, 2019
reference
https://www.geeksforgeeks.org/boggle-find-possible-words-board-characters/
problems:
Boggle (Find all possible words in a board of characters) | Set 1
Given a dictionary, a method to do lookup in dictionary and a M x N board where every cell has one character. Find all possible words that can be formed by a sequence of adjacent characters. Note that we can move to any of 8 adjacent characters, but a word should not have multiple instances of same cell.

Example:

Input: dictionary[] = {"GEEKS", "FOR", "QUIZ", "GO"};
       boggle[][]   = {{'G', 'I', 'Z'},
                       {'U', 'E', 'K'},
                       {'Q', 'S', 'E'}};
      isWord(str): returns true if str is present in dictionary
                   else false.

Output:  Following words of dictionary are present
         GEEKS
         QUIZ
"""
class Boggle(object):
    def find_words(self, words, boggle):
         """
         input: words is the dictionary contains all possible words
         boggle is the boggle
         output: a list contains word_in_boggle for all possible words  
         """
         R, C = len(boggle), len(boggle[0])
         def dfs(i, j, word, seen):
             if i>=R or i<0 or j>=C or j<0:return False 
             if (i,j) in seen:return False
             if not word:return True
             if boggle[i][j] != word[0]:
                 return False
             else:
                 seen.add((i, j))
                 return any(dfs(i+di, j+dj, word[1:], seen) 
                               for di, dj in [(0,1),(1,0),(-1,0),(0,-1),(-1,-1),(1,-1),(-1,1),(1,1)])
         def word_in_boggle(word):
            for i in range(R):
                for j in range(C):
                    if dfs(i,j,word,set()):
                        return True
            return False
            
         return [word_in_boggle(word) for word in words]

b = Boggle()
words = ["GEEKS", "FOR", "QUIZ", "GO"]
boggle = [['G', 'I', 'Z'],
          ['U', 'E', 'K'],
          ['Q', 'S', 'E']]
print(b.find_words(words, boggle))