Tag: boggle

如何从字母matrix中find可能的单词列表

最近我一直在我的iPhone上玩游戏，叫做Scramble。 你们中的一些人可能会把这个游戏理解为Boggle。 从本质上讲，当游戏开始时，你得到一个像这样的字母matrix： FXIE AMLO EWBX ASTU 游戏的目标是find尽可能多的单词链接在一起形成的单词。 你可以从任何字母开始，围绕它的所有字母都是公平的游戏，然后一旦你移动到下一个字母，围绕这个字母的所有字母都是公平的游戏， 除了以前使用的任何字母 。 所以，在上面的网格中，例如，我可以想出LOB ， TUX ， SEA ， FAME等词。单词必须至less有3个字符，并且不超过NxN个字符，在这个游戏中可以是16个，但是可以在一些实现中有所不同 虽然这个游戏很有趣，而且让人上瘾，但是我显然不是很擅长这个游戏，我想通过制作一个能够给我最好的单词（这个单词越长得分越多）的程序来作弊。 示例Boggle http://www.boggled.org/sample.gif 不幸的是，我不擅长algorithm或其效率等等。 我第一次尝试使用这样一个字典（〜2.3MB），并进行线性search，试图将组合与字典条目进行匹配。 这需要很长时间才能find可能的单词，而且由于每轮只能得到2分钟，所以根本不够。 我很感兴趣，看看是否有任何Stackoverflowers可以拿出更有效的解决scheme。 我主要是在寻找使用Big 3 Ps的解决scheme：Python，PHP和Perl，尽pipeJava或C ++也是很酷的，因为速度是必不可less的。 当前解决scheme ： Python的Adam Rosenfield，大约20多岁 约翰·福伊（John Fouhy），Python，〜3s Kent Fredric，Perl，〜1s 大stream士培根，Python，〜1s rvarcher，VB.NET （live link） ，〜1s Paolo Bergantino，PHP （live link） ，〜5s（本地〜2s） BOUNTY ： 我为这个问题增添了一笔赏金，这是我向所有参与其中的人们表示感谢的方式。 不幸的是，我只能给你们中的一个人接受答案，所以我将从现在起7天内衡量谁是最快的求助者，并奖励获奖者。 赏金赏赐。 感谢所有参与的人。