如何從字母矩陣中找到可能的單詞列表[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）
3 回答
慕尼黑5688855
TA貢獻1848條經驗 獲得超2個贊
我的回答與其他人一樣，但是我會發布它，因為它看起來比其他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中做同樣的事情會使速度提高一倍。
添加回答
舉報
0/150
提交
取消