Using negation in Prolog to solve a logic puzzle

In my previous blog I was pleased that I did not have to handle any negative clues in the logic puzzle I solved using Prolog. I mean that the clues did not contain references like "something is not something else". In contrast to that the one below does. In fact the very first clue in the logic puzzle below has "...but did not have a Magnum" as part of the description.

The Puzzle
----------

Three girls: Ellie, Emily, Jessica visit the zoo. Can you find which girl's 
favourite animal was the zebra?

Clue 1. Ellie went to the zoo with her Grandma, but did not have a Magnum.
Clue 2. Mum went with the girl whose favourite animal was the elephant.
Clue 3. The girl whose favourite was the giraffe did not have a Cornetto
Clue 4. The Aunt bought a Twister for the child she took to the zoo, this was not Jessica.

There are four clues in this puzzle that partially describe which items belong together in a group. Each group should contain the following items: a girl, an animal, a lolly and a relative.
The challenge for me, in representing this logic puzzle in Prolog, was clues which stated that some items were not associated with others.

My initial approach to representing logic clues which stated they were not associated was to list the alternative associations. For example, in Clue 1 the remaining lolly items which are not a Magnum are: A twister or A Cornetto. I was unhappy with this approach. I felt I was part solving the puzzle and also I was not truly representing the semantics of the logic puzzle. Instead, I wrote each clue of this type using Prolog's not equal operator A \== B and relied on Prolog's backtracking to work through each fact when the items were not equal.

The solution process starts with the solution(Group1,Group2,Group3) predicate. Clue 2 is represented at the beginning of this predicate as the only non-negative clue. Each clue gives details about the association of items which have been represented in the form of (G,A,L,R) in this program (where G is one of the girls, A is an animal, L is a lolly and R is a relative). Then for each clue an attempt is made to bind new items with existing items in a group (if any). If no match can be made backtrack and try the next group.

Unfortunately, I noticed when testing this program that some items were appearing in more than one group and this highlighted a implicit condition of this type of puzzle; that items should only belong to one group. So this is the reason for the use of the difference(X,Y) predicate.

The use of the cut (!) at the end of the solution(Group1,Group2,Group3) predicate is there to prevent the display of an alternative solution which, while still valid, doesn't provide an alternative grouping of items. The output would look the list below without the cut :-

?- solution(P1,P2,P3).
P1 = (girl(jessica), animal(elephant), lolly(magnum), relation(mum)),
P2 = (girl(ellie), animal(zebra), lolly(cornetto), relation(grandma)),
P3 = (girl(emilie), animal(giraffe), lolly(twister), relation(aunt)) ;
P1 = (girl(jessica), animal(elephant), lolly(magnum), relation(mum)),
P2 = (girl(emilie), animal(giraffe), lolly(twister), relation(aunt)),
P3 = (girl(ellie), animal(zebra), lolly(cornetto), relation(grandma)) ;
false.

At the end of the Prolog entrepreter's display of the contents for the first P3 I used the Prolog alternative solution character ";". Then when I used it again at the end of the output of the second P3 the Prolog interpreter returned false. 

Since Prolog variable Group1 is fixed to always contain references to animal(elephant) and relation(mum) only the variables Group2 and Group3 can provide the alternative solutions. Potentially, there could have been 6 solutions because there is nothing in the clues to specify an order to the groups, unlike the Houses in the logic puzzle of my previous blog. It has been my observation in solving puzzles in general that it is often best to start from the same starting position as this often leads to a reduced number of searches for a solution (and makes the solution easier to remember when solving it using the brain). I was able to fix the known values from Clue2 of the solution to Group1 (chosen arbitarily) because this was only one clue which didn't have alternative solutions.

Below is the listing of the Prolog program with the resulting output from the solution inquiry beneath. It is informative to solve this puzzle by hand as this does illustrate the issues I have mentioned in this blog and thus you can verify the Prolog output.

/*.
Programmer: Kevin Bentley
Date: 15-Oct-2013
Copyright(c) 2013 Kevin Bentley
*/

% the facts

girl(ellie).
girl(emilie).
girl(jessica).

animal(elephant).
animal(zebra).
animal(giraffe).

lolly(twister).
lolly(cornetto).
lolly(magnum).

relation(aunt).
relation(grandma).
relation(mum).

% Matching rules 

match(X,Group1,Group2,Group3):-
    Group1 = X,
    different(Group1,Group2,Group3).

match(X,Group1,Group2,Group3):-
    Group2 = X,
    different(Group1,Group2,Group3).

match(X,Group1,Group2,Group3):-
    Group3 = X,
    different(Group1,Group2,Group3).

% Ensure each item is used only once.
different(X,Y,Z):-
    different(X,Y),
    different(Y,Z),
    different(Z,X).

different(X,Y):-
    (A1,B1,C1,D1) = X,
    (A2,B2,C2,D2) = Y,
    A1 \== A2,
    B1 \== B2,
    C1 \== C2,
    D1 \== D2.

% Represent logic puzzle clues
clue1(Group1,Group2,Group3):-
    animal(A),
    lolly(L),
    lolly(L) \== lolly(magnum),
    match((girl(ellie),animal(A),lolly(L),relation(grandma)),Group1,Group2,Group3).

clue3(Group1,Group2,Group3):-
    girl(G),
    relation(R),
    lolly(L),
    lolly(L) \== lolly(cornetto),
    match((girl(G),animal(giraffe),lolly(L),relation(R)),Group1,Group2,Group3).

clue4(Group1,Group2,Group3):-
    animal(A),
    girl(G),
    girl(G) \== girl(jessica),
    match((girl(G),animal(A),lolly(twister),relation(aunt)),Group1,Group2,Group3).

% Main predicate 
solution(Group1,Group2,Group3) :-
    girl(G),
    lolly(L),
    Group1 = (girl(G),animal(elephant),lolly(L),relation(mum)), 
    clue1(Group1,Group2,Group3),
    clue3(Group1,Group2,Group3),
    clue4(Group1,Group2,Group3),!. 

Sample output from querying the above Prolog program.

?- solution(P1,P2,P3).
P1 = (girl(jessica), animal(elephant), lolly(magnum), relation(mum)),
P2 = (girl(ellie), animal(zebra), lolly(cornetto), relation(grandma)),
P3 = (girl(emilie), animal(giraffe), lolly(twister), relation(aunt)).

My next blog will be about using Prolog to solve a different type of puzzle which involves checking adjacent numbers in a small grid...