Sudoku

题意：求解数独问题。

思路：用DLX解。首先，需要将格盘建模为DLX用到的十字链表。数字之间的互斥关系共有4种，因此可以对”每行每个数字”、”每列每个数字”、”每九宫格每个数字”、”每个格点位置”分别建立一个链表列，也即总共是9*9+9*9+9*9+9*9=324个链表列，十字链表中每一行表示在某格点放置某数，分别与4个对应的链表列相交。

然后，就是正式的深搜了。在深搜的每一层：
1) 在十字链表表头中找出元素最少且非零的一列，将该列以及列中包含的所有行元素从十字链表中移除；
2) 枚举列中的每行（作为解的一部分），将与该行相交的所有其他列以及这些列包含的行元素在十字链表中移除，递归下一层深搜;
3) 递归返回时，需要将2)中移除的相应列和行添加回十字链表；
4) 所有行枚举完毕时，需要将1)中移除的相应列和行添加回十字链表。

注意，对链表进行增删操作时，需要以相反的顺序修改各结点。同时，也需要动态维护表头的元素数。

没有想出太好的优化。c++下跑了188ms。

ps：
记得最早是11年寒假时，和Arios一起留校做MCM时听他提到，当时那道建模题可以用Dancing Links解。一晃眼，3年多过去了，我这才开始读Knuth的这篇论文。

文章本身的算法不算难懂，因为深搜的优化是很多问题都要用到的。之前做题的时候，确实也有考虑过对链表进行动态调整，但发现无法根本上降低时间复杂度（依然是指数时间）后，也没有深究了。而Knuth这篇论文里介绍的DLX，通过对十字链表进行动态调整从而尽量保持搜索树最优，可以说是在通常情况下将深搜优化到了极致。

做这题数独时，在链表建模那一步想了大概一整天时间。主要是数独问题元素间的互斥情况比较复杂。一开始只用了前3种互斥关系，发现表头记录的元素数无法正确维护，每次暴力重算并加了些优化后竟然勉强过了。然后就一直在想正解。想出应该增加第4种互斥关系后，又用了很长时间才推出要移除与当前行元素互斥的所有行。最后对链表的修改要比一开始想的要复杂得多。

查了下status，Arios在5年前作出的时间是32ms，并且是1A 47ms过的。实在是很强。