Solving a puzzle in Prolog about time constraints

Question

Stuck on a Prolog problem. I know the answer (because I did it on paper first), but I cannot figure out how to get Prolog to come up with the answer.

Problem:

Bill eats a snack every night, having a different fruit and different nuts each night. From the statements below, identify what Bill had for a snack for each weeknight last week.

a) The apple was eaten later in the week than the mango.

b) The banana was eaten later in the week than both the almonds and peanuts, but earlier in the week than the 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.

d) The pecans were not eaten the evening after the almonds.

e) Bill ate walnuts one night.

Note that the problem is about 5 weeknights (Monday through Friday), and mentions 5 kinds of fruit and 5 kinds of nuts. Your program should solve the problem and print out the solution, which will be a set of 5 triples like (Monday, apple, pecans), ... (Friday, mango, walnuts).

Clearly, these are not the correct answers, but just values to show you what the solution will look like.

Code so far:

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

First, there is really no need to print anything manually. Prolog's top level does this for you, if you enter the query solve(A). yet,

second, there is no solution. That is really what you are interested in. There is a very simple and very general method to narrow down the source of failure. Simply generalize away all the goals, one after the other. I like to do this by adding a * in front like so:

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

solve(A) :-
  * 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

In this program slice, which is a generalization of your original program, it boils down to the inability to succeed for

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

You have to change there something. day1 is a constant, it rather should be a variable.

Later, replace all X \= const by dif(X, const).

Answer 2

Your biggest issue is that you are using atoms (fruit4) but you should use variables (Fruit4). Note the capitalization at the start.

Also, you're doing a permutation that you don't need. Prolog does all of the permutations you need via backtracking. That's what make Prolog such an interesting language.

Try this code:

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

That gives me:

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

Answer 3

The puzzle can be easily solved by means of one of workhorses of Prolog: generate-and-test. The key is modelling expressions over domain variables (constraints) making easy to check if they are satisfied.

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