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

(来源:boggled.org)不幸的是，我不太擅长算法或它们的效率等等.我的第一次尝试使用字典 例如这个 (~2.3MB) 并进行线性搜索，尝试将组合与字典条目相匹配.这需要很长时间才能找到可能的单词，而且由于每轮只有 2 分钟，这根本不够.我有兴趣看看是否有任何 Stackoverflowers 可以提出更有效的解决方案.我主要是在寻找使用三大 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 (实时链接)，~5 秒(本地~2 秒)) 解决方案 我的答案和这里的其他答案一样，但我会发布它，因为它看起来比其他 Python 解决方案快一点，从更快地设置字典.(我根据 John Fouhy 的解决方案检查了这一点.)设置后，解决的时间减少了.grid = "fxie amlo ewbx astu".split()nrows, ncols = len(grid), len(grid[0])# 可以作为解决方案的字典单词必须仅使用网格的# 字母并且长度大于等于 3.(不区分大小写匹配.)进口重新字母 = ''.join(set(''.join(grid)))bogglable = re.compile('[' + 字母 + ']{3,}$', re.I).matchwords = set(word.rstrip('') for word in open('words') if bogglable(word))prefixes = set(word[:i] for word in words对于范围内的 i(2, len(word)+1))定义解决():对于 y，枚举(网格)中的行:对于 x，枚举中的字母(行):对于扩展(字母，((x，y)，))的结果:产出结果定义扩展(前缀，路径):如果单词前缀:产量(前缀，路径)对于(nx，ny)在邻居(路径[-1])中:如果 (nx, ny) 不在路径中:前缀 1 = 前缀 + 网格 [ny][nx]如果前缀为 prefix1:对于扩展(前缀1，路径+((nx，ny)，))的结果:产出结果定义邻居((x，y)):对于范围内的 nx(max(0, x-1), min(x+2, ncols)):对于范围内的 ny(max(0, y-1), min(y+2, nrows)):产量 (nx, ny)示例用法:# 打印最大长度的单词及其路径:打印 max(solve(), key=lambda (word, path): len(word))过滤掉少于 3 个字母的单词.编辑 2: 我很好奇为什么 Kent Fredric 的 Perl 解决方案更快；结果证明使用正则表达式匹配而不是一组字符.在 Python 中做同样的事情，速度会提高一倍.Lately I have been playing a game on my iPhone called Scramble. Some of you may know this game as Boggle. Essentially, when the game starts you get a matrix of letters like so:F X I EA M L OE W B XA S T UThe 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).(source: boggled.org)I am, unfortunately, not very good with algorithms or their efficiencies and so forth. My first attempt uses a dictionary such as this one (~2.3MB) and does a linear search trying to match combinations with dictionary entries. This takes a very long time to find the possible words, and since you only get 2 minutes per round, it is simply not adequate.I am interested to see if any Stackoverflowers can come up with more efficient solutions. I am mostly looking for solutions using the Big 3 Ps: Python, PHP, and Perl, although anything with Java or C++ is cool too, since speed is essential.CURRENT SOLUTIONS:Adam Rosenfield, Python, ~20sJohn Fouhy, Python, ~3sKent Fredric, Perl, ~1sDarius Bacon, Python, ~1srvarcher, VB.NET, ~1sPaolo Bergantino, PHP (live link), ~5s (~2s locally) 解决方案 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 realphabet = ''.join(set(''.join(grid)))bogglable = re.compile('[' + alphabet + ']{3,}$', re.I).matchwords = set(word.rstrip('') 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)Sample usage:# Print a maximal-length word and its path:print max(solve(), key=lambda (word, path): len(word))Edit: Filter out words less than 3 letters long.Edit 2: I was curious why Kent Fredric's Perl solution was faster; it turns out to use regular-expression matching instead of a set of characters. Doing the same in Python about doubles the speed. 这篇关于如何从字母矩阵中找到可能的单词列表 [Boggle Solver]的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！ 上岸，阿里云！