"Exact Cover" 维基百科详细示例,关于最后一步的问题



我正在遵循维基百科的伟大示例,使用高德纳的"跳舞链接"DLX算法解决一个简单的"精确封面"问题 - 示例在这里: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 一起使用,即使我可以从网上下载解决方案,但我想自己编写代码以供娱乐和学习(

如果存在未覆盖的列 X,并且剩余的行数为零,则声明失败。在具有最少剩余行的列上进行分支的标准使得这种列的存在很容易检测到,而无需太多特殊的逻辑。

相关内容

  • 没有找到相关文章

最新更新