这个操作是把x重新链接到双向链中。

       当然，指出这种操作以后，这个结果是显然的。但是，当我真正认识到操作（2）的作用以后，我突然感到了定义“啊哈”这个词语时候的感觉 ^_^ ，因为，L[x]和R[x]的值在X删除以后早已没有了它原来的语义。确实，一个精心设计的程序在删除x后会通过设置L[x],R[x]等于x 或者赋值位null来清理掉这些不用的数据结构。而让一个链外的对象指向链本身有时具有潜在的危险性。例如，指针就可以干扰垃圾回收机制的运作。

       那么是什么关于操作（2）的研究促使我写一整片论文来讨论这个问题呢？当x从链表删除以后；为什么又有人想把它放回链表中？恩！我承认，数据结构的更新通常来说是永久性的，但是非永久性的更新也时常发生。例如，在一个交互性的程序中，用户很可能想删除他所做的一系列操作，恢复到先前的状态。另一个典型的应用发生在backtrack programs(回溯程序)[16]里,回溯程序枚举约束集合里的所有解。回溯，也叫深度所搜，在之前的论文中有讨论到。

       操作（2）的观点是Hitotumatu和Noshita[22]于1979年提出的。他们在解决n皇后问题中提出了著名的Dijkstra's算法。[6,pages 72-82] 在使用了这个技巧后程序的速度比不使用几乎快了2倍。

       Floyd's 优雅的论述了回溯 和非确定性算法[11]都包含精确的数据结构更新算法。通常来说，回溯程序可以被考虑为一种搜索，所要做的就是确定这个任务需要搜索的范围，同时组织好数据用于控制搜索流程。解决问题的每一步操作，都将影响剩余问题的可解性。

       简单情况下，我们可以考虑维护一个栈，用来保存当前搜索树节点之前的所有相关状态信息，但是这个任务的拷贝动作需要耗时太多。因此，我们通常选用全局数据结构。这样无论搜索进行到何种程度，它都会保留相关状态信息，并且当搜索回溯的时候它都能恢复先前状态。

       例如，Dijkstra算法的回溯在三个全局boolean变量数组中产生n皇后问题的状态队列，他们分别表示棋盘上的列，2条对角线。Hitotumatu和Noshita在他们的程序中使用双向链来记录所有列和对角线上的可能性。当Dijkstra算法暂时放置一个皇后在棋盘上的时候，会把boolean数组里的一个数据从true改为false；回溯后又将这个数据改回true。Hitotumatu和Noshita使用（1）去删除一列，使用（2）去恢复删除操作。这意味着他们可以不通过搜索便找到一个空列。程序通过这种方法记录下每个状态信息，这样替换和恢复节点使得n皇后问题的计算更加高效。

       算法（2）的优雅之处就在于我们仅仅知道x的值就可以恢复（1）的操作。通常来说要恢复操作，需要我们记录下节点的左指针和它先前的值（请参阅[11];或[25],268-284页）。但是在这个实例中，我们只需要知道x的值，而回溯程序在做通常的操作时恰恰又很容易得到节点的值。

       我们可以把（1）、（2）这对操作应用于涉及到大量操作的复杂数据结构的双向链上。

       这个过程使得指针在数据结构内部灵活运用，仿佛设计精巧的舞蹈动作。因此，我很愿意把（1）、（2）这个技巧叫做Dancing Links（舞蹈链）。

完美覆盖问题。一个可以显示Dancing Links的威力的例子便是完美覆盖问题：给定一个0、1矩阵。问是否存在一个行的集合，使得该集合中恰好每列只含有一个1?

       例如下列矩阵（3）

请注意行集合{1，4，5}。我们可以认为该集合的1覆盖所有列，并且没有重复列出现1。我们也可以这样阐述：使用不相邻子集覆盖全集。或者说：如果行是全集的元素，列是全集的子集；那么，该问题便是找到一组元素使得每个子集恰好被覆盖1次。无论作何解释，该问题从本质上来讲都不是很容易，它是NP-complete，即使每行只含有3个1 [13,page 221]。这个问题让人很自然的会考虑用到回溯法。

       1958年，当Dana Scott作为普林斯顿大学一名研究生时，在Hale F. Trotter的帮助下在IAS "MANIAC" 机器上首次实现12片5格骨牌的拼图问题的回溯解法。12片5格骨牌拼图要求把12片骨牌放入正方形棋盘，并且中间留有2x2的空格。他的程序首次产生了所摆放的可能性。例如65种解其中一种如下图所示：

       这个问题是完美覆盖问题的一个特例。我们想象一个有72列的矩阵\
...

未翻译完
...