def readFile(path):
    with open(path, 'rt') as f:
        return f.read()

def loadWordsAndPrefixes(wordsFile, minLen):
    baseWords = readFile(wordsFile).upper().splitlines()
    words = set()
    for word in baseWords:
        if (not word.startswith('#') and
            (len(word) >= minLen)):
            words.add(word)
    prefixes = set()
    for word in words:
        for i in range(1,len(word)-1):
            prefixes.add(word[:i])
    return words, prefixes

def solveBoggle(board):
    rows, cols = len(board), len(board[0])
    def solve(board, row, col, prefix, moves):
        # prefix got us to board[row][col], solve from there
        result = set()
        for newRow in [row-1, row, row+1]:
            for newCol in [col-1, col, col+1]:
                if (((newRow, newCol) != (row, col)) and
                    ((newRow, newCol) not in moves) and
                    (newRow >= 0) and (newRow < rows) and
                    (newCol >= 0) and (newCol < cols)):
                        moves.add((newRow, newCol))
                        newPrefix = prefix + board[newRow][newCol]
                        if newPrefix in words:
                            result.add(newPrefix)
                        if newPrefix in prefixes:
                            result.update(solve(board, newRow, newCol, newPrefix, moves))
                        moves.remove((newRow, newCol))
        return result
    result = set()
    for row in range(rows):
        for col in range(cols):
            result.update(solve(board, row, col, '', set()))
    return result

WORDS_FILE = 'words.txt'
WORDS_FILE = '10k_common_words.txt'
WORDS_FILE = 'scrabble_words.txt'

words, prefixes = loadWordsAndPrefixes(WORDS_FILE, minLen=3)
board = [ 'AFROG',
          'MBEID',
          'JRCOP',
        ]

solution = solveBoggle(board)
print(solution)