數獨解算器，而不clpfd

Question

我有一個AI項目中，我應該做一個數獨解算器序言但不使用clpfd包。我應該如何編寫代碼，並且有什麼方法可以在變量獲取值時進行打印？

Answer 1

沒有clpfd，你必須編寫一個經典的生成和測試搜索。關於clpfd的好處是約束限制了搜索空間。你可以在不使用clpfd的情況下模擬它。讓我們簡化一下任務，這樣我就可以說明一切。你怎麼能找到解決這兩個方程的X和Y值：X + Y = 10，2 * X + Y - 1 = 15？

首先，編碼您的兩個等式：

eq1(X,Y) :- 10 is X + Y. 
eq2(X,Y) :- 15 is 2*X + Y - 1. 

現在創建一個求解謂詞搜索空間：

solution(X, Y) :- 
    between(1, 10, X), between(1, 10, Y), 
    eq1(X,Y), 
    eq2(X,Y). 

現在你可以運行它，看看：

?- solution(X,Y). 
X = 6, 
Y = 4 ; 
false. 

這比clpfd的效率要低，因爲clpfd會注意到關於方程式的事情，這會有助於解決它應變搜索空間：

?- [library(clpfd)]. 
true. 

?- X + Y #= 10, 2*X + Y - 1 #= 15. 
2*X+Y#=16, 
X+Y#=10. 

?- X + Y #= 10, 2*X + Y - 1 #= 15, X in 1..10. 
X = 6, 
Y = 4. 

看，它已經發現只有一個解決方案，我根本不必限制Y.這非常令人印象深刻！但是你仍然可以在沒有clpfd的情況下使用Prolog，它只是更糟。 :)在這個例子中，我們可能嘗試了所有10x10 = 100個可能的組合來找到這個解決方案。效率較低。但並非不可能。

那麼，你有什麼限制，你必須找出數獨？可能是這樣的：

unique(Row) :- sort(Row, Sorted), length(Row, Length), length(Sorted, Length). 
all_digits(Row) :- forall(between(1,9,X), memberchk(X, Row)). 

等等。

編輯：組合的複雜性估計

假設我們做一個完全無原則搜索：也就是說，我們甚至嘗試顯然是錯誤的情況下，像所有787-9的網格。我們有9x9 = 81個單元格和9個可能的值（1-9）。這會產生9^81 =非常大的數字，在您的一生中不太可能被檢查。而且這些網格中的大部分都將無果而終。

假設你限制你的搜索，使每一行是1-9的排列。有9！ 1-9的排列;其中9個，你可以乘以9，所以應該有9！^ 9。這仍然很糟糕！ clpfd可能能夠通過結合3x3網格約束來進一步剔除這個問題;我不知道我會如何去做手動，除了以半程序方式，選擇一個3x3的網格排列，然後將每個3x1的排傳遞給下一個3x3的網格選擇。

值得注意的是，經典Prolog程序中的大部分優化都歸結爲使生成步驟生成更好的合格候選者或使測試步驟更便宜。更明顯的實現對檢查更復雜的實現仍然有用。

感謝@mat檢查我的數學和推薦this excellent article on the combinatorial problem of Sudoku。