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

Question

最近我一直在我的 iPhone 上玩一款名为 Scramble 的游戏。你们中有些人可能知道这个游戏是 Boggle。本质上，当游戏开始时，您会得到一个字母矩阵，如下所示:

F X I E
A M L O
E W B X
A S T U

游戏的目标是尽可能多地找到可以通过将字母串在一起组成的单词。你可以从任何一个字母开始，它周围的所有字母都是公平游戏，然后一旦你移动到下一个字母，那个字母周围的所有字母都是公平游戏，除了之前使用过的字母 。所以在上面的网格中，例如，我可以想出 LOB 这个词, TUX , SEA , FAME , 等等。单词必须至少有 3 个字符，并且不能超过 NxN 个字符，在这个游戏中是 16 个，但在某些实现中可能会有所不同。虽然这款游戏既有趣又令人上瘾，但我显然不太擅长，我想通过制作一个程序来作弊一点，该程序会给我最好的单词(单词越长，您获得的分数就越多)。

_{(来源:boggled.org)}

不幸的是，我不太擅长算法或它们的效率等等。我的第一次尝试使用字典 such as this one (~2.3MB) 并进行线性搜索，尝试将组合与字典条目相匹配。这需要非常很长时间才能找到可能的词，而且由于每轮只有 2 分钟，所以这根本不够。

我很想知道是否有任何 Stackoverflowers 可以提出更有效的解决方案。我主要在寻找使用 Big 3 P 的解决方案:Python、PHP 和 Perl，尽管使用 Java 或 C++ 的任何东西也很酷，因为速度是必不可少的。

当前的解决方案:

• Adam Rosenfield，Python，20 多岁
• John Fouhy，Python，~3 岁
• Kent Fredric，Perl，~1s
• Darius Bacon，Python，~1s
• rvarcher，VB.NET，~1s
• Paolo Bergantino，PHP (live link) , ~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 result

def 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 result

def 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 中执行相同的操作大约会使速度提高一倍。