Knuth 与二级专栏的舞蹈链接
Knuth Dancing Links with Secondary Columns
我已经实施 Knuth's "Dancing Links" algorithm 来探索广义精确覆盖问题（即，使用辅助列）。对于精确覆盖（即所有列都是主列），代码按预期工作，对于简单的稀疏矩阵也是如此：
[0, 1, 0]
[0, 0, 1]
[1, 0, 0]
[1, 1, 0]
[0, 1, 1]
[1, 1, 1]
我的代码returns下面的一组行作为解决方案：
[0, 1, 2]
[1, 3]
[2, 4]
[5]
而且我还用许多其他确切的封面示例对此进行了测试，并通过了验证。但是，有关辅助列的详细信息有点模糊。根据我从各种 Knuth/non-Knuth 资源中收集到的信息，它说您需要做的是：
The only difference is that we initialize the data structure by making
a circular list of the column headers for the primary columns only. The header for each
secondary column should have L and R fields that simply point to itself. The remainder
of the algorithm proceeds exactly as before, so we will still call it algorithm DLX.
对 matrix/nodes/headers 的表示方式进行这些更改，然后将第一列设置为辅助列（即，只有第 2 列和第 3 列是主要列）后，我最终得到以下几组行作为解决方案：
[0, 1]
[1, 3]
[4]
[5]
虽然所有这些都是有效的解决方案并且有些与精确覆盖解决方案重叠，但似乎缺少其他解决方案（即，其中一些来自精确覆盖解决方案集）：
[0, 1, 2]
[2, 4]
也许这是我的误解，但我是不是在概念上遗漏了什么，还是 Knuth 的解释不完整？
如果你能证明你的算法产生了完整的解决方案集甚至会很有帮助，这将帮助我确认我的算法是不完整的！
不幸的是，即使 Knuth's "Art of Computer Programming" 关于舞蹈链接似乎也没有提供太多帮助。
定义
Pre-Fascicle 5C，Dancing Links：
第 7 页（当前）上的确切封面问题是如何扩展到非主要项目的
...an exact cover problem involves N distinct items, of which N1 are primary and N2 = N - N1 are secondary. It is defined by a family of options, each of which is a subset of the items. Every option must include at least one primary item. The task is to find all subsets of the options that (i) contain every primary item exactly one, and (ii) contain every secondary item at most once.
(Options that are purely secondary are excluded from this new definition, because they will never be chosen by Algorithm X as we've refined it. If for some reason you don't like that rule, you can always go back to the idea of slack options. Exercise 19 discusses another interesting alternative.)
第一段和第二段中强调的（Knuth）句子回答了您的问题。 Knuth 解决的确切覆盖问题不允许（或忽略）无助于覆盖主要项目的选项，即纯粹由次要项目组成。
例子
在您的问题示例中，我们将列称为 A、B、C，其中 A 是次要列，B 和 C 是主要列。选项是：
[0, 1, 0] -- option 0: [B]
[0, 0, 1] -- option 1: [C]
[1, 0, 0] -- option 2: [A]
[1, 1, 0] -- option 3: [A, B]
[0, 1, 1] -- option 4: [B, C]
[1, 1, 1] -- option 5: [A, B, C]
所以这里第三行 [1 0 0]，即选项 2，不包含主要项目。
您可以 运行 Knuth 的程序 DANCE 或 DLX1 中的任何一个，在名为（例如）foo.dlx:
的文件中输入以下内容
B C | A
B
C
A
A B
B C
A B C
程序找到相同的四个解决方案：
$ ./dance 1 < foo.dlx
1:
C (1 of 3)
B (1 of 2)
2:
C (1 of 3)
B A (2 of 2)
3:
C B (2 of 3)
4:
C A B (3 of 3)
Altogether 4 solutions, after 12 updates.
或
% ./dlx1 m1 < foo.dlx
Option ignored (no primary items): A
(5 options, 2+1 items, 14 entries successfully read)
1:
C (1 of 3)
B (1 of 2)
2:
C (1 of 3)
B A (2 of 2)
3:
C B (2 of 3)
4:
C A B (3 of 3)
Altogether 4 solutions, 261+231 mems, 12 updates, 360 bytes, 6 nodes.
（注意第二个程序中的明确警告，选项 2 仅包含次要项目 A，将被忽略。）
解决方案 1：更改问题
如果您删除不包含主要项目（列）的选项（行），那么该程序已经可以运行：您获得的解决方案对于新问题确实是详尽无遗的。
解决方案 2：Slack 选项
正如 Knuth 在引用的第二段中所说（忽略练习 19 的备选方案；它用于解决不同的问题），如果您真的想要包含仅包含次要项目的选项，您可以回到 slack 的想法选项。在 2000 年的论文中，这个想法是您引用的段落之后的下一句话：
A generalized cover problem can be converted to an equivalent exact cover problem if we simply append one row for each secondary column, containing a single 1 in that column.
（即，对于每个次要项，我们添加一个仅包含该项的选项，现在将其视为仅包含主要项的精确覆盖问题。）
更详细地说，我假设您想解决以下问题：
有 N 个不同的项目（列），其中一些是主要的，另一些是次要的。
有一些选项族（行），每个选项都是一组项目（列）。 其中一些可能不包含主要项目。
查找包含每个主要项目恰好一次且每个次要项目最多一次的选项的所有子集。
要解决这个问题，我们可以这样做：
在给定的选项（行）中，找出仅包含次要项目（列）的选项。因此，您将给出的所有行的集合分成两组：一组（称为 X），其中每个选项至少包含一个主要项目，另一组（称为 Y），其中每个选项仅包含次要项目。
对于每个次要项目，形成仅包含该项目的选项（行）。设 Z 为所有此类单项（松弛）选项的集合。
现在，将您的选项列表 (X + Y) 替换为 (X + Y + Z)，其中 + 是并集：Y 和 Z 之间可能有一些重叠，但您我将只保留每个选项中的一个。
最后解决原来的精确覆盖问题（所有选项都是主要的）。你会得到一些解决方案。
对于您获得的每个解决方案，
首先丢弃（忽略）不在 X 或 Y 中的每个选项（即，是您另外添加的松弛选项之一）
余下的选项，构成方案中仅包含次要项的选项集合Y'。令 X' 为剩余集合（即解决方案中至少包含一个主要项目的选项）。
为 Y' 的每个子集附加解决方案（X' 并集 S）。
在问题中的示例中：X 是以下集合：
[0, 1, 0] -- option 0: [B]
[0, 0, 1] -- option 1: [C]
[1, 1, 0] -- option 3: [A, B]
[0, 1, 1] -- option 4: [B, C]
[1, 1, 1] -- option 5: [A, B, C]
Y是下面的集合：
[1, 0, 0] -- option 2: [A]
Z和Y一样，所以在这种情况下你不需要添加任何东西。
你解决了原来的精确覆盖问题（一切都是初级的），得到如下解法：
[0, 1, 2]。这里 X' = [0, 1]，Y' = [2] 并且有两个子集：空集 ([]) 和 Y 本身 ([2])。所以添加两个解决方案 [0, 1] 和 [0, 1, 2].
[1, 3]。这里 X' = [1, 3] 和 Y' = []。添加解决方案 [1, 3].
[2, 4]。这里 X' = [4]，Y' = [2]。添加两个解决方案 [4] 和 [2, 4].
[5]。这里 X' = [5]，Y' = []。添加解决方案 [5].
这给出了所有六个解决方案。
我已经实施 Knuth's "Dancing Links" algorithm 来探索广义精确覆盖问题（即，使用辅助列）。对于精确覆盖（即所有列都是主列），代码按预期工作，对于简单的稀疏矩阵也是如此：
[0, 1, 0]
[0, 0, 1]
[1, 0, 0]
[1, 1, 0]
[0, 1, 1]
[1, 1, 1]
我的代码returns下面的一组行作为解决方案：
[0, 1, 2]
[1, 3]
[2, 4]
[5]
而且我还用许多其他确切的封面示例对此进行了测试，并通过了验证。但是，有关辅助列的详细信息有点模糊。根据我从各种 Knuth/non-Knuth 资源中收集到的信息，它说您需要做的是：
The only difference is that we initialize the data structure by making a circular list of the column headers for the primary columns only. The header for each secondary column should have L and R fields that simply point to itself. The remainder of the algorithm proceeds exactly as before, so we will still call it algorithm DLX.
对 matrix/nodes/headers 的表示方式进行这些更改，然后将第一列设置为辅助列（即，只有第 2 列和第 3 列是主要列）后，我最终得到以下几组行作为解决方案：
[0, 1]
[1, 3]
[4]
[5]
虽然所有这些都是有效的解决方案并且有些与精确覆盖解决方案重叠，但似乎缺少其他解决方案（即，其中一些来自精确覆盖解决方案集）：
[0, 1, 2]
[2, 4]
也许这是我的误解，但我是不是在概念上遗漏了什么，还是 Knuth 的解释不完整？
如果你能证明你的算法产生了完整的解决方案集甚至会很有帮助，这将帮助我确认我的算法是不完整的！
不幸的是，即使 Knuth's "Art of Computer Programming" 关于舞蹈链接似乎也没有提供太多帮助。
定义
Pre-Fascicle 5C，Dancing Links：
第 7 页（当前）上的确切封面问题是如何扩展到非主要项目的...an exact cover problem involves N distinct items, of which N1 are primary and N2 = N - N1 are secondary. It is defined by a family of options, each of which is a subset of the items. Every option must include at least one primary item. The task is to find all subsets of the options that (i) contain every primary item exactly one, and (ii) contain every secondary item at most once.
(Options that are purely secondary are excluded from this new definition, because they will never be chosen by Algorithm X as we've refined it. If for some reason you don't like that rule, you can always go back to the idea of slack options. Exercise 19 discusses another interesting alternative.)
第一段和第二段中强调的（Knuth）句子回答了您的问题。 Knuth 解决的确切覆盖问题不允许（或忽略）无助于覆盖主要项目的选项，即纯粹由次要项目组成。
例子
在您的问题示例中，我们将列称为 A、B、C，其中 A 是次要列，B 和 C 是主要列。选项是：
[0, 1, 0] -- option 0: [B]
[0, 0, 1] -- option 1: [C]
[1, 0, 0] -- option 2: [A]
[1, 1, 0] -- option 3: [A, B]
[0, 1, 1] -- option 4: [B, C]
[1, 1, 1] -- option 5: [A, B, C]
所以这里第三行 [1 0 0]，即选项 2，不包含主要项目。
您可以 运行 Knuth 的程序 DANCE 或 DLX1 中的任何一个，在名为（例如）foo.dlx:
B C | A
B
C
A
A B
B C
A B C
程序找到相同的四个解决方案：
$ ./dance 1 < foo.dlx
1:
C (1 of 3)
B (1 of 2)
2:
C (1 of 3)
B A (2 of 2)
3:
C B (2 of 3)
4:
C A B (3 of 3)
Altogether 4 solutions, after 12 updates.
或
% ./dlx1 m1 < foo.dlx
Option ignored (no primary items): A
(5 options, 2+1 items, 14 entries successfully read)
1:
C (1 of 3)
B (1 of 2)
2:
C (1 of 3)
B A (2 of 2)
3:
C B (2 of 3)
4:
C A B (3 of 3)
Altogether 4 solutions, 261+231 mems, 12 updates, 360 bytes, 6 nodes.
（注意第二个程序中的明确警告，选项 2 仅包含次要项目 A，将被忽略。）
解决方案 1：更改问题
如果您删除不包含主要项目（列）的选项（行），那么该程序已经可以运行：您获得的解决方案对于新问题确实是详尽无遗的。
解决方案 2：Slack 选项
正如 Knuth 在引用的第二段中所说（忽略练习 19 的备选方案；它用于解决不同的问题），如果您真的想要包含仅包含次要项目的选项，您可以回到 slack 的想法选项。在 2000 年的论文中，这个想法是您引用的段落之后的下一句话：
A generalized cover problem can be converted to an equivalent exact cover problem if we simply append one row for each secondary column, containing a single 1 in that column.
（即，对于每个次要项，我们添加一个仅包含该项的选项，现在将其视为仅包含主要项的精确覆盖问题。）
更详细地说，我假设您想解决以下问题：
有 N 个不同的项目（列），其中一些是主要的，另一些是次要的。
有一些选项族（行），每个选项都是一组项目（列）。 其中一些可能不包含主要项目。
查找包含每个主要项目恰好一次且每个次要项目最多一次的选项的所有子集。
要解决这个问题，我们可以这样做：
在给定的选项（行）中，找出仅包含次要项目（列）的选项。因此，您将给出的所有行的集合分成两组：一组（称为 X），其中每个选项至少包含一个主要项目，另一组（称为 Y），其中每个选项仅包含次要项目。
对于每个次要项目，形成仅包含该项目的选项（行）。设 Z 为所有此类单项（松弛）选项的集合。
现在，将您的选项列表 (X + Y) 替换为 (X + Y + Z)，其中 + 是并集：Y 和 Z 之间可能有一些重叠，但您我将只保留每个选项中的一个。
最后解决原来的精确覆盖问题（所有选项都是主要的）。你会得到一些解决方案。
对于您获得的每个解决方案，
首先丢弃（忽略）不在 X 或 Y 中的每个选项（即，是您另外添加的松弛选项之一）
余下的选项，构成方案中仅包含次要项的选项集合Y'。令 X' 为剩余集合（即解决方案中至少包含一个主要项目的选项）。
为 Y' 的每个子集附加解决方案（X' 并集 S）。
在问题中的示例中：X 是以下集合：
[0, 1, 0] -- option 0: [B]
[0, 0, 1] -- option 1: [C]
[1, 1, 0] -- option 3: [A, B]
[0, 1, 1] -- option 4: [B, C]
[1, 1, 1] -- option 5: [A, B, C]
Y是下面的集合：
[1, 0, 0] -- option 2: [A]
Z和Y一样，所以在这种情况下你不需要添加任何东西。
你解决了原来的精确覆盖问题（一切都是初级的），得到如下解法：
[0, 1, 2]。这里 X' = [0, 1]，Y' = [2] 并且有两个子集：空集 ([]) 和 Y 本身 ([2])。所以添加两个解决方案 [0, 1] 和 [0, 1, 2].
[1, 3]。这里 X' = [1, 3] 和 Y' = []。添加解决方案 [1, 3].
[2, 4]。这里 X' = [4]，Y' = [2]。添加两个解决方案 [4] 和 [2, 4].
[5]。这里 X' = [5]，Y' = []。添加解决方案 [5].
这给出了所有六个解决方案。