optimization - Prolog:优化难题求解器

Question

我目前正在解决一个特定的kenken问题，并且我注意到它大约需要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减小和从smallerfromlarger的“ Result is”更改为“ Result =“会使查询花费很长时间/无法解决，而如果我在第三个插槽中使用变量，则可以同时解决这两个问题。

另外，我注意到如果将行和列检查移至最接近开始处，查询将花费很长时间。

Answer 1

您似乎正在使用先生成后测试的方法，该方法首先生成候选对象，然后检查它们是否有效。

使用约束进行此任务效率更高。考虑使用有限域约束，这由SWI-Prolog中的library(clpfd)提供。

约束允许您甚至在搜索具体解决方案之前就声明性地陈述所有需求。它们可以在搜索之前和搜索期间过滤不一致的元素，这通常会带来巨大的性能提升。