all*_*aws 12
您可能对谷歌搜索由Appel和Jacobson(1988)撰写的研究论文"The World's Eastest Scrabble Program"感兴趣.算法以伪代码概述,因此需要花费一些工作才能将其塑造成可用的形式并将它们粘合在一起; 但是,作者概述的程序非常有用.
将您的字典存储为树,例如:
*
|
+----+----+
| |
A* B
| |
+--+--+ E*
| | |
P S +-+-+
| | | |
P* K* A E*
| |
+-+-+ +-+-+
| | | |
E L D* N*
| |
A E*
|
L*
感谢paxdiablo让我的树更具可读性.
这棵树有单词a,app,appeal,apple,ask,bead,bean,be和bee.标有星号的节点表示"如果我要停在这里,这将是一个有效的单词",例如'be'下面的'e'下面的'e'.
当您找到一封您不知道的信件时,请使用通配符(即,选择所有孩子并递归所有路径).
你说填字游戏,但是你的"字母......制作单词"似乎表明了拼字游戏.这对两者都有效.不是最快,但速度很快.
感谢Andreas提醒我们这被称为trie.
如果你想说"第二个字母是P"你将从根节点开始并取每个分支(这将是字母表中的每个字母,假设它是一个正确的字典),然后是"P"分支,然后去从那里开始.
我之前实际上写了一个填字游戏程序(含糊不清但构造背后的理论是相同的).
我有一个单词及其线索的数据库,可以按使用的时间排序(这样我就不会在后续运行中获得重复的填字游戏).
你要做的第一件事就是设计你的图案(黑色,你不能把字母和白色放在哪里).在动态创建模式时尝试将单词插入网格中非常耗时并且容易出错.如果你看大多数填字游戏,他们往往会遵循某些规则,以使其更容易.就像在一条对角线周围对称并且不允许四个白色单元的正方形(以便于选择合适的单词的任务)之类的事情.
一旦你有了模式,那么你就开始找到要放在其中的单词.这样,您就会知道"app"是该单词的开头,并且能够将您的搜索限制为以"app"开头的搜索,而不是每个包含"app"的单词.类似地,对于您在任何位置已知字母的单词.在已知位置定位带字母的单词比在单词中的任何起始位置评估这些字母要容易得多.
我最终用shell脚本编写(信不信由你),并使用来自Linux的字典作为单词搜索工具.如果你知道你有一个以"app"开头的5个字母的单词,它很容易使用:
grep '^app..$' words.txt
获得所有有效可能性的列表.
并且,当找到每个单词时,它被复制到包含单词和多个可能线索的clues.txt文件中.实际格式是使用{count,word,clue},其中同一个单词可能存在于具有不同线索的多行上 - 这允许grep通过管道,sort以便较少使用的单词/线索漂浮到顶部(每当一个单词/线索是使用时,其计数增加,使其下次使用的可能性降低.
一旦该文件大小合适,程序将首先使用它来定位单词,并且只有在未找到单词的情况下,它才会恢复到需要手动干预的单词文件(无线索).
它实际上最终做得很好.它的速度并不快,但我不需要每三秒生成一个 - 这是一个每周发送一次的社区通讯.
现在您已将问题更改为Scrabble变体,这实际上要困难得多.
你需要考虑你的信件,董事会上的信件以及你需要评估更多地方的事实.这使得暴力方法更加困难.
我作为初始剪切将做的是选择随机选择的可能性(棋盘上的起始位置和方向),然后使用与上面的填字游戏变体相同的算法来找到可以适合那里的所有单词.然后,如果您有满足该单词的字母,请将其(及其分数)存储在列表中.
请记住,您需要注意干扰电路板上的其他字样.
我将继续研究可能性,直到下列之一:
最后一个是重要的 - 如果你是初学者,你不想详尽地检查数百万种可能性.
然后,从列表中选择最佳移动(或者如果在初学者级别玩,则可能不是最佳移动 - 这完全取决于您希望计算机有多好).