娱乐 每 日 算 法 挑 战 【第B期】

[yhz012]

艹，感觉又到了我的本职工作了，某种意义上和扫雷或者数独差不多吧，准确来说离数独更近，扫雷比这个还会涉及到一些置信度问题以及一些局部的SAT问题快速求解

 

因为反正只有24个词，我先根据长度sort一下应该不亏

另外我姑且假设不存在连续的2个词排在一起，所以根据长度已经可以剪枝掉很大一部分情况了。而且算一下格子和字符串长度能不能对上，对不上根本不用试了，直接QAQ就好了

 

接下来就先从可选情况最少的开始试就好了吧，这是最基本的heuristic

可选情况举例来说

现在有3个5字母，1个6字母，2个7字母

那应该先试1个6字母的，然后再试7字母的，最后是5字母的

 

另外我还有一个会有用的heuristic来tie-break

对于相同的可能情况，比如2个4字母的，1个3字母的，优先选用和其他格子交叉多的，比如3字母的和另外2个交叉，而6字母的只和1个交叉，那么先填3字母的，接着再填6字母的

加入4字母的交叉分别是1个和2个，7字母的交叉分别是3个和1个，那优先把3个交叉的7字母空格丢进来，然后再试2交叉的4字母

 

（说白了就是优先选用可能性最少，且对其他限制最多的来试

 

填入之后，根据交叉，就可以搜索指定长度字符串内指定位置带指定字母这样的字符串了，如果没有，直接剪枝然后backtrack

 

如果剪枝剪秃了，那就QAQ吧，不然会得到搜索结果的

四月 21, 2020，由yhz012修改