可以將跳舞鏈接應用於此CSP嗎？

Question

能否舞蹈鏈實現Knuth的算法X的被用來解決this CSP？在這個遊戲中，第一個和最後一個數字總是在董事會中，我相信每個制定好的問題只有一個解決方案。

Answer 1

號

約束求解器肯定可以解決這樣的問題，但似乎不太可能做到這一點的最快方式。不好意思的是，似乎很難告訴求解者「路徑不能交叉」，這是一個有用的提示。

Answer 2

是。

假設我們要解決這個嗨達圖：

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

首先，讓我們命名空單元格用字母A，B，C，d：

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

我們需要表達3種對於每個解決方案行的約束條件爲X Algorithm：

• 使用了一個數字（以便相同的數字不會使用兩次）
• 使用了一個單元格（以便同一個單元格不被使用兩次）
• 下一個單元格受到約束（以便下一個單元格只能在相鄰的單元格中進行選擇）。這最後一個約束不需要精確覆蓋，所以它只能用作輔助列的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 

其中，例如，第二行（不計的標題線）可以理解爲：此行設置數（第一1 ）在單元a（第二個1）中。它也受到光限制的約束。並且它還限制3不在3a和3d，因爲它們不與單元a相鄰。

所有行讀這種方式，除了：

• 第一行僅指出在數約束。
• 行（最後4個），這也嵌入了與相鄰的限制。

的實現就留給讀者做練習...