CIS 554 Prolog 1: Logic Puzzle Notes
Fall 2014, David Matuszek

Sample puzzle

It's a Tie!

Sample code

% Problem #1, "It's a tie", Dell Logic Puzzles, October 1999
% Each man (mr so-and-so) got a tie from a relative.
tie(cupids).
tie(happy_faces).
tie(leprechauns).
tie(reindeer).

mr(crow).
mr(evans).
mr(hurley).
mr(speigler).

relative(daughter).
relative(father_in_law).
relative(sister).
relative(uncle).

solve :-
    tie(CrowTie), tie(EvansTie), tie(HurleyTie), tie(SpeiglerTie),
    all_different([CrowTie, EvansTie, HurleyTie, SpeiglerTie]),
    
    relative(CrowRelative), relative(EvansRelative),
    relative(HurleyRelative), relative(SpeiglerRelative),
    all_different([CrowRelative, EvansRelative, HurleyRelative, SpeiglerRelative]),

    Triples = [ [crow, CrowTie, CrowRelative],
                [evans, EvansTie, EvansRelative],
                [hurley, HurleyTie, HurleyRelative],
                [speigler, SpeiglerTie, SpeiglerRelative] ],
   
    % 1. The tie with the grinning leprechauns wasn't a present from a daughter.
    \+ member([_, leprechauns, daughter], Triples),
    
    % 2. Mr. Crow's tie features neither the dancing reindeer nor the yellow happy faces.
    \+ member([crow, reindeer, _], Triples),
    \+ member([crow, happy_faces, _], Triples),
    
    % 3. Mr. Speigler's tie wasn't a present from his uncle.
    \+ member([speigler, _, uncle], Triples),
    
    % 4. The tie with the yellow happy faces wasn't a gift from a sister.
    \+ member([_, happy_faces, sister], Triples),
    
    % 5. Mr Evans and Mr. Speigler own the tie with the grinning leprechauns
    %    and the tie that was a present from a father-in-law, in some order.
    ( (member([evans, leprechauns, _], Triples),
       member([speigler, _, father_in_law], Triples)) ;
       
      (member([speigler, leprechauns, _], Triples),
       member([evans, _, father_in_law], Triples)) ),
    
    % 6. Mr. Hurley received his flamboyant tie from his sister.
    member([hurley, _, sister], Triples),
    
    tell(crow, CrowTie, CrowRelative),
    tell(evans, EvansTie, EvansRelative),
    tell(hurley, HurleyTie, HurleyRelative),
    tell(speigler, SpeiglerTie, SpeiglerRelative).

% Succeeds if all elements of the argument list are bound and different.
% Fails if any elements are unbound or equal to some other element.
all_different([H | T]) :- member(H, T), !, fail.
all_different([_ | T]) :- all_different(T).
all_different([_]).

tell(X, Y, Z) :-
    write('Mr. '), write(X), write(' got the '), write(Y),
    write(' tie from his '), write(Z), write('.'), nl.
  

Comments

This is the "main" predicate:

solve :-
    tie(CrowTie), tie(EvansTie), tie(HurleyTie), tie(SpeiglerTie),
    all_different([CrowTie, EvansTie, HurleyTie, SpeiglerTie]),
    ... .

This predicate first chooses some ties. It will choose the same tie for everybody, then repeatedly backtrack, choosing different ties, until the all_different predicate is satisfied. It then does the same thing for relatives.

The all_different predicate takes a list and succeeds if the list contains no duplicate values. You can use this predicate without completely understanding it. That's fortunate, because it uses the metalogical ! operator. It also uses lists, but the syntax is simple (brackets and commas).

    Triples = [ [crow, CrowTie, CrowRelative],
                [evans, EvansTie, EvansRelative],
                [hurley, HurleyTie, HurleyRelative],
                [speigler, SpeiglerTie, SpeiglerRelative] ]
Each list in the triple is [mr, SomeTie, SomeRelative]. Notice that the person owning the tie is specified. We could instead have specfied all the ties, or all the relatives. The important thing is that we cover all three dimensions.
    % 1. The tie with the grinning leprechauns wasn't a present from a daughter.
    \+ member([_, leprechauns, daughter], Triples),

Uh, oh, negation. That's the \+ operator. All this says is that you cannot find, in the list of triples, a triple containing both leprechauns and daughter. The underscore, _, is a variable that could unify with anything, and you don't care what. Later tests are similar.

Negation isn't difficult, but it's tricky. Here's what you need to remember about negation: Whether negation succeeds or fails, it cannot ever unify (instantiate) anything. You can use negation to prevent certain unifications, as above, but you cannot use it to find out anything.