如何从字母矩阵中找到可能的单词列表[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个字符，并且不超过N×N个字符，这将是本场比赛16，但可以在一些实现改变。尽管这款游戏既有趣又令人上瘾，但我显然并不擅长于此，我想通过编写一个程序给我一些欺骗，该程序将为我提供尽可能最好的单词（单词越长，您获得的积分就越多）。

样本虫
（来源：boggled.org）

不幸的是，我对算法或其效率等不是很好。我的第一次尝试是使用诸如此类的字典（〜2.3MB），并进行线性搜索以尝试将组合与字典条目匹配。这需要很长时间才能找到可能的单词，并且由于您每轮只能得到2分钟，因此这根本不够用。

我很想看看是否有任何Stackoverflowers可以提出更有效的解决方案。我主要在寻找使用Big 3 P的解决方案：Python，PHP和Perl，尽管Java或C ++的任何功能也很酷，因为速度至关重要。

当前解决方案：

• 亚当·罗森菲尔德（Adam Rosenfield），Python，约20秒
• John Fouhy，Python，大约3秒
• Kent Fredric，Perl，〜1秒
• Darius Bacon，Python，〜1秒
• rvarcher，VB.NET （实时链接），〜1s
• Paolo 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 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中执行相同的操作可使速度提高一倍。