序言：優化一個謎題求解器

Question

我目前正在解決一個特定的肯恩問題，我注意到它需要大約5秒鐘來解決。這是一個較小的謎題。不過，我也需要解決更大的問題，而且我擔心解決方案需要很長時間才能找到。下面是我的代碼的最相關的部分（我已刪除多餘的部分，他們是預期格式的）：

getlarger(First, Second, First) :- First >= Second. 
getlarger(First, Second, Second) :- First < Second. 

getsmaller(First, Second, Second) :- First >= Second. 
getsmaller(First, Second, First) :- First < Second. 

subtractsmallerfromlarger(First, Second, Result) :- getlarger(First, Second, Larger), 
    getsmaller(First, Second, Smaller), Result is Larger - Smaller. 

intdividelargerbysmaller(First, Second, Result) :- getlarger(First, Second, Larger), 
getsmaller(First, Second, Smaller), Result is Larger // Smaller. 

groupof4(List) :- nodups(List). 

allrowsof4([X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, X15, X16]) :- 
    groupof4([X1, X5, X9, X13]), groupof4([X2, X6, X10, X14]), %snip.... 

allcolumnsof4([X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, X15, X16]) :- 
    groupof4([X1, X2, X3, X4]), groupof4([X5, X6, X7, X8]), %snip.... 

validnumbers4([X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, X15, X16]) :- 
    validnumber4(X1), validnumber4(X2), %..... 

kenken([X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, X15, X16]) :- 
    %snip... 
    validnumbers4([X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, X15, X16]), 
    X5 * X1 * X2 =:= 2, 
    %Additional Arithmetic contraints removed 
    intdividelargerbysmaller(X11, X15, 2), %Dividend =:= 2, 
    subtractsmallerfromlarger(X12, X16, 3), %Difference =:= 3, 
    X13 * X14 =:= 6, 
    allcolumnsof4([X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, X15, X16]), 
    allrowsof4([X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14, X15, X16]). 

對於已定義的值，我使用的語法：X1 is 5，我把這個在我的代碼頂部認爲它會加快查找。

沒有必要讓我的代碼變得非常複雜，有沒有什麼地方可以讓它更有效率？

此外，我注意到改變intdividelargerbysmaller和subtractsmallerfromlarger「結果是」到「結果=」使查詢需要很長時間/不解決，而如果我在第三個槽中使用變量它解決這兩個問題。

此外，我注意到，如果將行和列檢查移動到開始附近，查詢需要很長時間。

Answer 1

您似乎在使用生成 - 然後測試方法，它首先生成候選項，然後檢查它們是否是有效的解決方案。

對於此任務使用約束條件要高效得多。考慮使用有限域約束，其由SWI-Prolog中的library(clpfd)提供。

約束條件允許您在搜索具體解決方案之前聲明式地聲明所有需求。他們可以在搜索前和搜索過程中過濾不一致的元素，這通常會顯着提高性能。