我已经实现了Knuth's "Dancing Links" algorithm来探索广义精确覆盖问题（即，使用第二列）。对于精确覆盖（即所有列都是主列）和简单稀疏矩阵，代码的工作方式与预期一致：
[0, 1, 0]
[0, 0, 1]
[1, 0, 0]
[1, 1, 0]
[0, 1, 1]
[1, 1, 1]
我的代码返回以下行集作为解决方案：
[0, 1, 2]
[1, 3]
[2, 4]
[5]
我也用许多其他精确的封面例子来测试过这个，结果证明了这一点但是，关于第二列的细节有点模糊。从我从各种资源中收集到的信息来看，你需要做的是：
唯一的区别是我们通过
仅用于主要列的列标题的循环列表。每个的标题
第二列应该有简单指向自身的L和R字段其余的
算法的进程和以前一样，所以我们仍然称它为算法dlx。
在对矩阵/节点/头的表示方式进行这些更改，然后将第一列设置为第二列（即，只有第2列和第3列是主列）之后，我最终得到了以下几组行作为解决方案：
[0, 1]
[1, 3]
[4]
[5]
虽然所有这些都是有效解，有些与精确覆盖解重叠，但似乎缺少其他解（即，来自精确覆盖解集的一些解）：
[0, 1, 2]
[2, 4]
也许这是我的误解，但我是在概念上遗漏了什么，还是克努特的解释不完整？
如果你能证明你的算法产生了完整的解集，这将有助于我确认我的算法是不完整的！
不幸的是，即使是关于舞蹈链接的Knuth似乎也没有提供太多帮助。
最佳答案
定义
这就是如何将精确的封面问题扩展到Pre-Fascicle 5C的第7页（当前）上的非主要项目，舞蹈链接：
…一个精确的覆盖问题涉及N个不同的项，其中N1是主要项，N2=N-N1是次要项它由一系列选项定义，每个选项都是项的子集。每个选项必须至少包含一个主项任务是找到所有选项的子集，这些选项（i）恰好包含每个主项一个，并且（ii）最多一次包含每个辅助项。
（纯次要的选项被排除在这个新定义之外，因为在我们对其进行了改进之后，算法x永远不会选择它们。如果出于某种原因你不喜欢这条规则，你总是可以回到松弛选项的想法。练习19讨论了另一个有趣的选择。）
你的问题由第一段中的强调句（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，在名为（比如）的文件中输入以下内容：
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.
（请注意第二个程序中的明确警告，将忽略仅包含辅助项A的选项2。）
解决方案1：改变问题
如果删除不包含主项（列）的选项（行），则程序已经工作：您得到的解决方案确实是针对新问题的详尽无遗的。
解决方案2：松弛选项
正如Knuth在引用的第二段中所说（忽略练习19的备选方案；它是为了解决另一个问题），如果你真的想包含只包含次要项的选项，你可以回到松弛选项的概念在2000年的论文中，这是你引用的段落后面的下一句话：
一个广义覆盖问题可以转化为一个等价的精确覆盖问题，只要我们为每一个二级列附加一行，在该列中包含一个1。
（也就是说，对于每个次要项，我们添加一个仅包含该项的选项，现在将其视为仅包含主要项的完全覆盖问题。）
更详细地说，我假设您希望解决以下问题：
有n个不同的项（列），其中一些是主项，另一些是辅助项。
有一些选项（行）系列，每个选项（行）都是一组项（列）。其中一些可能不包含主项。
只需一次查找包含每个主项的所有选项子集，最多一次查找包含每个辅助项的所有选项子集。
要解决这个问题，我们可以做以下几点：
在给定的选项（行）中，标识那些只包含辅助项（列）的选项。因此，取给定的所有行的集合，并将其分为两个集合：一个集合（称为X），其中每个选项至少包含一个主项；另一个集合（称为Y），其中每个选项仅包含辅助项。
对于每个次要项，形成仅包含该项的选项（行）设Z为所有此类一项（松弛）选项的集合。
现在，将选项列表（X+Y）替换为（X+Y+Z），其中+是并集：Y和Z之间可能有一些重叠，但每个选项只保留一个。
最后，解决原始的精确覆盖问题（其中所有选项都是主要选项）。你会得到一些解决方案。
对于你得到的每一个解决方案，
首先扔掉（忽略）不在x或y中的每个选项（即，是您添加的松弛选项之一）
在剩余的选项中，在解决方案中形成仅包含辅助项的选项集Y'。设x'为剩余集合（即解决方案中至少包含一个主项的选项）。
为y'的每个子集追加解（x'并）。
在问题中的示例中：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]。
这给出了所有六种解决方案。