单词搜索算法

我试图想出一个比“蛮力”方法更好的方法，但在某种程度上是一种损失。单词搜索算法

下面是一个简单的例子：

鉴于预选择的字母有限数，和一个舱口（像一个纵横重叠），我试图找到词语的所有组合都可以使用。（字被从字典数据库中检索。）

实施例：

鉴于字母：
A，C，R，E，T，U，P，L，M，O
多少组合的话可以适应以下填字游戏？

_ 
_ _ _ _ 
    _ 
    _ 
    _ _ _

一个例子：

c 
t r e e 
    e 
    e 
    p o t

当然显着地与每个字母或除字谜舱口搜索时间增加。任何更好的搜索方式的建议？

来源

2011-09-09 kylex

我可以用'sed's | /.* ||'来减少62 000个单词的字典/var/cache/postgresql/dicts/en_us.dict | egrep“^ [acretuplmo] {3,5} $”|在第一次粗略剪切中，用566个单词。但我很好奇：你使用4次'e'，但没有使用'a'。这样好吗？ –

是的，单词是使用提供的任何字母创建的（每个字母可以多次使用） – kylex

查看开放源代码arccc，填入纵横填字网格，将它们视为constraint satisfaction problem。如果你想自己做一个学习练习，阅读CSP应该是一个很好的起点。

至于限制字母表，最好在源词典上作为预处理步骤完成。

来源

2011-09-09 02:57:35

单词搜索算法

回答

相关问题