最近我一直在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)


当前回答

我已经在OCaml中实现了一个解决方案。它将字典预编译为trie,并使用双字母序列频率来消除单词中永远不会出现的边,以进一步加快处理速度。

它在0.35ms内解决了示例板的问题(额外的6ms启动时间主要与将trie加载到内存有关)。

找到的解决方案:

["swami"; "emile"; "limbs"; "limbo"; "limes"; "amble"; "tubs"; "stub";
 "swam"; "semi"; "seam"; "awes"; "buts"; "bole"; "boil"; "west"; "east";
 "emil"; "lobs"; "limb"; "lime"; "lima"; "mesa"; "mews"; "mewl"; "maws";
 "milo"; "mile"; "awes"; "amie"; "axle"; "elma"; "fame"; "ubs"; "tux"; "tub";
 "twa"; "twa"; "stu"; "saw"; "sea"; "sew"; "sea"; "awe"; "awl"; "but"; "btu";
 "box"; "bmw"; "was"; "wax"; "oil"; "lox"; "lob"; "leo"; "lei"; "lie"; "mes";
 "mew"; "mae"; "maw"; "max"; "mil"; "mix"; "awe"; "awl"; "elm"; "eli"; "fax"]

其他回答

搞笑。几天前我差点因为这款该死的游戏而发布了同样的问题!然而我没有,因为我只是在谷歌上搜索boggle solver python,得到了我想要的所有答案。

我花了3个月的时间致力于解决10个最佳点密集的5x5 Boggle板问题。

这个问题现在已经解决了,并在5个网页上进行了全面披露。有问题请联系我。

该棋盘分析算法使用显式堆栈,通过具有直接子信息的有向无环词图伪递归遍历棋盘方格,并使用时间戳跟踪机制。这很可能是世界上最先进的词汇数据结构。

该方案在四核上每秒评估大约10,000块非常好的电路板。(9500 +分)

父网页:

DeepSearch.c - http://www.pathcom.com/~vadco/deep.html

组件网页:

最佳记分牌- http://www.pathcom.com/~vadco/binary.html

高级词汇结构- http://www.pathcom.com/~vadco/adtdawg.html

板分析算法- http://www.pathcom.com/~vadco/guns.html

并行批处理- http://www.pathcom.com/~vadco/parallel.html

- 只有追求最好的人才会对这本全面的著作感兴趣。

最快的解决方案可能是将字典存储在一个trie中。然后,创建一个三元组队列(x, y, s),其中队列中的每个元素对应于一个可以在网格中拼写的单词的前缀s,结束于位置(x, y)。初始化队列中有N x N个元素(其中N是网格的大小),网格中的每个正方形都有一个元素。然后,算法进行如下:

While the queue is not empty:
  Dequeue a triple (x, y, s)
  For each square (x', y') with letter c adjacent to (x, y):
    If s+c is a word, output s+c
    If s+c is a prefix of a word, insert (x', y', s+c) into the queue

如果将字典存储在trie中,则可以在常数时间内测试s+c是否是单词或单词的前缀(前提是还在每个队列数据中保留一些额外的元数据,例如指向trie中当前节点的指针),因此此算法的运行时间为O(可拼写的单词数量)。

[编辑]下面是我刚刚编写的Python实现:

#!/usr/bin/python

class TrieNode:
    def __init__(self, parent, value):
        self.parent = parent
        self.children = [None] * 26
        self.isWord = False
        if parent is not None:
            parent.children[ord(value) - 97] = self

def MakeTrie(dictfile):
    dict = open(dictfile)
    root = TrieNode(None, '')
    for word in dict:
        curNode = root
        for letter in word.lower():
            if 97 <= ord(letter) < 123:
                nextNode = curNode.children[ord(letter) - 97]
                if nextNode is None:
                    nextNode = TrieNode(curNode, letter)
                curNode = nextNode
        curNode.isWord = True
    return root

def BoggleWords(grid, dict):
    rows = len(grid)
    cols = len(grid[0])
    queue = []
    words = []
    for y in range(cols):
        for x in range(rows):
            c = grid[y][x]
            node = dict.children[ord(c) - 97]
            if node is not None:
                queue.append((x, y, c, node))
    while queue:
        x, y, s, node = queue[0]
        del queue[0]
        for dx, dy in ((1, 0), (1, -1), (0, -1), (-1, -1), (-1, 0), (-1, 1), (0, 1), (1, 1)):
            x2, y2 = x + dx, y + dy
            if 0 <= x2 < cols and 0 <= y2 < rows:
                s2 = s + grid[y2][x2]
                node2 = node.children[ord(grid[y2][x2]) - 97]
                if node2 is not None:
                    if node2.isWord:
                        words.append(s2)
                    queue.append((x2, y2, s2, node2))

    return words

使用示例:

d = MakeTrie('/usr/share/dict/words')
print(BoggleWords(['fxie','amlo','ewbx','astu'], d))

输出:

['fa', 'xi', 'ie', 'io', 'el', 'am', 'ax', 'ae', 'aw', 'mi', 'ma', 'me', 'lo', 'li', 'oe', 'ox', 'em', 'ea', 'ea', 'es', 'wa', 'we', 'wa', 'bo', 'bu', 'as', 'aw', 'ae', 'st', 'se', 'sa', 'tu', 'ut', 'fam', 'fae', 'imi', 'eli', 'elm', 'elb', 'ami', 'ama', 'ame', 'aes', 'awl', 'awa', 'awe', 'awa', 'mix', 'mim', 'mil', 'mam', 'max', 'mae', 'maw', 'mew', 'mem', 'mes', 'lob', 'lox', 'lei', 'leo', 'lie', 'lim', 'oil', 'olm', 'ewe', 'eme', 'wax', 'waf', 'wae', 'waw', 'wem', 'wea', 'wea', 'was', 'waw', 'wae', 'bob', 'blo', 'bub', 'but', 'ast', 'ase', 'asa', 'awl', 'awa', 'awe', 'awa', 'aes', 'swa', 'swa', 'sew', 'sea', 'sea', 'saw', 'tux', 'tub', 'tut', 'twa', 'twa', 'tst', 'utu', 'fama', 'fame', 'ixil', 'imam', 'amli', 'amil', 'ambo', 'axil', 'axle', 'mimi', 'mima', 'mime', 'milo', 'mile', 'mewl', 'mese', 'mesa', 'lolo', 'lobo', 'lima', 'lime', 'limb', 'lile', 'oime', 'oleo', 'olio', 'oboe', 'obol', 'emim', 'emil', 'east', 'ease', 'wame', 'wawa', 'wawa', 'weam', 'west', 'wese', 'wast', 'wase', 'wawa', 'wawa', 'boil', 'bolo', 'bole', 'bobo', 'blob', 'bleo', 'bubo', 'asem', 'stub', 'stut', 'swam', 'semi', 'seme', 'seam', 'seax', 'sasa', 'sawt', 'tutu', 'tuts', 'twae', 'twas', 'twae', 'ilima', 'amble', 'axile', 'awest', 'mamie', 'mambo', 'maxim', 'mease', 'mesem', 'limax', 'limes', 'limbo', 'limbu', 'obole', 'emesa', 'embox', 'awest', 'swami', 'famble', 'mimble', 'maxima', 'embolo', 'embole', 'wamble', 'semese', 'semble', 'sawbwa', 'sawbwa']

Notes: This program doesn't output 1-letter words, or filter by word length at all. That's easy to add but not really relevant to the problem. It also outputs some words multiple times if they can be spelled in multiple ways. If a given word can be spelled in many different ways (worst case: every letter in the grid is the same (e.g. 'A') and a word like 'aaaaaaaaaa' is in your dictionary), then the running time will get horribly exponential. Filtering out duplicates and sorting is trivial to due after the algorithm has finished.

我建议根据单词做一个字母树。这棵树将由字母结构组成,像这样:

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”。

下面是我的java实现:https://github.com/zouzhile/interview/blob/master/src/com/interview/algorithms/tree/BoggleSolver.java

Trie构建耗时0小时0分1秒532毫秒 单词搜索花了0小时0分0秒92毫秒

eel eeler eely eer eke eker eld eleut elk ell 
elle epee epihippus ere erept err error erupt eurus eye 
eyer eyey hip hipe hiper hippish hipple hippus his hish 
hiss hist hler hsi ihi iphis isis issue issuer ist 
isurus kee keek keeker keel keeler keep keeper keld kele 
kelek kelep kelk kell kelly kelp kelper kep kepi kept 
ker kerel kern keup keuper key kyl kyle lee leek 
leeky leep leer lek leo leper leptus lepus ler leu 
ley lleu lue lull luller lulu lunn lunt lunule luo 
lupe lupis lupulus lupus lur lure lurer lush lushly lust 
lustrous lut lye nul null nun nupe nurture nurturer nut 
oer ore ort ouphish our oust out outpeep outpeer outpipe 
outpull outpush output outre outrun outrush outspell outspue outspurn outspurt 
outstrut outstunt outsulk outturn outusure oyer pee peek peel peele 
peeler peeoy peep peeper peepeye peer pele peleus pell peller 
pelu pep peplus pepper pepperer pepsis per pern pert pertussis 
peru perule perun peul phi pip pipe piper pipi pipistrel 
pipistrelle pipistrellus pipper pish piss pist plup plus plush ply 
plyer psi pst puerer pul pule puler pulk pull puller 
pulley pullus pulp pulper pulu puly pun punt pup puppis 
pur pure puree purely purer purr purre purree purrel purrer 
puru purupuru pus push puss pustule put putt puture ree 
reek reeker reeky reel reeler reeper rel rely reoutput rep 
repel repeller repipe reply repp reps reree rereel rerun reuel 
roe roer roey roue rouelle roun roup rouper roust rout 
roy rue ruelle ruer rule ruler rull ruller run runt 
rupee rupert rupture ruru rus rush russ rust rustre rut 
shi shih ship shipper shish shlu sip sipe siper sipper 
sis sish sisi siss sissu sist sistrurus speel speer spelk 
spell speller splurt spun spur spurn spurrer spurt sput ssi 
ssu stre stree streek streel streeler streep streke streperous strepsis 
strey stroup stroy stroyer strue strunt strut stu stue stull 
stuller stun stunt stupe stupeous stupp sturnus sturt stuss stut 
sue suer suerre suld sulk sulker sulky sull sully sulu 
sun sunn sunt sunup sup supe super superoutput supper supple 
supplely supply sur sure surely surrey sus susi susu susurr 
susurrous susurrus sutu suture suu tree treey trek trekker trey 
troupe trouper trout troy true truer trull truller truly trun 
trush truss trust tshi tst tsun tsutsutsi tue tule tulle 
tulu tun tunu tup tupek tupi tur turn turnup turr 
turus tush tussis tussur tut tuts tutu tutulus ule ull 
uller ulu ululu unreel unrule unruly unrun unrust untrue untruly 
untruss untrust unturn unurn upper upperer uppish uppishly uppull uppush 
upspurt upsun upsup uptree uptruss upturn ure urn uro uru 
urus urushi ush ust usun usure usurer utu yee yeel 
yeld yelk yell yeller yelp yelper yeo yep yer yere 
yern yoe yor yore you youl youp your yourn yoy 

注意: 我在这个线程的开头使用了字典和字符矩阵。代码在我的MacBookPro上运行,下面是关于这台机器的一些信息。

型号:MacBook Pro 型号标识符:MacBookPro8,1 处理器名称:Intel Core i5 处理器速度:2.3 GHz 处理器数量:1 总核数:2 L2缓存(每核):256kb L3 Cache: 3mb 内存:4gb 引导ROM版本:MBP81.0047.B0E SMC版本(系统):1.68f96