prolog - 如何在 Prolog 中创建算术和不等式约束

Question

我是 Prolog 的新手，我有兴趣将以下应用题转换为 (SWI) Prolog:

There are 4 children: Abe, Dan, Mary, and Sue. Their ages, in no particular order, are 3, 5, 6, and 8. Abe is older than Dan. Sue is younger than Mary. Sue's age is Dan's age plus 3 years. Mary is older than Abe.

到目前为止我已经想出了

child(X) :-
    member(X, [3,5,6,8]).

solution(Abe, Dan, Mary, Sue) :-
    child(Abe),
    child(Dan),
    child(Mary),
    child(Sue),
    Abe > Dan,
    Sue < Mary,
    Sue == Dan+3,
    Mary > Abe,
    Abe \== Dan,
    Abe \== Mary,
    Abe \== Sue,
    Dan \== Mary,
    Dan \== Sue,
    Mary \== Sue.

但是运行查询

?- solution(Abe, Dan, Mary, Sue)

我刚刚得到错误。作为一个附带问题，Prolog 是否会执行强力搜索来寻找解决方案，或者是否有一些机制可以比 O(n!) 更好地解决这个(某种)问题？

我想要的结果是Abe = 5，Dan = 3，Mary = 9，Sue = 6。

Answer 1

整数的算术约束(例如此谜题中的约束)最好用 Prolog 系统的 CLP(FD) 约束来表达。

例如，在 SICStus Prolog、YAP 或 SWI 中:

:- use_module(library(clpfd)).

ages(As) :-
        As = [Abe,Dan,Mary,Sue],    % There are 4 children: Abe, Dan, Mary, Sue
        As ins 3\/5\/6\/8,          % Their ages are 3, 5, 6 and 8
        all_different(As),
        Abe #> Dan,                 % Abe is older than Dan
        Sue #< Mary,                % Sue is younger than Mary
        Sue #= Dan + 3,             % Sue's age is Dan's age plus 3 years
        Mary #> Abe.                % Mary is older than Abe

示例查询及其结果:

?- ages([Abe,Dan,Mary,Sue]).
Abe = 5,
Dan = 3,
Mary = 8,
Sue = 6.

从这个答案中我们可以看出，这个谜题有一个独特的解决方案。

请注意，无需进行任何搜索即可获得此答案!约束求解器通过称为约束传播的强大隐式机制推导出了唯一的解决方案，这是 CLP 系统相对于强力搜索的关键优势。本示例成功使用约束传播来修剪搜索树中除一个剩余分支之外的所有分支。