如何从字母矩阵中找到可能的单词列表[Boggle Solver]

Question

如何从字母矩阵中找到可能的单词列表[Boggle Solver]最近我一直在我的iPhone上玩一款名为Scramble的游戏。有些人可能认为这个游戏是Boggle。基本上，当游戏开始时你得到一个像这样的字母矩阵：F X I EA M L OE W B XA S T U游戏的目标是尽可能多地找到可以通过将字母链接在一起形成的单词。你可以从任何字母开始，并且它周围的所有字母都是公平的游戏，然后一旦你继续下一个字母，围绕那个字母的所有字母都是公平的游戏，除了以前使用的任何字母。因此在上面的网格，例如，我能想出的话LOB，TUX，SEA，FAME，等词必须至少有3个字符，并且不超过N×N个字符以上，这将是本场比赛16，但可以在一些实现改变。虽然这个游戏很有趣且令人上瘾，但我显然不是很擅长它而且我想通过制作一个可以给我最好的单词的程序来作弊（单词越长，得分就越多）。（来源：boggled.org）遗憾的是，我不熟悉算法或效率等等。我第一次尝试使用字典，如这一个（〜2.3MB），并确实试图以配合字典条目组合线性搜索。这需要很长时间才能找到可能的单词，而且由于每轮只有2分钟，所以根本就不够。我很想知道Stackoverflowers是否可以提供更有效的解决方案。我主要是在寻找使用Big 3 Ps的解决方案：Python，PHP和Perl，尽管Java或C ++也很酷，因为速度至关重要。当前的解决方案：Adam Rosenfield，Python，〜20年代John Fouhy，Python，~3sKent Fredric，Perl，~1sDarius Bacon，Python，~1srvarcher，VB.NET （实时链接），~1sPaolo Bergantino，PHP （实时链接），~5s（本地~2s）

Answer 1

我的回答与其他人一样，但是我会发布它，因为它看起来比其他Python解决方案更快，从更快地设置字典。（我对John Fouhy的解决方案进行了检查。）设置完成后，解决的时间是噪音。

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 resultdef extending(prefix, path):
    if prefix in words:
        yield (prefix, path)
    for (nx, ny) in neighbors(path[-1]):
        if (nx, ny) not in path:
            prefix1 = prefix + grid[ny][nx]
            if prefix1 in prefixes:
                for result in extending(prefix1, path + ((nx, ny),)):
                    yield resultdef neighbors((x, y)):
    for nx in range(max(0, x-1), min(x+2, ncols)):
        for ny in range(max(0, y-1), min(y+2, nrows)):
            yield (nx, ny)

样品用法：

# Print a maximal-length word and its path:print max(solve(), key=lambda (word, path): len(word))

编辑：过滤少于3个字母的单词。

编辑2：我很好奇为什么Kent Fredric的Perl解决方案更快; 事实证明，使用正则表达式匹配而不是一组字符。在Python中做同样的事情会使速度提高一倍。