单词搜索算法

Question

我试图提出一种比"蛮力"方法更好的方法,但我有点不知所措.

这是一个简单的案例:

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

例:

给出字母:
a,c,r,e,t,u,p,l,m,o
在下面的填字游戏中可以容纳多少个单词组合？

   _
 _ _ _ _ 
   _
   _
   _ _ _

一个例子:

  c
t r e e
  e
  e
  p o t

当然,随着每个字母或填字游戏的加法,搜索时间会急剧增加.有什么建议可以更好地搜索？

Answer 1

查看开源arccc，它通过将填字游戏网格视为约束满足问题来填充填字游戏网格。如果您想自己执行此操作作为学习练习，那么阅读 CSP 应该是一个很好的起点。

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