C++ Dancing Links 算法 (DLX)

解决精确覆盖问题的一种良好且高效的方法是**_舞蹈链算法_**或**_DLX_**。该过程要求您从集合中选择子集，以便通用集中的每个元素都被精确覆盖一次。同样，就像约束满足问题、铺砖问题和谜题求解一样，这些问题以多种形式出现在计算机科学、数学和人工智能的各个领域。精确覆盖问题最著名的应用可能是在数独游戏中：您必须在每个行、列和子网格中用数字 1 到 9 填充整个网格，并且每个数字只能出现一次。

Donald Knuth 的算法需要一个递归的、非确定性的回溯算法来解决这些问题，一个极其优化的版本名为 DLX。DLX 与其前身 Algorithm X 的不同之处在于，它利用了一种称为舞蹈链的高级数据结构，该数据结构允许在回溯过程中高效地移除和重新插入元素。该算法的名称指的是元素在暂时移除时“跳舞”回到原位，从而有利于在解决方案空间中快速探索。

理解 DLX 算法的上下文将基于对精确覆盖问题的基本理解以及它们需要满足的约束。此外，它还暗示了理解舞蹈链如何操作矩阵以确保导出解决方案，以及如何使用稀疏矩阵表示这些问题。这些概念涉及对精确覆盖问题、Algorithm X 以及 DLX 如何使用舞蹈链方法扩展该方法的基本了解。

精确覆盖问题：原型障碍

要理解 DLX，我们必须首先定义什么是精确覆盖问题。这种形式的问题采用一个元素为二进制（0 和 1）的矩阵，任务是选择一个行子集，以便每个列只有一个“1”。这意味着必须选择包含每个列的“1”的行——这将“覆盖”该列。

从一个更大的集合中找到一个子集族，使得通用集的每个元素都只包含在一个子集中，这相当于有效地解决了精确覆盖问题。这是基本的计算问题之一，在组合优化和问题解决领域有许多应用。

让我们考虑以下矩阵，它表示一个精确覆盖问题

在这种情况下，目标是选择一个条目子矩阵，使得每个列恰好包含一个“1”。一种可能的方法是选择行 {1, 4, 5}，它们精确覆盖每个列一次。DLX 正在寻找这种子集，因为它本身将代表精确覆盖问题的难点。

舞蹈链算法：循环双向链表

舞蹈链 (DLX) 算法中一个关键的数据结构，它有助于有效移除和恢复元素，是一个循环双向链表。该算法以最小的计算开销执行回溯的能力依赖于这种独特的链表。在完全掌握循环双向链表在 DLX 中的作用之前，理解它的功能以及它为何如此擅长解决精确覆盖问题至关重要。这种形式的问题采用一个元素为二进制（0 和 1）的矩阵，任务是选择一个行子集，以便每个列只有一个“1”。这意味着必须选择包含每个列的“1”的行——这将“覆盖”该列。

循环双向链表的组成

传统双向链表中的每个节点都有两个指针，一个指向序列中的前一个节点，另一个指向下一个节点，以及数据。这使得可以向前和向后遍历列表。另一方面，循环双向链表创建一个循环，其中序列中的最后一个节点链接回第一个节点，最后一个节点连接到第一个节点的前一个指针。由于其循环特性，您可以循环遍历整个列表而不会遇到边界或空引用。

例如，具有节点 A、B 和 C 的双向链表中的指针将按如下方式组织

• 节点 A 的前一个指针指向 C，下一个指针指向 B。
• 节点 B 的前一个指针指向 A，下一个指针指向 C。
• 节点 C 的前一个指针指向 B，下一个指针指向 A。
• 这种循环结构使得节点可以高效地添加、移除和恢复，这对于 DLX 的回溯过程至关重要。

循环双向链表在 DLX 中的功能

舞蹈链算法使用这种数据结构来表示稀疏矩阵，这是一种解决精确覆盖问题的流行格式。潜在的解决方案由矩阵的行表示，而约束（例如确保每个元素都被精确覆盖一次）由列表示。

DLX 中使用循环双向链表来表示矩阵，其中每个节点表示矩阵中的一个“1”。每个节点有四个连接方向：左、右、上、下。矩阵由垂直链接的列和水平链接的行组成。为了简化列的遍历，列还链接到头部节点，这些头部节点是其自身循环双向链表的一部分。

这表明矩阵中的每个节点都是垂直和水平循环双向链表的成员。在 DLX 中，这些指针的功能如下

• 左右指针通过将节点连接到同一行中的其他节点来实现水平矩阵遍历。
• 上下指针：这些通过将节点连接到同一列中的其他节点来实现垂直导航。

元素的有效移除和恢复

DLX 使用循环双向链表的主要原因是在搜索过程中它们移除和恢复元素的效率。在典型矩阵形式中移除行或列（即覆盖或取消覆盖约束）通常涉及大量数据移动。另一方面，在循环双向链表中消除节点（从而消除行或列）要容易得多。

当 DLX“覆盖”一列时，该列以及选项列表中所有包含“1”的行都将被消除。算法通过简单地更改附近节点的指针来避免被消除的节点。由于需要修改的指针很少，因此取消链接过程非常快。通过重新链接节点，可以“取消覆盖”移除的列和行，并将矩阵恢复到其原始状态。

节点移除的示例

在 DLX 中，必须将其列头部节点与其邻居断开连接以覆盖列。让我们举一个例子，我们有一个包含节点 A、B 和 C 的循环双向链表。我们想要移除节点 B。该过程继续如下

• 节点 A 的下一个指针更改为指向节点 C。
• 节点 C 的前一个指针更改为指向节点 A。
• 节点 B 现在从列表中移除。但节点 B 仍然完好无损，因此稍后要恢复它，只需反转指针修改即可。
• 这种有效的矩阵操作对于 DLX 的回溯至关重要，因为它使其能够在不产生大量处理开销的情况下探索替代场景。

循环双向链表对 DLX 的好处 快速移除和恢复 添加和恢复节点的简单性是利用循环双向链表的主要好处。由于 DLX 算法能够快速覆盖和取消覆盖列，因此回溯非常有效。

• **最小内存开销：** DLX 消除了重新定位或复制矩阵大部分的需求，节省了内存并提高了效率，因为在覆盖/取消覆盖操作期间只需更新指针。
• **双向遍历：** 由于循环双向链表提供向前和向后遍历，DLX 可以轻松调查多个选项并在回溯时返回到早期状态。

舞蹈链方法中的一个关键数据结构是循环双向链表，它提供了解决精确覆盖问题所需的速度，通过回溯。DLX 因其快速移除和恢复节点而非常适合解决组合难题，如数独、聚氨酯铺砖和其他约束满足问题，从而保证对可行解决方案的最佳探索。

算法 X：一种回溯技术

Donald Knuth 于 2000 年发表了他的递归、非确定性、深度优先搜索算法 X。该算法的目的是系统地精确覆盖问题并测试可能的解决方案。它按照以下方式工作

在这种情况下，目标是选择一个条目子矩阵，使得每个列恰好包含一个“1”。一种可能的方法是选择行 {1, 4, 5}，它们精确覆盖每个列一次。DLX 正在寻找这种子集，因为它本身将代表精确覆盖问题的难点。

Donald Knuth 于 2000 年发表了他的递归、非确定性、深度优先搜索算法 Algorithm X。该算法的目的是系统地精确覆盖问题并测试可能的解决方案。它按照以下方式工作

舞蹈链：天才的构想

舞蹈链技术赋予了 DLX 非凡的力量。基本上，它是一种表达和处理精确覆盖问题所依赖的稀疏矩阵的方法。在传统矩阵格式下，通常擦除一行或一列需要大量时间。通过将矩阵表示为循环双向链表，舞蹈链提高了这种操作的效率。

矩阵中的每个节点都有四个方向的连接，即左、右、上、下。矩阵中的每个节点都与原始二进制矩阵中的一个“1”相关联。除了这些连接到“1”的节点外，矩阵的每个列都有一个头部节点，它们之间通过循环双向链表连接。然后可以重新链接相关节点，以生成一个稀疏矩阵，该矩阵可以轻松生成用于移除和恢复的行和列。

舞蹈链的巧妙之处在于它允许轻松地“覆盖”和“取消覆盖”行和列。如果一列被覆盖，它会从开放列列表中移除；如果被取消覆盖，则将该列添加到开放列列表中。被覆盖列中所有包含“1”的行也会被移除。回溯很快，因为节点可以立即重新链接以恢复原始结构。

DLX：基于舞蹈链的算法 X 优化

DLX 算法结合了算法 X 的搜索技术和舞蹈链的效率。这个想法非常简单：在算法 X 的回溯阶段，实际上是舞蹈链结构的行和列被覆盖和取消覆盖以执行。因此，DLX 可以在不增加数据操作开销的情况下真正搜索潜在的解决方案。

DLX 的另一个好处是它与稀疏矩阵配合得非常好，这在许多精确覆盖问题中很常见：由于稀疏矩阵包含大量的“0”和少量的“1”，该技术一次只需更改矩阵的一小部分。因此，DLX 是处理复杂、大规模问题的非常强大的工具。

C++ 中的 DLX 算法

在 DLX 中，矩阵中的每个节点都表示为一个结构体，整个矩阵是链接节点的集合。每个节点都包含指向其四个方向（左、右、上、下）邻居的指针，以及对其所属列的引用。

每个列还有一个头部节点，它跟踪该列中存在的节点（1s）数量。头部节点以循环双向链表的形式连接，允许高效遍历矩阵。

覆盖和取消覆盖列

覆盖列涉及将其从头部列表中移除，并取消链接该列中包含“1”的所有行。这是通过遍历该列并从其相应行中移除节点来实现的。反向过程称为取消覆盖，其中节点被重新链接到矩阵中。

解决精确覆盖

DLX 算法通过递归覆盖列、选择行并在必要时回溯来解决精确覆盖问题。以下是算法的核心

舞蹈链算法使我们能够使用 Donald Knuth 的算法 X 以非常有效的方式解决精确覆盖问题，利用强大的循环双向链表来表示问题矩阵，从而非常快速地进行大量回溯。DLX 特别适合处理大型稀疏问题。算法 X 的优势和舞蹈链的效率使 DLX 在从约束满足到组合优化的许多问题领域中得以建立。

Donald Knuth 的舞蹈链算法是算法 X 的改进，在各种计算机科学领域都有惊人的应用。它为解决精确覆盖问题而开发的方法使得可以在约束满足、组合优化和娱乐数学中使用这些问题。DLX 最著名的用途是解决数独谜题，但它也可以应用于解决矩阵操作和多边形铺砖困难，甚至背包问题。下一节将概述 DLX 的几个实际应用以及其构造和效率如何帮助解决此类难题。

应用

1. 解决数独

DLX 最著名的应用可能是解决基于逻辑的数字放置谜题数独。著名的数独谜题的目标是在 9x9 的网格中填充 1 到 9 的数字，而不会在任何行、列或 3x3 子网格（通常称为盒子）中重复任何一个数字。

数独谜题甚至可以被视为精确覆盖问题。在数独问题中，有一些必须满足的要求，DLX 非常擅长处理这些要求：每个单元格中应该只有一个整数。

• 每行中的每个数字都应该只出现一次。
• 每列中的每个数字都应该只出现一次。
• 每个 3x3 盒子中每个数字只能包含一个整数。

要应用 DLX，我们必须首先构建一个约束矩阵。在这里，矩阵的每一行对应于单元格中数字的可用位置，矩阵的每一列对应于包含数字的约束行、列或盒子。然后，DLX 算法通过选择精确满足覆盖标准的行（即数字放置）来实际解决谜题。

使用 DLX 解决数独的方法

通过以下方式创建矩阵：将数独谜题表示为布尔值矩阵。一行可以被视为数字在网格中的每个可能位置，列表示约束，例如数字在一行、一列或一个盒子中。

• **应用 DLX：** 我们通过 DLX 方法寻找矩阵的精确覆盖，以满足所有约束。
• **解释解决方案：** DLX 返回的解决方案对应于有效的数独配置。它选择的每一行都代表在特定单元格中填充特定数字。

由于 DLX 针对精确覆盖问题进行了优化，而数独就是其中之一，因此它在解决数独谜题方面效率很高。在处理复杂和大规模数独谜题的最佳算法中，DLX 排名很高，因为它针对解决方案空间中的行和列的快速移除和恢复进行了优化。

2. 拼图覆盖

DLX 的另一个有趣应用是拼图覆盖问题。拼图由边到边连接的正方形组成。目标是使用一组拼图覆盖某个给定区域（例如矩形或不规则形状），而没有间隙或重叠。

覆盖问题可以表述为精确覆盖问题，其中目标区域中的每个位置都等同于矩阵中的一列，每个拼图都等同于矩阵中的一行。目标区域中的每个单元格都应该被一个拼图精确覆盖一次。这被称为精确覆盖要求。

五格拼图

假设我们希望用一个多米诺骨牌填充两个额外的方块和十二个五格拼图（由五个连接的方块组成的形状）来覆盖一个 8x8 的棋盘。我们的问题是在没有间隙或重叠的情况下覆盖棋盘。

为 DLX 准备此问题

将棋盘上的一个位置视为每一列，将一个多边形的所有可能放置位置视为每一行。二进制矩阵表示某个多边形是否覆盖棋盘上的某个点。

• **使用 DLX：** DLX 算法找到满足精确覆盖要求的多边形位置排列。
• **解释解决方案：** 它会产生一个有效的铺砖配置，多米诺骨牌和多边形覆盖棋盘。

舞蹈链数据结构允许高效地执行这些放置可能性，这意味着 DLX 非常适合解决复杂的铺砖问题。

3. N 皇后问题

N 皇后问题是经典的组合问题，它包括在 NxN 棋盘上放置 N 个皇后，使得没有两个皇后可以相互攻击。本质上，没有两个皇后共享相同的对角线列或行。

这个问题也适用于 DLX 解决方案，因为它可以通过映射到精确覆盖问题来解决。在矩阵中，皇后的每个放置对应一行，所有约束——占据一行、占据一列和占据两个对角线——也都映射到列中。

如何将 DLX 应用于 N 皇后问题？

• **构建矩阵：** 每一行是皇后放置在自己的单元格中的过程，而列是将多个皇后放置在同一行、列或对角线中的过程。
• DLX 应用后，它会尝试找到满足精确覆盖条件的行（皇后放置）子集。
• 解释解决方案：该解决方案意味着在棋盘上找到一个可行的皇后放置。

4. 图论的精确覆盖

图论也通过使用 DLX 来解决哈密顿路径问题和图着色问题，其中相关问题通常与顶点或边的精确覆盖有关。

**图着色：** 这个问题为图的顶点着色，使得没有两个相邻的顶点具有相同的颜色。这个问题可以通过指定一个矩阵来表述为精确覆盖问题，其中行表示潜在的顶点颜色，列表示约束，即具有不同颜色的相邻顶点。此外，它还暗示了理解舞蹈链如何操作矩阵以确保导出解决方案，以及如何使用稀疏矩阵表示这些问题。这些概念涉及对精确覆盖问题、算法 X 以及 DLX 如何使用舞蹈链方法扩展该方法的基本了解。

图上的哈密顿路径是恰好遍历每个顶点一次的路径。通过将顶点和边重新视为矩阵中的行和列并确保每个顶点恰好访问一次，可以将此问题重新表述为精确覆盖问题。

5. 背包问题

DLX 在组合优化中的经典背包问题版本上很有用：选择一个子集以在背包限制内最大化价值。DLX 然后可以通过将物品选择问题重新表述为精确覆盖问题来搜索最优解决方案，其中行是物品的可行组合，列表示诸如重量限制之类的限制。将提供上下文，以理解 DLX 算法，基于对精确覆盖问题的基本理解以及它们需要满足的约束。

图论、铺砖谜题、数独和优化问题（包括背包问题）都使用了 DLX——舞蹈链算法——一种解决精确覆盖问题的灵活方法。这项工作的目的是描述最有效的算法之一，该算法通过稀疏矩阵操作进行回溯来处理困难的组合问题。通过利用 DLX 的固有结构，开发人员能够解决那些通过标准暴力方法解决起来计算成本高昂的问题。