algorithm - How to find list of possible words from a letter matrix [Boggle Solver] - Stack Overflow

algorithm - How to find list of possible words from a letter matrix [Boggle Solver] - Stack Overflow

My answer works like the others here, but I'll post it because it looks a bit faster than the other Python solutions, from setting up the dictionary faster. (I checked this against John Fouhy's solution.) After setup, the time to solve is down in the noise. grid = "fxie amlo ewbx astu".split() nrows, ncols = len(grid), len(grid[0]) # A dictionary word that could be a solution must use only the grid's # letters and have length >= 3. (With a case-insensitive match.) import re alphabet = ''.join(set(''.join(grid))) bogglable = re.compile('[' + alphabet + ']{3,}$', re.I).match words = set(word.rstrip('\n') for word in open('words') if bogglable(word)) prefixes = set(word[:i] for word in words for i in range(2, len(word)+1)) def solve(): for y, row in enumerate(grid): for x, letter in enumerate(row): for result in extending(letter, ((x, y),)): yield result def extending(prefix, path): if prefix in words: yield (prefix,

Read full article from algorithm - How to find list of possible words from a letter matrix [Boggle Solver] - Stack Overflow