调试 Exact Cover Pentominoes，维基百科示例不完整？或者...我误解了一些东西（包括代码）
Debug Exact Cover Pentominoes, Wikipedia example incomplete? OR... I'm misunderstanding something (includes code)
问题：
我已经以两种完全不同的方式为 Pentominoes 实现了 Knuth 的 DLX“跳舞链接”算法，但仍然得到不正确的解决方案。简单的维基百科示例工作正常 (https://en.wikipedia.org/wiki/Knuth%27s_Algorithm_X#Example)，但更复杂的示例失败。
调试完整的 Pentominoes 游戏需要 table 将近 2,000 个条目，所以我想出了一个大大减少的谜题（如下图所示），它仍然足够复杂以显示错误行为。
下面是我简单的 3x5 五联骨牌示例，仅使用 3 块来放置。我可以用笔和纸完成算法，并且可以肯定我的代码完全按照我告诉它的方式执行，但是在第一步中，它破坏了我所有的行！当我查看连通性时，这些列似乎确实没问题。很明显我误会了什么。
数据模型：
这是我试图让 DLX 解决的简单解决方案：
下面是“着法”table，它编码了 3 个棋子可以做出的所有有效着法。 （我过滤掉了一个棋子会产生一个不能被 5 整除的洞的动作）
- 左列是编码的着法，例如第一行是
件“L”，放置在 0,0，然后旋转一圈 90 度
counter-clockwise.
- 竖线 (|) 分隔符
- 前 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
失败示例：
第一步杀死我数组的所有行（忽略数字 header 行和列）
根据前面引用的维基百科文章，我这样做：
- 查找列中设置的最小位数
- 4 是最小计数，第 2 列是设置了该位的最左边的列
- 我选择与第 2 列相交的第一行，即第 13 行。
- 第 4 列和第 13 行将添加到要“覆盖”（也称为删除）的列和行中
- 现在我查看第 13 行并找到所有相交的列：2、5、6、7、11 和 16
- 现在我查看与任何这些列中的任何 1 相交的所有行 - 这似乎是有问题的步骤 - 该标准选择要删除的所有 24 个数据行。
- 由于棋盘是空的，系统认为它找到了一个有效的解决方案。
这是我的 pen-and-paper 算法版本的图片：
鉴于对代码的请求，我现在附上它。顶部的评论解释了在哪里看。
代码如下：
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
您亲手 运行 算法遇到的问题是没有行的矩阵不是解决方案。您需要删除所有 列 ，仅删除行是失败的。您的示例 运行 仍有 12 列需要解决，因此未成功。
对于缩小的实例，您的确切封面实现似乎没问题，但绘图仪坏了。我通过更改
修复了它
boardBitmap = fullBitmap[12:]
到
boardBitmap = fullBitmap[3:]
在plotMoveToBoard_np中，因为缩小后的实例只有三块。
编辑：还有一个关于如何生成移动名称的问题。有不同的同名动作。还有重复的动作（不影响正确性但会影响性能）。我变了
- g_rowNames.append(rowName)
+ g_rowNames.append(str(hash(str(finalBitmask))))
3x20 开始正常工作。 （这不是生成名称的好方法，因为理论上哈希值可能会发生冲突，但它是一行。）
问题：
我已经以两种完全不同的方式为 Pentominoes 实现了 Knuth 的 DLX“跳舞链接”算法，但仍然得到不正确的解决方案。简单的维基百科示例工作正常 (https://en.wikipedia.org/wiki/Knuth%27s_Algorithm_X#Example)，但更复杂的示例失败。
调试完整的 Pentominoes 游戏需要 table 将近 2,000 个条目，所以我想出了一个大大减少的谜题（如下图所示），它仍然足够复杂以显示错误行为。
下面是我简单的 3x5 五联骨牌示例，仅使用 3 块来放置。我可以用笔和纸完成算法，并且可以肯定我的代码完全按照我告诉它的方式执行，但是在第一步中，它破坏了我所有的行！当我查看连通性时，这些列似乎确实没问题。很明显我误会了什么。
数据模型：
这是我试图让 DLX 解决的简单解决方案：
下面是“着法”table，它编码了 3 个棋子可以做出的所有有效着法。 （我过滤掉了一个棋子会产生一个不能被 5 整除的洞的动作）
- 左列是编码的着法，例如第一行是 件“L”，放置在 0,0，然后旋转一圈 90 度 counter-clockwise.
- 竖线 (|) 分隔符
- 前 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
失败示例：
第一步杀死我数组的所有行（忽略数字 header 行和列）
根据前面引用的维基百科文章，我这样做：
- 查找列中设置的最小位数
- 4 是最小计数，第 2 列是设置了该位的最左边的列
- 我选择与第 2 列相交的第一行，即第 13 行。
- 第 4 列和第 13 行将添加到要“覆盖”（也称为删除）的列和行中
- 现在我查看第 13 行并找到所有相交的列：2、5、6、7、11 和 16
- 现在我查看与任何这些列中的任何 1 相交的所有行 - 这似乎是有问题的步骤 - 该标准选择要删除的所有 24 个数据行。
- 由于棋盘是空的，系统认为它找到了一个有效的解决方案。
这是我的 pen-and-paper 算法版本的图片：
鉴于对代码的请求，我现在附上它。顶部的评论解释了在哪里看。
代码如下：
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
您亲手 运行 算法遇到的问题是没有行的矩阵不是解决方案。您需要删除所有 列 ，仅删除行是失败的。您的示例 运行 仍有 12 列需要解决，因此未成功。
对于缩小的实例，您的确切封面实现似乎没问题，但绘图仪坏了。我通过更改
修复了它boardBitmap = fullBitmap[12:]
到
boardBitmap = fullBitmap[3:]
在plotMoveToBoard_np中，因为缩小后的实例只有三块。
编辑：还有一个关于如何生成移动名称的问题。有不同的同名动作。还有重复的动作（不影响正确性但会影响性能）。我变了
- g_rowNames.append(rowName)
+ g_rowNames.append(str(hash(str(finalBitmask))))
3x20 开始正常工作。 （这不是生成名称的好方法，因为理论上哈希值可能会发生冲突，但它是一行。）