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

Using Prolog to solve a classic logic puzzle

The program below was my first attempt at a complete Prolog program. I had done some research and gathered information from the Web concerning how to write Prolog. While there are a number of Prolog interpreters available - I have found SWI Prolog to be the most easy to use and it appears to have wide support. It has a built in editor. The text is highlighted in brown if a variable is unused or red if a rule is not used. The debugger opens in a new window and allows you to set break points and step through the program. It can be download from http://www.swi-prolog.org/download/stable and reference documentation is available on the website.

To help me get used to thinking in Prolog I thought I would try a reasonably straightforward logic puzzle. I chose a type of puzzle where you have to match, people with things and locations and one where I already had worked out the solution. Having a solution to refer to helped me in checking whether I was getting the correct outcome from my program and help find where I was making mistakes. The puzzle is written below.

Logic Puzzle Details
--------------------

There are 5 houses in 5 different colours.
In each house lives a person with a different nationality.
The 5 owners drink a certain type of beverage, smoke a certain brand of cigar, 
and keep a certain pet. No owners have the same pet, smoke the same brand of 
cigar, or drink the same beverage.

Who owns the fish?

Clues:
------
1.  The Brit lives in the red house.
2.  The Swede keeps dogs as pets.
3.  The Dane drinks tea.
4.  The green house is on the left of the white house.
5.  The green homeowner drinks coffee.
6.  The person who smokes Pall Mall rears birds.
7.  The owner of the yellow house smokes Dunhill.
8.  The man living in the center house drinks milk.
9.  The Norwegian lives in the first house.
10. The man who smokes Blend lives next to the one who keeps cats.
11. The man who keeps the horse lives next to the man who smokes Dunhill.
12. The owner who smokes Bluemaster drinks beer.
13. The German smokes prince.
14. The Norwegian lives next to the blue house.
15. The man who smokes Blend has a neighbor who drinks water.

One interesting feature of this puzzle is that there is no negative conditions like "X does not have Y". I had read that the use of negative Prolog terms (e.g not(X)) can be problematic and was pleased I did not need to use them in this program. Although I noticed there was no reference to a clue directly relating to the association with the pet(fish) I felt it needed to add it to the result clause to fill in a missing gap in the house matching process.

I have used a feature of Prolog for the House representation of what I call an anonymous functor. It has the form (A,B,C,D,E) which represents the houses (in order). This structure forms the basis for the whole puzzle as Prolog attempts to try matching various attributes of the puzzle with those that are already been bound from a previous step. As you can see from the final result each house ends up with a set of attributes which satisfy all the criteria.

Most of steps in the "result" rule match a clue given in the puzzle. I found it useful when writing this program to have the actual solution worked out beforehand. This also gave me an insight on how to approach this puzzle which was different from my initial investigations. I had been expecting to create a logic grid of all the possibilities like those seen in magazine logic puzzles. However, I tried using a simple grid of houses along the top and remaining attributes listed in row headings and found a solution was possible with just this.

The "match" rule has been written as a set of "or" alternatives (using the ";" operator). On reflection, I could have written these are as a set of terms like :-

match(X,(X,_,_,_,_)).
match(X,(_,X,_,_,_)).
:
:
etc

I think it makes no difference in the program logic. Though, with the benefit of more Prolog programs behind me, the form above does show the progressiveness of the matching process more clearly.

% Programmer: Kevin Bentley. Copyright (c) 2013
% Date: 05-Oct-2013
% Using: SWI Prolog.

% facts
% ----------
colour(red).
colour(white).
colour(yellow).
colour(blue).
colour(green).

race(brit).
race(swede).
race(dane).
race(norwegian).
race(german).

pet(dog).
pet(bird).
pet(cat).
pet(horse).
pet(fish).

drink(tea).
drink(coffee).
drink(milk).
drink(beer).
drink(water).

cigar(pallmall).
cigar(dunhill).
cigar(blend).
cigar(prince).
cigar(bluemaster).

% unify X with the next house (by backtracking)
% ----------------------------------------------
match(X,(House1,House2,House3,House4,House5)):-
 House1 = X;
 House2 = X;
 House3 = X;
 House4 = X;
 House5 = X.

onLeftOf(X,Y,(X,Y,_,_,_)).
onLeftOf(X,Y,(_,X,Y,_,_)).
onLeftOf(X,Y,(_,_,X,Y,_)).
onLeftOf(X,Y,(_,_,_,X,Y)).

centreHouse(X,(_,_,X,_,_)).

nextTo(X,Y,(X,Y,_,_,_)).
nextTo(X,Y,(Y,X,_,_,_)).

nextTo(X,Y,(_,X,Y,_,_)).
nextTo(X,Y,(_,Y,X,_,_)).

nextTo(X,Y,(_,_,X,Y,_)).
nextTo(X,Y,(_,_,Y,X,_)).

nextTo(X,Y,(_,_,_,X,Y)).
nextTo(X,Y,(_,_,_,Y,X)).

% Try to match (unify) each puzzle clue with each house.
% NB note use of (.....) terms which unify purely on arity/5
% ----------------------------------------------------------
result(House1,House2,House3,House4,House5) :-
    House1 = (_,race(norwegian),_,_,_),
    match((colour(red),race(brit),_,_,_),(House1,House2,House3,House4,House5)),
    match((_,race(swede),_,pet(dog),_),(House1,House2,House3,House4,House5)),
    match((_,race(dane),_,_,drink(tea)),(House1,House2,House3,House4,House5)),
    match((_,race(german),cigar(prince),_,_),(House1,House2,House3,House4,House5)),
    centreHouse((_,_,_,_,drink(milk)),(House1,House2,House3,House4,House5)),
    nextTo((_,_,cigar(blend),_,_),(_,_,_,pet(cat),_),(House1,House2,House3,House4,House5)),
    nextTo((_,_,_,pet(horse),_),(_,_,cigar(dunhill),_,_),(House1,House2,House3,House4,House5)),
    nextTo((colour(blue),_,_,_,_),(_,race(norwegian),_,_,_),(House1,House2,House3,House4,House5)),
    nextTo((_,_,cigar(blend),_,_),(_,_,_,_,drink(water)),(House1,House2,House3,House4,House5)),
    onLeftOf((colour(green),_,_,_,_),(colour(white),_,_,_,_),(House1,House2,House3,House4,House5)),
    match((colour(green),_,_,_,drink(coffee)),(House1,House2,House3,House4,House5)),
    match((_,_,cigar(pallmall),pet(bird),_),(House1,House2,House3,House4,House5)),
    match((colour(yellow),_,cigar(dunhill),_,_),(House1,House2,House3,House4,House5)),
    match((_,_,cigar(bluemaster),_,drink(beer)),(House1,House2,House3,House4,House5)),
    match((_,_,_,pet(fish),_),(House1,House2,House3,House4,House5)). 

Note in the above program I have added a reference to pet(fish), as the last term, as it has not been directly mentioned in the supplied clues. This will be bound to the House which does not have a value for pet.

Results from query
------------------
?- result(House1,House2,House3,House4,House5).
House1 = (colour(yellow), race(norwegian), cigar(dunhill), pet(cat), drink(water)),
House2 = (colour(blue), race(dane), cigar(blend), pet(horse), drink(tea)),
House3 = (colour(red), race(brit), cigar(pallmall), pet(bird), drink(milk)),
House4 = (colour(green), race(german), cigar(prince), pet(fish), drink(coffee)),
House5 = (colour(white), race(swede), cigar(bluemaster), pet(dog), drink(beer)) .

So the answer is the German owns the Fish.

One final observation I can make is the program looks far easier to understand than it took to write. I took several hours to come up with a suitable representation of the logic puzzle. I was told that this was far longer than the half an hour given to solve the puzzle on paper. I solved this logic puzzle manually in 20 mins. If you fancy a challenge, give it a go!

In my next blog I will look at another logic puzzle which involves the use of negative clues...