Solve Einstein’s Riddle using Prolog

This week, we started learning Prolog at school. So to exercise, I choose the Einstein's Riddle. Einstein wrote this riddle in the 19th century. He stated that only 2% of the population can solve it by mind. Personnally, I'm not of this two %, I needed paper and pens to solve it. But this is not the them of the post, so let's use Prolog to solve it. I will present my solution, there is certainly other solutions, and certainly better, but it makes only some days that I started learning this language and this new kind of developing, logical programming.

Here is the riddle as stated by Einstein :

1. In a street there are five houses, painted five different colours.
2. In each house lives a person of different nationality
3. These five homeowners each drink a different kind of beverage, smoke different brand of cigar and keep a different pet.

The question is : Who owns the fish ?

And there are 15 hints :

1. The Brit lives in a red house.
2. The Swede keeps dogs as pets.
3. The Dane drinks tea.
4. The Green house is next to, and on the left of the White house.
5. The owner of the Green house 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 centre house drinks milk.
9. The Norwegian lives in the first house.
10. The man who smokes Blends lives next to the one who keeps cats.
11. The man who keeps horses lives next to the man who smokes Dunhill.
12. The man who smokes Blue Master drinks beer.
13. The German smokes Prince.
14. The Norwegian lives next to the blue house.
15. The man who smokes Blends has a neighbour who drinks water.

So let's start with the code !

First of all, we'll create a list of tuple containing all the informations about a men . The position in the list represent the position of the house in the street. So we'll create a predicate to create the list :

persons(0, []) :- !.
persons(N, [(_Men,_Color,_Drink,_Smoke,_Animal)|T]) :- N1 is N-1, persons(N1,T).

The first predicate, is to end when the index is 0 and the list is empty. And the second one create a recursive list with N element. Then, I needed a predicate to get the Nth element if corresponding to some informations of the recursive list :

person(1, [H|_], H) :- !.
person(N, [_|T], R) :- N1 is N-1, person(N1, T, R).

Again, the first one is used to stop when we are at the good element. And the second predicate iterate until the good element is found.

Then, I have translated the hints into predicate :

% The Brit lives in a red house
hint1([(brit,red,_, _, _)|_]).
hint1([_|T]) :- hint1(T).
% The Swede keeps dogs as pets
hint2([(swede,_,_,_,dog)|_]).
hint2([_|T]) :- hint2(T).
% The Dane drinks tea
hint3([(dane,_,tea,_,_)|_]).
hint3([_|T]) :- hint3(T).
% The Green house is on the left of the White house
hint4([(_,green,_,_,_),(_,white,_,_,_)|_]).
hint4([_|T]) :- hint4(T).
% The owner of the Green house drinks coffee. 
hint5([(_,green,coffee,_,_)|_]).
hint5([_|T]) :- hint5(T).
% The person who smokes Pall Mall rears birds
hint6([(_,_,_,pallmall,bird)|_]).
hint6([_|T]) :- hint6(T).
% The owner of the Yellow house smokes Dunhill
hint7([(_,yellow,_,dunhill,_)|_]).
hint7([_|T]) :- hint7(T).
% The man living in the centre house drinks milk
hint8(Persons) :- person(3, Persons, (_,_,milk,_,_)).
% The Norwegian lives in the first house
hint9(Persons) :- person(1, Persons, (norwegian,_,_,_,_)).
% The man who smokes Blends lives next to the one who keeps cats
hint10([(_,_,_,blend,_),(_,_,_,_,cat)|_]).
hint10([(_,_,_,_,cat),(_,_,_,blend,_)|_]).
hint10([_|T]) :- hint10(T).
% The man who keeps horses lives next to the man who smokes Dunhill
hint11([(_,_,_,dunhill,_),(_,_,_,_,horse)|_]).
hint11([(_,_,_,_,horse),(_,_,_,dunhill,_)|_]).
hint11([_|T]) :- hint11(T).
% The man who smokes Blue Master drinks beer
hint12([(_,_,beer,bluemaster,_)|_]).
hint12([_|T]) :- hint12(T).
% The German smokes Prince
hint13([(german,_,_,prince,_)|_]).
hint13([_|T]) :- hint13(T).
% The Norwegian lives next to the blue house
hint14([(norwegian,_,_,_,_),(_,blue,_,_,_)|_]).
hint14([(_,blue,_,_,_),(norwegian,_,_,_,_)|_]).
hint14([_|T]) :- hint14(T).
% The man who smokes Blends has a neighbour who drinks water
hint15([(_,_,_,blend,_),(_,_,water,_,_)|_]).
hint15([(_,_,water,_,_),(_,_,_,blend,_)|_]).
hint15([_|T]) :- hint15(T).
% The question : Who owns the fish ?
question([(_,_,_,_,fish)|_]).
question([_|T]) :- question(T).

I've used one main way to do the predicates. The first predicate type used for every predicates except 8 and 9 is really simple. I expressed the valid values and then, I used iteration to iterate over the arrays. With that, the predicate is true when the the list contains the good value (or values when testing for an house next to another).

The other predicate is that we specify that the Nth contains some values.

After that, we must specify the question :

question([(_,_,_,_,fish)|_]).
question([_|T]) :- question(T).

We just iterate the list, specifying that there is a man with a fish. Without the question, we can solve the problem, but we don't know that the last animal is a fish.

And after all, we can try to solve the riddle :

solution(Persons) :-
  persons(5, Persons),
  hint1(Persons),
  hint2(Persons),
  hint3(Persons),
  hint4(Persons),
  hint5(Persons),
  hint6(Persons),
  hint7(Persons),
  hint8(Persons),
  hint9(Persons),
  hint10(Persons),
  hint11(Persons),
  hint12(Persons),
  hint13(Persons),
  hint14(Persons),
  hint15(Persons),
  question(Persons).

We just say that the solution is the combinaison of all the hints and the question, so that the solution must validate all predicates.

So let's try our program :

wichtounet@wichtounet-laptop:~/Desktop$ gprolog
GNU Prolog 1.3.0
By Daniel Diaz
Copyright (C) 1999-2007 Daniel Diaz
| ?- [einstein.pl].      
uncaught exception: error(syntax_error('user_input:1 (char:10) , | ] or operator expected in list'),read_term/3)
| ?- 
Prolog interruption (h for help) ? e
wichtounet@wichtounet-laptop:~/Desktop$ gprolog
GNU Prolog 1.3.0
By Daniel Diaz
Copyright (C) 1999-2007 Daniel Diaz
| ?- consult('einstein.pl').
compiling /home/wichtounet/Desktop/einstein.pl for byte code...
/home/wichtounet/Desktop/einstein.pl compiled, 100 lines read - 14891 bytes written, 17 ms
yes
| ?- solution(Persons).
Persons = [(norwegian,yellow,water,dunhill,cat),(dane,blue,tea,blend,horse),(brit,red,milk,pallmall,bird),
(german,green,coffee,prince,fish),(swede,white,beer,bluemaster,dog)] ? a
(20 ms) no
| ?- 
Prolog interruption (h for help) ? e

With that, we found not only the man who have fish but also all the other informations. The answer is the german.

That's all we need :)

I hope you found that post interesting.

Here is the complete source code : Einstein's Riddle in Prolog

Related articles