假如你对数独解法感兴趣，你可能听说过精确覆盖问题。给定全集 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的表示有轻微的不同。事实上，我们需要能快速删除和添加行到每列，这就是为什么我们使用集合。另一方面，高德纳没有提到这点，实际上整个算法中所有行是保持不变的。
以下是算法的代码。
def solve(x, y, solution=[]):
if not x:
yield list(solution)
else:
c = min(x, key=lambda c: len(x[c]))
for r in list(x[c]):
solution.append(r)
cols = select(x, y, r)
for s in solve(x, y, solution):
yield s
deselect(x, y, r, cols)
solution.pop()
def select(x, y, r):
cols = []
for j in y[r]:
for i in x[j]:
for k in y[i]:
if k != j:
x[k].remove(i)
cols.append(x.pop(j))
return cols
def deselect(x, y, r, cols):
for j in reversed(y[r]):
x[j] = cols.pop()
for i in x[j]:
for k in y[i]:
if k != j:
x[k].add(i)
真的只有 30 行！
格式化输入
在解决实际问题前，我们需要将输入转换为上面描述的格式。可以这样简单处理
x = {j: set(filter(lambda i: j in y[i], y)) for j in x}
但这样太慢了。假如设 x 大小为 m，y 的大小为 n，则迭代次数为 m*n。在这例子中的数独格子大小为 n，那需要 n^5 次。我们有更好的办法。
x = {j: set() for j in x}
for i in y:
for j in y[i]:
x[j].add(i)
这还是 o(m*n) 的复杂度，但是是最坏情况。平均情况下它的性能会好很多，因为它不需要遍历所有的空格位。在数独的例子中，矩阵中每行恰好有 4 个条目，无论大小，因此它有n^3的复杂度。
优点
简单: 不需要构造复杂的数据结构，所有用到的结构python都有提供。
可读性: 上述第一个例子是直接从wikipedia上的范例直接转录下来的！
灵活性: 可以很简单得扩展来解决数独。
求解数独
我们需要做的就是把数独描述成精确覆盖问题。这里有完整的数独解法代码，它能处理任意大小，3×3，5×5，即使是2×3，所有代码少于100行，并包含doctest！（感谢winfried plappert 和 david goodger的评论和建议）