algorithm - Dancing Links 可以应用于此 CSP 吗？

Question

能否使用 Knuth 算法 X 的 Dancing Links 实现来解决 this CSP ？在这个游戏中，第一个和最后一个数字总是已经在棋盘上，我相信每个精心设计的问题只有一个解决方案。

Answer 1

是的。

假设我们要解决这个 Hidato:

+---+   +---+
|   |   | 6 |
+---+---+---+
|   |   |
+---+---+
| 1 |   |
+---+---+

首先，让我们用字母 a、b、c、d 命名空单元格:

+---+   +---+
| d |   | 6 |
+---+---+---+
| b | c |
+---+---+
| 1 | a |
+---+---+

我们需要为 X Algorithm 的每个解行表达 3 种约束。 :

• 使用了一个号码(这样同一个号码就不会被使用两次)
• 使用一个单元格(这样同一个单元格就不会被使用两次)
• 下一个单元格是受约束的(这样下一个单元格只能在相邻的单元格中选择)。最后一个约束不需要精确覆盖，因此它应该只用作 DLX 中的辅助列术语。

由此产生的问题矩阵是:

1 2 3 4 5 6 a b c d   2a 2b 2c 2d     3a 3b 3c 3d     4a 4b 4c 4d     5a 5b 5c 5d
1                              1
  1         1         1               1        1
  1           1          1               1
  1             1           1               1
  1               1            1      1        1
    1       1                         1               1        1
    1         1                          1               1
    1           1                           1               1
    1             1                            1      1        1
      1     1                                         1               1        1
      1       1                                          1               1
      1         1                                           1               1
      1           1                                            1      1        1
        1   1                                                         1
        1     1                                                          1
        1 1     1                                                           1
        1         1                                                            1

例如，第二行(不包括标题行)可以读作:此行在单元格 a 中设置数字 2(第一个 1)(第二个 1).它也受到 2a 光约束的约束。并且它还限制 3 不在 3a 和 3d 上，因为它们不与单元格 a 相邻。

所有的行都是这样读的，除了:

• 第一行仅说明对数字 2 的限制。
• 5 行(最后 4 行)，其中还嵌入了与 6 相邻的约束。

实现留给读者练习......