algorithm - 词搜索算法

Question

我正试图想出一种比“蛮力”方法更好的方法，但有点不知所措。

这是一个简单的例子:

给定有限数量的预选字母和阴影线(如填字游戏重叠)，我试图找到可以使用的所有单词组合。 (单词是从字典数据库中检索的。)

例子:

给定字母:
a,c,r,e,t,u,p,l,m,o
下面的填字游戏可以包含多少种单词组合？

   _
 _ _ _ _ 
   _
   _
   _ _ _

一个例子:

  c
t r e e
  e
  e
  p o t

当然，搜索时间会随着每个字母或填字游戏阴影线的增加而显着增加。对于更好的搜索方式有什么建议吗？

Answer 1

查看开源 arccc , 它通过将填字游戏网格视为 constraint satisfaction problem 来填充填字游戏网格.如果您想自己将此作为学习练习，阅读 CSP 应该是一个很好的起点。

至于限制字母表，最好作为对源字典的预处理步骤来完成。