有103,005个结点和19组解 (X在23处) 有106,232个结点和20组解 (X在24处)
有126,636个结点和26组解 (X在33处,P没有翻转)。
Golomb和Baurnert [16]建 议，在每个回溯的过程中，选择能够导出最少分支的子问题，任何时候这都是可以被有效完成的。在精确覆盖问题中，这意味着我们希望每步都选择在当前A中包含 1最少的列。幸运的是我们将看到dancing links技术让我们相当好地做到这一点；使用这个技术后，Scott的骨牌问题的搜索树将分别仅有：
10,421 个结点 (X在23处) 12,900 个结点 (X在24处)
14,045 个结点 (X在33处,P没有翻转)。
舞蹈步骤。一个实现X算法的好方法就是将矩阵A中的每个1用一个有5个域L[x]、R[x]、U[x]、D[x]、C[x]的数据对象（data object）x来表示。矩阵的每行都是一个经由域L和R(“左”和“右”)双向连接的环状链表；矩阵的每列是一个经由域U和D(“上”和“下”)双向连接的环状链表。每个列链表还包含一个特殊的数据对象，称作它的表头（list header）。
这些表头是一个称作列对象（column object）的大型对象的一部分。每个列对象y包含一个普通数据对 象的5个域L[y]、R[y]、U[y]、D[y]和C[y]，外加两个域S[y]（大小）和N[y]（名字）；这里“大小”是一个列中1的个数，而“名 字”则是用来标识输出答案的符号。每个数据对象的C域指向相应列头的列对象。 表头的L和R连接着所有需要被覆盖的列。这个环状链表也包含一个特殊的列对象称作“根”，h，它相当于所有活动表头的主人。而且它不需要U[h]、D[h]、C[h]、S[h]和N[h]这几个域。
举个例子，（3）中的0-1矩阵将用这些数据对象来表示，就像图2展示的那样，我们给这些列命名为A、B、C、D、E、F和G（这个图表在上下左右处“环绕扭曲”。C的连线没有画出，因为他们会把图形弄乱；每个C域指向每列最顶端的元素）。
图2 完全覆盖问题（3）的四方向连接表示法
我们寻找所有精确覆盖的不确定性算法现在可以定型为下面这个明析、确定的形式，即一个递归过程search(k)，它一开始被调用时k=0： 如果 R[h]=h ，打印当前的解（见下）并且返回。 否则选择一个列对象c（见下）。 覆盖列c（见下）。
对于每个r←D[c]，D[D[c]]，……，当 r!=c， 设置 Ok<-r；
对于每个j←R[r]，R[R[r]]，……，当 j!=r， 覆盖列j（见下）； search(k+1)；
设置 r←Ok 且 c←C[r]；
对于每个j←L[r]，L[L[r]]，……，当 j!=r， 取消列j的覆盖（见下）。 取消列c的覆盖（见下）并且返回。
输出当前解的操作很简单：我们连续输出包含O0、O1、……、Ok-1的行,这里包含数据对象O的行可以通过输出N[C[O]]、N[C[R[O]]]、N[C[R[R[O]]]]……来输出。
为了选择一个列对象c,我们可以简单地设置c<-R[h]；这是最左边没有覆盖的列。或者如果我们希望使分支因数达到最小，我们可以设置s<-无穷大，那么接下来： 对于每个j←R[h]，R[R[h]]，……，当 j!=h， 如果 S[j]
那么c就是包含1的序数最小的列(如果不用这种方法减少分支的话，S域就没什么用了)。
覆盖列c的操作则更加有趣：把c从表头删除并且从其他列链表中去除c链表的所有行。
设置 L[R[c]]←L[c] 且 R[L[c]]←R[c]。 对于每个i←D[c]，D[D[c]]，……，当 i!=c， 对于每个j←R[i]，R[R{i]]，……，当 j!=i， 设置 U[D[j]]←U[j]，D[U[j]]←D[j]， 并且设置 S[C[j]]←S[C[j]]-1。
操作（1），就是我在本文一开始提到的，在这里他被用来除去水平、竖直方向上的数据对象。
最后，我们到达了整个算法的尖端，即还原给定的列c的操作。这里就是链表舞蹈的过程：
对于每个i←U[c]，U[U[c]]，……，当 j!=i， 对于每个j←L[i]，L[L[i]]，……，当 j!=i， 设置 S[C[j]]←S[C[j]]+1，
并且设置 U[D[j]]←j，D[U[j]]←j。 设置 L[R[c]]←c 且 R[L[c]]←c。
注意到还原操作正好与覆盖操作执行的顺序相反，我们利用操作（2）来取消操作（1）。（其实没必要严格限制“后执行的先取消”，由于j可以以任何顺 序穿过第i行；但是从下往上取消对行的移除操作是非常重要的，因为我们是从上往下把这些行移除的。相似的，对于第r行从右往左取消列的移除操作也是十分重 要的，因为我们是从左往右覆盖的。）
图3 图2中第A列后面的链表被覆盖
考虑一下，例如，对图2表示的数据（3）执行search(0)会发生什么。通过从其他列移除A的行来将其覆盖；那么现在整个结构就成了图3的样子。注意现在D列出现了不对称的链接：上面的元素首先被删除，所以它仍然指向初始的邻居，但是另一个被删除的元素指向了列头。
继续search(0)，当r指向（A，D，G）这一行的A元素时，我们也覆盖D列和G列。图4展示了我们进入search(1)时的状态，这个数据结构代表削减后的矩阵
现在search(1)将覆盖B列，而且C列将没有“1”。因此search(2)将什么也找不到。接着search(1)会找不到解并返回，图4的状态会恢复。外部的过程，search(0)，将把图4变回图3，而且它会让r前进到（A，D）行的A元素处。
图4 图3中D列和G列后的链被覆盖
很快就能找到解，并输出
A D E F C B G
如果在选择c的时候无视S域，会输出
A D B G C E F
如果每步选择最短的列。（每行输出的第一项是已经完成分支的列的名字）在一些例子上试验过这个算法的读者应该会明白我为什么给这篇论文选这个标题。 效率分析。当算法X用Dancing Links实现时，让我们称之为DLX算法。DLX算法的运行时间本质上和它执行操作（1）来移除表中对象的次数是成比例的；这同时也是它执行操作（2）来还原对象的次数。我们把这个数量称作更新（updates） 的次数。如果每步选择最短的列，则在对（3）求解的的过程中共做了28次更新：第0层更新10次，第1层更新14次，第2层更新4次。如果我们忽略启发条 件S，这个算法就在第1层更新16次，在第2层更新7次，总计33次。但是在后者的更新明显快些，因为S[C[j]←S[C[j]]±1这样的语句可以忽
略；因此全部的运行时间会少些。当然，我们在给启发条件S的期望效果下一般结论前还需要对一些大规模的实例进行分析。
图5 Scott的12片5格骨牌拼图问题的搜索树