algorithm - “Exact Cover”维基百科详细示例，关于最后一步的问题

Question

我正在关注使用 Knuth 的“Dancing Links”DLX 算法解决简单“精确封面”问题的 Wikipedia 示例 - 示例在这里：https ://en.wikipedia.org/wiki/Knuth%27s_Algorithm_X#Example

在最后一步，他们显示了简化的矩阵：

  2 3 5 6
D 0 1 1 1

他们说这是一个失败的解决方案，但我们到底是怎么知道的呢？是不是只有一行，任何一行？还是最左边的列有 0 而右边的 3 列有 1？或者也许它下降到 1 行并且该行不是完全 1 的？

真的试图理解所有这些东西（最终与 Pentominoes 一起使用，即使我可以从网上下载解决方案，但我想自己编写代码以供娱乐和学习）

Answer 1

如果存在未覆盖的列 X 并且剩余零行可以覆盖它，我们声明失败。对覆盖它的剩余行最少的列进行分支的标准使得这种列的存在很容易检测，而无需太多特殊逻辑。