6

问题：

我已经以两种完全不同的方式为 Pentominoes 实现了 Knuth 的 DLX“跳舞链接”算法，但仍然得到不正确的解决方案。简单的 Wikipedia 示例可以正常工作 ( https://en.wikipedia.org/wiki/Knuth%27s_Algorithm_X#Example )，但更复杂的示例会失败。

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

下面是我简单的 3x5 Pentominoes 示例，仅使用 3 块放置。我可以用笔和纸完成算法，果然我的代码完全按照我的要求做，但在第一步，它破坏了我所有的行！当我查看连通性时，这些列确实看起来不错。很明显我误解了一些东西。

数据模型：

这是我试图让 DLX 解决的简单解决方案： 在此处输入图像描述

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

  • 左列是编码移动，例如第一行是块“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

示例失败：

第一步会杀死我数组的所有行（忽略数字标题行和列）

按照前面引用的维基百科文章，我这样做：

  • 查找列中设置的最小位数
  • 4 是最小计数，第 2 列是设置该位的最左边的列
  • 我选择与第 2 列相交的第一行，即第 13 行。
  • 第 4 列和第 13 行将被添加到要“覆盖”（又名删除）的列和行中
  • 现在我查看第 13 行并找到所有相交的列：2、5、6、7、11 和 16
  • Now I look at all the rows that intersect with any 1 in any of those columns - THIS seem to be the problematic step - that criteria selects ALL 24 data rows to remove.
  • Since the board is empty, the system thinks it has found a valid solution.

Here's a picture of my pen-and-paper version of the algorithm:

在此处输入图像描述

Given the requests for code, I'm now attaching it. The comments at the top explain where to look.

Here's the code:

https://gist.github.com/ttennebkram/8bd27adece6fb3a5cd1bdb4ab9b51166

Second Test

There's a second 3x5 puzzle I thought of, but it hits the same problem the first example has. For the record, the second 3x5 is:

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

2 回答 2

2

The issue you're seeing with your hand-run of the algorithm is that a matrix with no rows is not a solution. You need to eliminate all the columns, just getting rid of the rows is a failure. Your example run still has 12 columns that need to be solved left, so it's not a success.

于 2020-07-24T04:15:37.843 回答
1

Your exact cover implementation seems OK for the reduced instance, but the plotter was broken. I fixed it by changing

boardBitmap = fullBitmap[12:]

to

boardBitmap = fullBitmap[3:]

in plotMoveToBoard_np, since there are only three pieces in the reduced instance.

EDIT: there's also a problem with how you generate move names. There are distinct moves with the same name. There are also duplicate moves (which don't affect correctness but do affect performance). I changed

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

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

于 2020-08-02T15:56:25.483 回答