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

Question

问题：

我已经以两种完全不同的方式为 Pentominoes 实现了 Knuth 的 DLX“dancing links”算法，但仍然得到不正确的解决方案。简单的维基百科示例工作正常（https://en.wikipedia.org/wiki/Knuth%27s_Algorithm_X#Example），但更复杂的示例失败。

调试完整的 Pentominoes 游戏需要一个包含近 2,000 个条目的表，所以我想出了一个大大简化的谜题（如下图所示），它仍然足够复杂以显示错误的行为。

下面是我简单的 3x5 Pentominoes 示例，只使用了 3 块来放置。我可以用笔和纸来完成算法，而且我的代码确实按照我告诉它的去做，但在第一步，它破坏了我的所有行！当我查看连通性时，这些列确实似乎没问题。很明显我误解了一些东西。

数据模型：

这是我试图让 DLX 解决的微不足道的解决方案：

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

• 左列是编码移动，例如第一行是“L”，放置在 0,0，然后逆时针旋转 ONE 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

对于减少的实例，您的确切封面实现似乎没问题，但绘图仪已损坏。我通过改变来修复它

boardBitmap = fullBitmap[12:]

到

boardBitmap = fullBitmap[3:]

中plotMoveToBoard_np，因为缩减实例中只有三块。

编辑：如何生成移动名称也存在问题。有相同名称的不同动作。还有重复的动作（这不会影响正确性，但会影响性能）。我变了

-                    g_rowNames.append(rowName)
+                    g_rowNames.append(str(hash(str(finalBitmask))))

3x20 开始正常工作。（这不是生成名称的好方法，因为理论上哈希可能会发生冲突，但它是一行。）