最近我一直在iPhone上玩一款名为《Scramble》的游戏。有些人可能知道这个游戏叫拼字游戏。从本质上讲，当游戏开始时，你会得到一个字母矩阵:
F X I E
A M L O
E W B X
A S T U
The goal of the game is to find as many words as you can that can be formed by chaining letters together. You can start with any letter, and all the letters that surround it are fair game, and then once you move on to the next letter, all the letters that surround that letter are fair game, except for any previously used letters. So in the grid above, for example, I could come up with the words LOB, TUX, SEA, FAME, etc. Words must be at least 3 characters, and no more than NxN characters, which would be 16 in this game but can vary in some implementations. While this game is fun and addictive, I am apparently not very good at it and I wanted to cheat a little bit by making a program that would give me the best possible words (the longer the word the more points you get).
(来源:boggled.org)
不幸的是，我不太擅长算法或它们的效率等等。我的第一次尝试使用一个像这样的字典(约2.3MB)，并进行线性搜索，试图匹配字典条目的组合。这需要花费很长时间来找到可能的单词，因为你每轮只有2分钟的时间，这是不够的。
我很有兴趣看看是否有任何Stackoverflowers可以提出更有效的解决方案。我主要是在寻找使用三大p的解决方案:Python、PHP和Perl，尽管任何使用Java或c++的东西也很酷，因为速度是至关重要的。
目前的解决方案:
Adam Rosenfield, Python， ~20岁
John Fouhy, Python， ~3秒
Kent Fredric, Perl， ~1s
Darius Bacon, Python， ~1s
rvarcher, VB。净,~ 1 s
Paolo Bergantino, PHP(实时链接)，~5s(本地~2s)
如何简单的排序和使用字典中的二进制搜索?
在0.35秒内返回整个列表，并可以进一步优化(例如删除含有未使用字母的单词等)。
from bisect import bisect_left
f = open("dict.txt")
D.extend([line.strip() for line in f.readlines()])
D = sorted(D)
def neibs(M,x,y):
n = len(M)
for i in xrange(-1,2):
for j in xrange(-1,2):
if (i == 0 and j == 0) or (x + i < 0 or x + i >= n or y + j < 0 or y + j >= n):
continue
yield (x + i, y + j)
def findWords(M,D,x,y,prefix):
prefix = prefix + M[x][y]
# find word in dict by binary search
found = bisect_left(D,prefix)
# if found then yield
if D[found] == prefix:
yield prefix
# if what we found is not even a prefix then return
# (there is no point in going further)
if len(D[found]) < len(prefix) or D[found][:len(prefix)] != prefix:
return
# recourse
for neib in neibs(M,x,y):
for word in findWords(M,D,neib[0], neib[1], prefix):
yield word
def solve(M,D):
# check each starting point
for x in xrange(0,len(M)):
for y in xrange(0,len(M)):
for word in findWords(M,D,x,y,""):
yield word
grid = "fxie amlo ewbx astu".split()
print [x for x in solve(grid,D)]
我建议根据单词做一个字母树。这棵树将由字母结构组成，像这样:
letter: char
isWord: boolean
然后构建树，每个深度添加一个新字母。换句话说，第一层是字母表;然后从这些树中，会有另外26个条目，以此类推，直到你把所有的单词都拼出来。坚持这个解析树，它将使所有可能的答案更快地查找。
使用这个解析过的树，您可以非常快速地找到解决方案。下面是伪代码:
BEGIN:
For each letter:
if the struct representing it on the current depth has isWord == true, enter it as an answer.
Cycle through all its neighbors; if there is a child of the current node corresponding to the letter, recursively call BEGIN on it.
这可以通过一些动态编程来加快。例如，在你的样本中，两个“A”都在一个“E”和一个“W”旁边，这(从它们击中它们的点来看)是相同的。我没有足够的时间来详细说明这个代码，但我想你们可以理解。
此外，我相信你会找到其他解决方案，如果你谷歌“Boggle solver”。
