Решение головоломки в Прологе о временных ограничениях

Question

Застрял в проблеме Пролог. Я знаю ответ (потому что сначала я сделал это на бумаге), но я не могу понять, как заставить Пролога придумать ответ.

Проблема:

Билл ест перекусывать каждый вечер, каждый вечер есть разные фрукты и орехи. Из приведенных ниже утверждений определите, что Билл ел на каждую неделю на прошлой неделе.

а) Яблоко съели позже на неделе, чем мужчина go.

б) банан ели позже на неделе, чем миндаль и арахис, но раньше на неделе, чем грушу.

c) Кешью ели раньше на неделе, чем и банан, и абрикос, но позже на неделе, чем арахис.

d) орехи-пеканы не ели на вечер после миндаля.

e) Билл ел грецкие орехи одну ночь.

Обратите внимание, что проблема около 5 будней (с понедельника по пятницу), и упоминает 5 видов фруктов и 5 видов орехов. Ваша программа должна решить проблему и распечатать решение, которое будет состоять из 5 троек, таких как (понедельник, яблоко, орехи пекан), ... (пятница, человек go, грецкие орехи).

Понятно это не правильные ответы, а просто значения, показывающие, как будет выглядеть решение.

Код до сих пор:

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).

Answer 1

Во-первых, вам не нужно ничего печатать вручную. Верхний уровень Пролога делает это за вас, если вы введете запрос solve(A).,

секунда, решения не будет. Это действительно то, что вас интересует. Существует очень простой и очень общий метод, чтобы сузить источник неудачи. Просто обобщите все цели, одну за другой. Мне нравится делать это, добавляя * впереди так:

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

solve(A) :-
  * <s>A = [[day1, fruit1, nut1], [day2, fruit2, nut2], [day3, fruit3, nut3],</s>
         <s>[day4, fruit4, nut4], [day5, fruit5, nut5]]</s>,

  Days = [monday|_<s>/*[tuesday, wednesday, thursday, friday]*/</s>],
  Days = [day1|_<s>/*[day2, day3, day4, day5]*/</s>],

  * <s>Fruits = [apple,banana,pear,mango,apricot]</s>,
  * <s>permutation(Fruits, [fruit1, fruit2, fruit3, fruit4, fruit5])</s>,

  * <s>Nuts = [almonds,pecans,cashews,peanuts,walnuts]</s>,
  * <s>permutation(Nuts, [nut1, nut2, nut3, nut4, nut5])</s>,

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

В этом фрагменте программы, который является обобщением вашей исходной программы, он сводится к невозможности добиться успеха для

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

Вы должны там что-то изменить. day1 - это константа, скорее, она должна быть переменной.

Позже заменить все X \= const на dif(X, const).

Answer 2

Головоломка может быть легко решена с помощью одной из рабочих лошадок 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).

Answer 3

Ваша самая большая проблема в том, что вы используете атомы (fruit4), но вы должны использовать переменные (Fruit4). Обратите внимание на заглавные буквы в начале.

Кроме того, вы делаете перестановку, которая вам не нужна. 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).

Это дает мне:

[monday, mango, peanuts]
[tuesday, apple, cashews]
[wednesday, apricot, almonds]
[thursday, banana, walnuts]
[friday, pear, pecans]
Yes.