如何检查序言中的顺序？

Question

我正在尝试解决序言中的这个难题

Five people were eating apples, A finished before B, but behind C. D finished before E, but behind B. What was the finishing order?

我当前的解决方案有单例变量，我不确定如何解决这个问题。

finishbefore(A, B, Ls) :- append(_, [A,B|_], Ls).

order(Al):-
   length(Al,5),
   finishbefore(A,B,Al),
   finishbefore(C,A,Al),
   finishbefore(D,E,Al),
   finishbefore(B,D,Al).
%%query
%%?- order(Al).

Answer 1

让我们更正 finishbefore/3:

finishbefore(X, Y, L) :-
  append(_, [X|R], L),
  memberchk(Y, R).

然后让我们对已知的约束进行编码：

check_finish_time(Order) :-
  forall(
    member(X<Y, [a<b,c<a, d<e,d<b]),
    finishbefore(X,Y,Order)).

现在让我们测试所有可能的顺序

?- permutation([a,b,c,d,e],P),check_finish_time(P).

我得到 9 个解决方案，使用 ; 回溯...可能存在应编码的隐式约束。

编辑

抱歉打扰了，已找到错误。交换最后一个约束顺序，即 b<d 而不是 d<b，现在只允许 1 个解决方案...

Answer 2

这里是使用 library(clpz) 或 library(clpfd) 约束的纯版本。这个想法是要求一个稍微不同的问题。

How can an endpoint in time be associated to each person respecting the constraints given?

因为我们有五个人，五个不同的时间点就足够了，但不是绝对必要的，比如 1..5.

:- use_module(library(clpz)).  % or clpfd
:- set_prolog_flag(double_quotes, chars).  % for "abcde" below.

appleeating_(Ends, Zs) :-
    Ends = [A,B,C,D,E],
    Zs = Ends,
    Ends ins 1..5,
    % alldifferent(Ends),
    A #< B,
    C #< A,
    D #< E,
    B #< D.

?- appleeating_(Ends, Zs).
   Ends = [2, 3, 1, 4, 5], Zs = [2, 3, 1, 4, 5].

只有一种解决方法！请注意 alldifferent/1 不是直接需要的，因为它没有说明不允许两个人同时结束。事实上，以上证明没有更短的解决方案。 @CapelliC 的解决方案强加了一个命令，即使两个人均等完成。但为了兼容性，现在让我们将解决方案映射回您的表示。

list_nth1(Es, N, E) :-
    nth1(N, Es, E).

appleeatingorder(OrderedPeople) :-
    appleeating_(Ends, Zs),
    same_length(OrderedPeople, Ends),
    labeling([], Zs), % not strictly needed
    maplist(list_nth1(OrderedPeople), Ends,"abcde").  % effectively enforces alldifferent/1

?- appleeatingorder(OrderedPeople).
   OrderedPeople = [c,a,b,d,e].
?- appleeatingorder(OrderedPeople).
   OrderedPeople = "cabde".

最后一个使用双引号的解决方案直接产生了Scryer。在 SWI 中使用 library(double_quotes).

(appleeating_/2 的额外参数 Zs 在这种情况下并不是严格需要的，但它通常对 CLP 谓词来说是一个非常有用的约定。它将建模部分 (appleeating_/2) 从搜索部分 (labeling([], Zs)) 以便您可以轻松地同时尝试 search/labeling 的各种版本。为了真正解决，Zs 中的所有变量都必须有实际价值。）

如何检查序言中的顺序？

How to check order in prolog?

prolog