单词搜索算法

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应该是一个很好的起点。

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