prolog - 在 Prolog 中解决关于时间限制的难题

Question

卡在 Prolog 问题上。我知道答案（因为我先在纸上做了），但我不知道如何让 Prolog 想出答案。

问题：

比尔每晚都吃点零食，每晚吃不同的水果和不同的坚果。从下面的陈述中，找出比尔上周每个工作日晚上吃了什么零食。

a) 苹果比芒果吃得晚。

b) 香蕉比杏仁和花生吃得晚，但比梨吃得早。

c) 腰果比香蕉和杏早吃，但比花生晚。

d) 杏仁后晚上没有吃山核桃。

e) 比尔吃了一晚核桃。

请注意，问题是关于 5 个工作日晚上（周一至周五），并提到了 5 种水果和 5 种坚果。您的程序应该解决问题并打印出解决方案，这将是一组 5 个三元组，例如（星期一，苹果，山核桃），...（星期五，芒果，核桃）。

显然，这些不是正确的答案，而只是向您展示解决方案的价值。

到目前为止的代码：

before_in_week(X, Y, Days) :-
    nth1(Xi, Days, X),
    nth1(Yi, Days, Y),
    Xi < Yi.

print_solve([Head|Tail]) :-
    write(Head),
    nl,
    print_solve(Tail).  

solve(A) :-
  % all triples
  A = [[day1, fruit1, nut1],
       [day2, fruit2, nut2],
       [day3, fruit3, nut3],
       [day4, fruit4, nut4],
       [day5, fruit5, nut5]],

  Days = [monday, tuesday, wednesday, thursday, friday],
  Days = [day1, day2, day3, day4, day5],

  Fruits = [apple,banana,pear,mango,apricot],
  permutation(Fruits, [fruit1, fruit2, fruit3, fruit4, fruit5]),

  Nuts = [almonds,pecans,cashews,peanuts,walnuts],
  permutation(Nuts, [nut1, nut2, nut3, nut4, nut5]),

  % clue 1 - mango before apple
  fruit5 \= mango,
  member([C1,mango,_], A),
  member([C2,apple,_], A), before_in_week(C1,C2,Days),
  % clue 2 - banana after almonds and peanuts, but before pear
  fruit5 \= banana,
  member([C1,banana,_], A),
  member([C2,pear,_], A), before_in_week(C1,C2,Days),
  member([C3,_,almonds], A), before_in_week(C3,C1,Days),
  member([C4,_,peanuts], A), before_in_week(C4,C1,Days),
  % clue 3 - cashews before banana and apricot, but after peanuts
  nut5 \= peanuts,
  member([C1,_,cashews], A),
  member([C2,_,peanuts], A), before_in_week(C1,C2,Days),
  member([C3,banana,_], A), before_in_week(C3,C1,Days),
  member([C4,apricot,_], A), before_in_week(C4,C1,Days),
  % clue 4 - pecans not night after almonds
  nut5 \= almonds,
  % clue 5 - ate walnuts one night


  print_solve(A).

score 2 · Accepted Answer

首先，真的不需要手动打印任何东西。Prolog 的顶层会为您执行此操作，如果您输入查询solve(A).，

第二，没有解决办法。那确实是您感兴趣的。有一种非常简单且非常通用的方法可以缩小失败的根源。简单地概括所有目标，一个接一个。*我喜欢通过在前面添加一个来做到这一点，如下所示：

:- op(950, fy, *)。
*_0。

解决（A）：-
  * A = [[day1,fruit1,nut1],[day2,fruit2,nut2],[day3,fruit3,nut3], 
         [day4,fruit4,nut4],[day5,fruit5,nut5]] ,

  天数 = [星期一|_ /*[星期二、星期三、星期四、星期五]*/ ]、
  天数 = [day1|_ /*[day2, day3, day4, day5]*/ ],

  *水果 = [苹果、香蕉、梨、芒果、杏] ,
  *排列（水果，[水果1，水果2，水果3，水果4，水果5]），

  *坚果 = [杏仁、山核桃、腰果、花生、核桃] ,
  *排列（坚果，[nut1，nut2，nut3，nut4，nut5]），

  % 线索 1 - 苹果之前的芒果
  *水果5 \=芒果，
  *成员([C1,mango,_], A) ,
  *成员([C2,apple,_], A), before_in_week(C1,C2,Days) ,
  % 线索 2 - 香蕉在杏仁和花生之后，但在梨之前
  *水果5 \=香蕉，
  *成员([C1,banana,_], A) ,
  * member([C2,pear,_], A), before_in_week(C1,C2,Days) ,
  *成员([C3,_,almonds], A), before_in_week(C3,C1,Days) ,
  * member([C4,_,peanuts], A), before_in_week(C4,C1,Days) ,
  % 线索 3 - 腰果在香蕉和杏之前，但在花生之后
  * nut5 \= 花生，
  *成员([C1,_,腰果], A) ,
  * member([C2,_,peanuts], A), before_in_week(C1,C2,Days) ,
  *成员([C3,banana,_], A), before_in_week(C3,C1,Days) ,
  *成员([C4,杏,_], A), before_in_week(C4,C1,Days) ,
  % 线索 4 - 杏仁后不晚上吃山核桃
  * nut5 \= 杏仁。
  % 线索 5 - 一晚吃了核桃

在这个程序切片中，它是您原始程序的概括，它归结为无法成功

Days = [monday|_], Days = [day1|_]

你必须在那里改变一些东西。day1是一个常数，它应该是一个变量。

稍后，全部替换X \= const为dif(X, const).

score 1 · Accepted Answer

您最大的问题是您正在使用原子（fruit4），但您应该使用变量（Fruit4）。注意开头的大小写。

此外，你正在做一个你不需要的排列。Prolog 通过回溯完成您需要的所有排列。这就是让 Prolog 成为如此有趣的语言的原因。

试试这个代码：

?- solve(A),print_solve(A).

solve(A) :-
    A = [[monday,_,_],[tuesday,_,_],[wednesday,_,_],[thursday,_,_],[friday,_,_]],
%clue 1 - mango before apple
    before([_,mango,_],[_,apple,_],A),
% clue 2 - banana after almonds and peanuts, but before pear
    before([_,_,almonds],[_,banana,_],A),
    before([_,_,peanuts],[_,banana,_],A),
    before([_,banana,_],[_,pear,_],A),
% clue 3 - cashews before banana and apricot, but after peanuts
    before([_,_,cashews],[_,banana,_],A),
    before([_,_,cashews],[_,apricot,_],A),
    before([_,_,peanuts],[_,_,cashews],A),
% clue 4 - pecans not night after almonds
    append(H,[[_,_,almonds],[_,_,_]|T],A),
    (member([_,_,pecans],H);member([_,_,pecans],T)),
% clue 5 - ate walnuts one night
    member([_,_,walnuts],A),
    true.

print_solve([]).
print_solve([Head|Tail]) :-
    write(Head),
    nl,
    print_solve(Tail). 

before(X,Y,Days) :-
    append(A,B,Days),
    member(X,A),
    member(Y,B).

这给了我：

[星期一，芒果，花生]
[星期二，苹果，腰果]
[星期三，杏，杏仁]
[星期四，香蕉，核桃]
[星期五，梨，山核桃]
是的。

score 1 · Accepted Answer

这个难题可以通过 Prolog 的主力之一轻松解决：生成和测试。关键是对域变量（约束）的表达式建模，以便检查它们是否满足。

snacks(Week) :-

    % model the problem with domain variables,
    % make the symbolic associations explicit

    % this is the 'generation phase'

    Nuts = [
        almonds:Almonds,
        cashews:Cashews,
        pecans:Pecans,
        peanuts:Peanuts,
        walnuts:_Walnuts
    ],
    Fruits = [
        apple:Apple,
        banana:Banana,
        pear:Pear,
        mango:Mango,
        apricot:Apricot
    ],

    % since we are going to use plain arithmetic, assign numbers before attempt to evaluate constraints
    assign_days(Nuts),
    assign_days(Fruits),

    % now the 'application symbols' are bound to integers, then we can
    % code actual constraint expressions in a simple way...

    % this is the 'test phase'

    % a) The apple was eaten later in the week than the mango.
    Apple>Mango,

    % b) The banana was eaten later in the week than both the almonds and peanuts,
    %    but earlier in the week than the pear.
    Banana>Almonds,Banana>Peanuts,Banana<Pear,

    % c) The cashews were eaten earlier in the week than both the banana and the apricot,
    %    but later in the week than the peanuts.
    Cashews<Banana,Cashews<Apricot,Cashews>Peanuts,

    % d) The pecans were not eaten the evening after the almonds.
    Pecans=\=Almonds+1,

    % e) Bill ate walnuts one night.
    % no constraints, just existance

    % when we get here, domain variables satisfy the constraints
    % just format the workspace in easy to read list
    findall((Day,Fruit,Nut),(
                nth1(NDay,['Monday','Tuesday','Wednesday','Thursday','Friday'],Day),
                memberchk(Fruit:NDay,Fruits),
                memberchk(Nut:NDay,Nuts)
            ),Week).

assign_days(Snacks) :-
    numlist(1,5,Nums),
    permutation(Nums,Perm),
    maplist([Day,_:Day]>>true,Perm,Snacks).

prolog - 在 Prolog 中解决关于时间限制的难题

3 回答 3

Related

Reference