& quot;精确保护&"维基百科的详细示例，有关最后一步的问题 [英] "Exact Cover" Wikipedia detailed example, question about the very last step

问题描述

我正在跟踪Wikipedia上的一个很好的例子，该例子解决了简单的精确覆盖"问题.使用Knuth的跳舞链接"的问题DLX算法-示例在此处: https://en.wikipedia.org/wiki/Knuth％27s_Algorithm_X#Example

I'm following the great Wikipedia example of solving a simple "Exact Cover" problem using Knuth's "Dancing Links" DLX algorithm - example is here: https://en.wikipedia.org/wiki/Knuth%27s_Algorithm_X#Example

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

On the VERY LAST STEP they show the reduced matrix:

  2 3 5 6
D 0 1 1 1

他们说这是一个失败的解决方案，但是我们究竟怎么知道呢?是下降到一行，还是一行?还是最左边的列为0，最右边的3列为1?还是下降到1行，而该行完全不是1行?

They state that this is a failed solution, but exactly how do we know that? Is it that it's down to one row, any single row? Or is it that the leftmost column has 0 and the right 3 columns have 1's? Or maybe it's down to 1 row and that row is not ENTIRELY 1's ?

真正地试图理解所有这些东西(即使我可以从网络上下载解决方案，但最终还是要与Pentominoes一起使用，但是我想自己编写代码以便娱乐和学习)

Really trying to understand all this stuff (to eventually use with Pentominoes, even though I can download solutions from the web, but I want to code it myself for recreation and learning)

推荐答案

如果存在未覆盖的X列，而该列X剩余零行可以覆盖它，则我们声明失败.在具有最少剩余行数的列上进行分支的标准使该列的存在易于检测，而无需太多特殊逻辑.

We declare failure if there exists an uncovered column X for which there are zero rows remaining that would cover it. The criterion of branching on the column with the least remaining rows that would cover it makes the existence of such a column easy to detect without much special logic.

这篇关于& quot;精确保护&"维基百科的详细示例，有关最后一步的问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！