python - Debug Exact Cover Pentominoes，维基百科示例不完整？或者...我误解了一些东西(包括代码)

Question

问题:
我已经以两种完全不同的方式为 Pentominoes 实现了 Knuth 的 DLX“dancing links”算法，但仍然得到不正确的解决方案。简单的 Wikipedia 示例工作正常( https://en.wikipedia.org/wiki/Knuth%27s_Algorithm_X#Example )，但更复杂的示例失败。
调试完整的 Pentominoes 游戏需要一个包含近 2,000 个条目的表，所以我想出了一个大大简化的谜题(如下图所示)，它仍然足够复杂以显示错误的行为。
下面是我的简单的 3x5 Pentominoes 示例，仅使用 3 块放置。我可以用笔和纸来完成算法，而且我的代码确实按照我告诉它的去做，但在第一步，它会破坏我的所有行!当我查看连通性时，这些列确实似乎没问题。很明显我误解了一些东西。
数据模型:
这是我试图让 DLX 解决的微不足道的解决方案:

下面是“移动”表，它编码了 3 个棋子可以进行的所有有效移动。 (我过滤掉一块会产生不能被 5 整除的孔大小的 Action )

左列是编码的移动，例如第一行是
一块“L”，放置在 0,0，然后旋转一个 90 度转弯
逆时针。

竖线 (|) 分隔符

前 3 列是我所指的选择器位。
由于“l”是第一部分(只有 3 个)，因此它在最左边的列中有一个 1。

接下来的 15 列对于 3x5 五联骨牌板上的每个点都是 1 位。

l_0,0_rr10|100111100001000000
l_0,1_rr10|100011110000100000
l_1,1_rr10|100000000111100001
l_0,0_rr01|100111101000000000
l_0,1_rr01|100011110100000000
l_1,0_rr01|100000001111010000
l_0,0_rr30|100100001111000000
l_1,0_rr30|100000001000011110
l_1,1_rr30|100000000100001111
l_0,1_rr01|100000010111100000
l_1,0_rr01|100000000001011110
l_1,1_rr01|100000000000101111
t_0,1_rr00|010011100010000100
t_0,0_rr10|010100001110010000
t_0,1_rr20|010001000010001110
t_0,2_rr30|010000010011100001
y_1,0_rr00|001000000100011110
y_1,1_rr00|001000000010001111
y_1,0_rr01|001000000100011110
y_1,1_rr01|001000000010001111
y_0,0_rr20|001111100010000000
y_0,1_rr20|001011110001000000
y_0,0_rr01|001111100100000000
y_0,1_rr01|001011110010000000

失败示例:
First Move 杀死了我数组的所有行(不考虑数字标题行和列)
按照前面引用的维基百科文章，我这样做:

查找列中设置的最小位数

4 是最小计数，第 2 列是设置了该位的最左边的列

我选择与第 2 列相交的第一行，即第 13 行。

第 4 列和第 13 行将添加到要“覆盖”(也称为删除)的列和行

现在我查看第 13 行并找到所有相交的列:2, 5, 6, 7, 11 & 16

现在我查看与这些列中的任何 1 相交的所有行 - 这似乎是有问题的步骤 - 该标准选择要删除的所有 24 个数据行。

由于板子是空的，系统认为它找到了一个有效的解决方案。

这是我的算法的纸笔版本的图片:

鉴于对代码的要求，我现在附上它。顶部的评论解释了在哪里看。
这是代码:
https://gist.github.com/ttennebkram/8bd27adece6fb3a5cd1bdb4ab9b51166
第二次测试
我想到了第二个 3x5 拼图，但它遇到了第一个示例的相同问题。作为记录，第二个 3x5 是:

# Tiny Set 2: 3x5
#   u u v v v
#   u p p p v
#   u u p p v

Answer 1

您在手动运行算法时看到的问题是没有行的矩阵不是解决方案。您需要消除所有列，仅消除行是失败的。您的示例运行仍有 12 列需要解决，因此它不成功。