仅利用30行Python代码来展示X算法
假如你对数独解法感兴趣，你可能听说过精确覆盖问题。给定全集X和X的子集的集合Y，存在一个Y的子集Y*，使得Y*构成X的一种分割。
这儿有个Python写的例子。
X={1,2,3,4,5,6,7}
Y={
'A':[1,4,7],
'B':[1,4],
'C':[4,5,7],
'D':[3,5,6],
'E':[2,3,6,7],
'F':[2,7]}
这个例子的唯一解是['B','D','F']。
精确覆盖问题是NP完备（译注：指没有任何一个够快的方法可以在合理的时间内，意即多项式时间找到答案）。X算法是由大牛高德纳发明并实现。他提出了一种高效的实现技术叫舞蹈链，使用双向链表来表示该问题的矩阵。
然而，舞蹈链实现起来可能相当繁琐，并且不易写地正确。接下来就是展示Python奇迹的时刻了！有天我决定用Python来编写X算法，并且我想出了一个有趣的舞蹈链变种。
算法
主要的思路是使用字典来代替双向链表来表示矩阵。我们已经有了Y。从它那我们能快速的访问每行的列元素。现在我们还需要生成行的反向表，换句话说就是能从列中快速访问行元素。为实现这个目的，我们把X转换为字典。在上述的例子中，它应该写为
X={
1:{'A','B'},
2:{'E','F'},
3:{'D','E'},
4:{'A','B','C'},
5:{'C','D'},
6:{'D','E'},
7:{'A','C','E','F'}}
眼尖的读者能注意到这跟Y的表示有轻微的不同。事实上，我们需要能快速删除和添加行到每列，这就是为什么我们使用集合。另一方面，高德纳没有提到这点，实际上整个算法中所有行是保持不变的。
以下是算法的代码。
defsolve(X,Y,solution=[]): ifnotX: yieldlist(solution) else: c=min(X,key=lambdac:len(X[c])) forrinlist(X[c]): solution.append(r) cols=select(X,Y,r) forsinsolve(X,Y,solution): yields deselect(X,Y,r,cols) solution.pop() defselect(X,Y,r): cols=[] forjinY[r]: foriinX[j]: forkinY[i]: ifk!=j: X[k].remove(i) cols.append(X.pop(j)) returncols defdeselect(X,Y,r,cols): forjinreversed(Y[r]): X[j]=cols.pop() foriinX[j]: forkinY[i]: ifk!=j: X[k].add(i)
真的只有30行！
格式化输入
在解决实际问题前，我们需要将输入转换为上面描述的格式。可以这样简单处理
X={j:set(filter(lambdai:jinY[i],Y))forjinX}
但这样太慢了。假如设X大小为m，Y的大小为n，则迭代次数为m*n。在这例子中的数独格子大小为N，那需要N^5次。我们有更好的办法。
X={j:set()forjinX}
foriinY:
forjinY[i]:
X[j].add(i)
这还是O(m*n)的复杂度，但是是最坏情况。平均情况下它的性能会好很多，因为它不需要遍历所有的空格位。在数独的例子中，矩阵中每行恰好有4个条目，无论大小，因此它有N^3的复杂度。
优点
- 简单:不需要构造复杂的数据结构，所有用到的结构Python都有提供。
- 可读性:上述第一个例子是直接从Wikipedia上的范例直接转录下来的！
- 灵活性:可以很简单得扩展来解决数独。
求解数独
我们需要做的就是把数独描述成精确覆盖问题。这里有完整的数独解法代码，它能处理任意大小，3×3，5×5，即使是2×3，所有代码少于100行，并包含doctest！（感谢WinfriedPlappert和DavidGoodger的评论和建议）