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