从给定的单词最大化交叉点生成填字游戏

Question

是否有一些可行的（即多项式时间）算法，从一小组（~20）个单词开始，一个填字游戏最大化（或至少是"big"）的数量路口？或者，如果交集标准不切实际，是否可以最大化填字游戏的密度（在某种意义上）？

我已经在Python写了一个详尽的搜索，但是超过六个字就太长了...

另请参阅： Algorithm to generate a crossword（但那里的答案虽然很好，但并没有真正解决我的问题）。

Answer 1

有多项式时间算法吗？

答案：没有

对于一个简单的版本：如果一个单词结尾的字母与另一个单词开头的字母相同，我们可以将它们连接起来。例如：

cat+tree+element -> Valid
aaa+aaa -> Valid
cab+aboard -> Invalid ('a' != 'b')

问题是：尽可能多地连接单词。

但是它等价于哈密顿路径问题，所以我们没有任何多项式时间算法可以解决这个问题。

详情见此：Hamiltonian path problem

PS:

对于较小的（~20）集合，您可以尝试启发式搜索或动态规划方法来获得可行的解决方案。