假如你對數獨解法感興趣，你可能聽說過精確覆蓋問題。給定全集 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)