数独是流传很广的经典问题，本身就挺有意思。计算机求解搜索加回溯也是经典的入门问题，我就经常拿来当面试问。
计算机求解数独有很多脑洞大开的办法，比如数独可以看作一个特殊的二元可满足性优化问题，所有的最优化方法都能直接应用，直接调solver或者一些非梯度优化算法（蚁群算法，遗传算法，模拟退火等等）
我觉得最有意思的是前几年的一个github repo，Can Convolutional Neural Networks Crack Sudoku Puzzles?，暴力的把数独填充当作矩阵补全问题，通过卷积神经网络训练几百万对数独问题和答案，做到了86%的准确率。相信加更多的层数和更新的架构可以进一步的提高准确率。最有意思的是能看出来数独竟然是可以训练的，有一点反直觉。
但是做不到100%准确率是个遗憾，我就把这个方法向前再推一步，依然使用卷积神经网络进行训练，但是对于每一个未知的格子不再单纯的填概率最高的数字，而是拿到每一个格子对应的数字概率分布，使用这个信息来加速搜索。具体的做法是搜索到某一个格子，优先尝试概率最大的数字，同样会执行失败回溯。做了简单的perf测试，对于平均情况，搜索次数略有减少，但是因为多了一次大开销的inference，实际耗时半斤八两。有一个比较大的优势是新的搜索方法更稳定，可以保证每一个问题都能很快求解，对于极端例子
1 | hard1 = '.....6....59.....82....8....45........3........6..3.54...325..6..................' |
甚至能加速三万倍。详细代码和样例放在了github上面：sudoku-neural
可以进一步思考的地方比如经典数独问题是9x9的样本空间，暴力搜索+启发式规则+剪枝还是可以算的动的，如果推广出去比如15维或者19维这样子呢。大胆的猜想是在某个临界值会出现只有使用神经网络训练加速搜索才能在有限时间求解，有时间我会跟进一下。
这里面的优化是非常朴素的，把（领域知识 + 启发式规则）变成一个模型来求解了一个特定的最优化问题。那么这个思路能不能推广到最优化solver上面呢，像是cplex或者gurobi这种之所以这么快最大的秘密我猜是启发式规则写的好，能不能使用某种数据来训练一个通用的模型来加速搜索？具体的优化问题和深度网络结合也是这几年的热点之一，Bengio有一篇综述：Machine Learning for Combinatorial Optimization: a Methodological Tour d’Horizon可以参考一下，目前的工作都不太实用，处于探索性阶段，最大的问题还是如何建模，数独问题偏偏就有这么简单清晰的模型（不用处理自己就是2维或者3维的tensor）能不能打开新的思路呢？