The Zebra Problem
Author Message
The Zebra Problem

The Zebra Problem is described below.  I'm not looking for the solution but
rather a hint on how to solve it.  If anybody has ever encountered the
Zebra problem then could you please point me in the right direction.
Could you please tell me what kind of problem it is?

I have to solve this in C linking it with PVM (Parallel Virtual Machine).
I know Comp.Constraints and Comp.comp.prolog are the wrong newsgroup but I
figured it was more likely that someone had seen a similar problem in this
newsgroup rather than a C newsgroup.

Once I get this solved I will move onto a more general program able to
solve many Zebra like problems.

Thanks,

The Zebra Problem
=================

There are five houses, each of a different colour and inhabited
by men of different nationalities, with different pets, drinks
and cigarettes.

1  The Englishman lives in the red house.
2  The Spaniard owns a dog.
3  Coffee is drunk in the green house.
4  The green house is immediately to the right of the ivory house.
5  The Gold smoker owns the snails.
6  Kools are smoked in the yellow house.
7  Milk is drunk in the middle house.
8  The Norwegian lives in the first house.
9  The Chesterfield smoker lives next to the fox owner.
10  Kools are smoked next to the house where the horse is kept.
11  The Lucky-Strike smoker drinks orange juice.
12  The Japanese smokes Parliaments.
13  The Norwegian lives next to the blue house.

Who drinks water and who owns the zebra?

Attributes
==========

House Colours:  Red
Green
Yellow
Blue
Ivory

Nationalities:  English
Spaniard
Ukranian
Norwegian
Japanese

Pets:           Dog
Snail
Horse
Fox
Zebra (Not mentioned)

Drinks:         Coffee
Tea
Milk
Orange Juice
Water (Not mentioned)

Cigarettes:     Golds
Kools
Chesterfields
Lucky-Strikes
Parliament
--
==============================================================

Until you stalk and overrun, you can't devour anyone.
-Hobbes (Calvin and Hobbes)

Wed, 29 Jul 1998 03:00:00 GMT
The Zebra Problem

: The Zebra Problem is described below.  I'm not looking for the solution but
: rather a hint on how to solve it.  If anybody has ever encountered the
: Zebra problem then could you please point me in the right direction.
: Could you please tell me what kind of problem it is?

: I have to solve this in C linking it with PVM (Parallel Virtual Machine).
: I know Comp.Constraints and Comp.comp.prolog are the wrong newsgroup but I
: figured it was more likely that someone had seen a similar problem in this
: newsgroup rather than a C newsgroup.

: Once I get this solved I will move onto a more general program able to
: solve many Zebra like problems.

for solving such problems.  The code below is a Prolog program
"zebraOwner(Who)." and Prolog will reply: "japanese".

If you write a general purpose program to solve such problems,
I wonder if you won't end up building most of the mechanisms already
present in logic programming systems.

% The Zebra problem
% The traditional problem has "smokes" as one of the clue categories.
% Sports replace smokes in this version (attributed to Peter Reintjes).

% First, some preliminary definitions:

% member(X,Y): X belongs to the list Y.
member(X,[X|Tail]).
member(X,[_|Tail]) :- member(X,Tail).

% rightof(X,Y,Z): X is *immediately* to the right of Y in Z.
rightof(X,Y,[Y,X | _ ]).
rightof(X,Y,[_|L]):- rightof(X,Y,L).

% next(X,Y,Z): X and Y are next to each other in Z.
next(X,Y,[X,Y | _ ]).
next(X,Y,[Y,X | _ ]).
next(X,Y,[_|L]):- next(X,Y,L).

% rightEnd(X,Y): X is the right end element of Y.
rightEnd(X,[X]).
rightEnd(X,[_|Y]) :- rightEnd(X,Y).

% end(X,Y): X is either the left or right end element of Y.
end(X,[X|_]).
end(X,Y) :- rightEnd(X,Y).

% Here is the informal statement of the problem:

% 1: The Englishman lives in the red house
% 2: The Spaniard owns a dog
% 3: The man in the green house drinks coffee
% 4: The Ukrainian drinks tea
% 5: The green house is to the right of the ivory house
% 6: The Go player owns snails
% 7: The man in the yellow house plays cricket
% 8: Milk is drunk in the middle house
% 9: The Norwegian lives at the end
% 10: The Judo-ist lives next to the man who has a fox
% 11: The cricketer lives next to the man who has a horse
% 12: The poker player drinks orange juice
% 13: The Japanese plays polo
% 14: The Norwegian lives next to the blue house

% Who owns the zebra and who drinks water?

% Here is a translation of the problem into Prolog:

% house format: h(Nat,Game,Drink,Pet,Color).
clues(Hs) :-
Hs = [h(_,_,_,_,_),h(_,_,_,_,_),h(_,_,_,_,_),h(_,_,_,_,_),h(_,_,_,_,_)],
member(h(english,_,_,_,red), Hs),
member(h(spanish,_,_,dog,_), Hs),
member(h(_,_,coffee,_,green), Hs),
member(h(ukrainian,_,tea,_,_), Hs),
rightof( h(_,_,_,_,green), h(_,_,_,_,ivory), Hs),
member(h(_,go,_,snails,_), Hs),
member(h(_,cricket,_,_,yellow), Hs),
Hs = [_, _, h(_,_,milk,_,_), _, _],
end( h(norwegian,_,_,_,_), Hs),
next(h(_,judo,_,_,_), h(_,_,_,fox,_), Hs),
next(h(_,cricket,_,_,_), h(_,_,_,horse,_), Hs),
member(h(_,poker,juice,_,_), Hs),
member(h(japanese,polo,_,_,_), Hs),
next(h(norwegian,_,_,_,_), h(_,_,_,_,blue), Hs).

zebraOwner(Who) :- clues(Hs), member(h(Who,_,_,zebra,_),Hs).

Thu, 30 Jul 1998 03:00:00 GMT
The Zebra Problem

Quote:
> The Zebra Problem is described below.  I'm not looking for the solution but
> rather a hint on how to solve it.  If anybody has ever encountered the
> Zebra problem then could you please point me in the right direction.
> Could you please tell me what kind of problem it is?

> I have to solve this in C linking it with PVM (Parallel Virtual Machine).
> I know Comp.Constraints and Comp.comp.prolog are the wrong newsgroup but I
> figured it was more likely that someone had seen a similar problem in this
> newsgroup rather than a C newsgroup.

> Once I get this solved I will move onto a more general program able to
> solve many Zebra like problems.

> Thanks,

Ciao,
I am replying to your posting because I really love this kind of puzzles
...
I am not very expert of the field, but I sometimes play this game ...

I saw this kind of problems very neatly played with the help of a stack
of punched cards in one of the "Mathematical Games" columns written by the
wonderful Martin Gardner in the Scientific American years ago (and
collected in several paperback editions).

The cards were shaped this way:
______ ___ _ ___ ___
| O O U O U U O U O |
|                   |
|                   |
|___________________|

with a closed hole for a "0" valued feature and a open one for a "1"
valued feature.

For every possible combination of features we have a card that lists the
combination, e.g: Spanyard, yellow, dog, water, Kools
(Probably we will have to add the implicit feature "Position" because the
clauses speak about "the first house" .... and "the house near ...".)
(this accounts for 5^6 combinations)

The set of combinations represent the universe of possible results ...
For every clause we delete from the current universe the impossible
combinations and we hope we will finish with a universe that will reply
to the final questions.

Obviously this is a "brute force" approach, applicable only if the
universe is small. The cards game is then fast
because you can draw a group of cards that satisfy some assigment of
constraints in one single move, with the help of some pins inserted in
the holes.

The clauses of the zebra problem can be divided in two sets, the ones that
are independent from the current universe state (clauses
1,2,3,5,6,7,8,11,12) and those that depends on it.

For every "simple" clause in the problem remove all the combinations that
cannot satisfy the clause, e.g. for clause 1
remove englishman and not red
remove red and not englishman

Then for every complex clause we look if the current universe is
"simpler", that is it's possible to deduce some other kind of deletion.

The sequence of deletion could be:

Quote:
>     1  The Englishman lives in the red house.

remove englishman and not red
remove red and not englishman

Quote:
>     2  The Spaniard owns a dog.

remove spaniard and not dog
remove dog and not spaniard

Quote:
>     3  Coffee is drunk in the green house.

remove coffe and not green
remove green and not coffee

Quote:
>     4  The green house is immediately to the right of the ivory house.

(delay)

Quote:
>     5  The Gold smoker owns the snails.

remove gold and not snail
remove snail and not gold

Quote:
>     6  Kools are smoked in the yellow house.

remove kools and not yellow
remove yellow and not kools

Quote:
>     7  Milk is drunk in the middle house.

remove milk and not position=3
remove position=3 and not milk

Quote:
>     8  The Norwegian lives in the first house.

remove norvegian and not position=1
remove position=1 and not norvegian

Quote:
>     9  The Chesterfield smoker lives next to the fox owner.

(delay)

Quote:
>    10  Kools are smoked next to the house where the horse is kept.

(delay)

Quote:
>    11  The Lucky-Strike smoker drinks orange juice.

remove lucky-strike and not orange
remove orange and not lucky-strike

Quote:
>    12  The Japanese smokes Parliaments.

remove japanese and not parliaments
remove parliaments and not japanese

Quote:
>    13  The Norwegian lives next to the blue house.

Now we discover that the norvegian house is in position 1, and then the blue
is in position 2

remove blue and not position=2
remove position=2 and not blue

.... hopefully now the other delayed clauses can be applied ...

I have tried to solve the puzzle and I have found at least a pair of
solutions. (there could be more)

house 1: Norvegian Yellow ____   Fox    Kool
house 2: Ukranian  Blue   ____   Horse  Chesterfield
house 3: English   Red    Milk   Snails Gold
house 4: Spaniard  Ivory  Orange Dog    Lucky-strike
house 5: Japanese  Green  Coffee Zebra  Parliament

In both these two solutions the Japanese owns the zebra but we don't know
if the water drinker is the Norvegian or the Ukranian ...

I must say that to solve the problem I have used a different approach:
For every position of the house I have associated to each the 5 variables
Language, Color, Drink, Fox, Cigarettes the possible set of values. (Domain)

E.g.:
Home 1 Language = {Norv,Eng,Ukr,Span,Jap}

Then for every clause I have deleted the values that were not possible

E.g.:
Clause 8: the norv. lives in house 1
fix the value of "house1lang" to Norv and delete from the domains of the
other houses the Norvegian value.

By applying all the possible rules I have tried to restrict the domains,
such that when the domain of a variable contains one single value I can
fix the corresponding variable to this value and delete the value from the
other domains.

When I cannot fix more variables, I choose the variable with the smallest
domain and I assume that the correct value is the first one ... if this
reduces other domains I continue with the restrictions ... If i get a
contradiction I know the assumption on the value is wrong and I can delete
the value from the domain ...

I hope my explanation is understandable ... :-)

Perhaps you could also look for Assumption Based Truth Maintenance
systems in the literature ...

All the best
Ciao
Andrea

Quote:

> Who drinks water and who owns the zebra?

> Attributes
> ==========

> House Colours:     Red
>            Green
>            Yellow
>            Blue
>            Ivory

> Nationalities:     English
>            Spaniard
>            Ukranian
>            Norwegian
>            Japanese

> Pets:              Dog
>            Snail
>            Horse
>            Fox
>            Zebra (Not mentioned)

> Drinks:            Coffee
>            Tea
>            Milk
>            Orange Juice
>            Water (Not mentioned)

> Cigarettes:        Golds
>            Kools
>            Chesterfields
>            Lucky-Strikes
>            Parliament
> --
> ==============================================================

> Until you stalk and overrun, you can't devour anyone.
>                            -Hobbes (Calvin and Hobbes)

-- Andrea Sterbini, PhD,  Computer Science Dept., Rome University "La Sapienza"

Visiting DIKU, Copenhagen 'til Easter tel: +45-35-32-13-59 fax: +45-35-32-14-01
"Life, don't talk me about life"
Marvin the paranoid android

Fri, 31 Jul 1998 03:00:00 GMT
The Zebra Problem

: The Zebra Problem is described below.  I'm not looking for the solution but
: rather a hint on how to solve it.  If anybody has ever encountered the
: Zebra problem then could you please point me in the right direction.
: Could you please tell me what kind of problem it is?

A solution of the original zebra problem using CLP(FD) is in

http://www.ecrc.de/eclipse/html/extroot/node59.html

--Micha

Sun, 02 Aug 1998 03:00:00 GMT
The Zebra Problem

: The Zebra Problem is described below.  I'm not looking for the solution but
: rather a hint on how to solve it.  If anybody has ever encountered the
: Zebra problem then could you please point me in the right direction.
: Could you please tell me what kind of problem it is?

The problem you describe is undoubtably a search problem. There is a search
-space of possible solutions, and within this search space there are
a large number of solutions (the problem may not be completely restricted
and it may be that the Irishman can live in the yellow house or the Englishman)

So how do you tackle search problems - well you use logic programming
which has a builtin search machine which acts over logical variables
to find possible solutions and then determine whether or not the problem
is solvable, when yes then the system delivers solutions - one by one
or when not the machine says no. - literally

So you takes the best logic programming system around (;-) IF/Prolog) and
you uses the best way to constrain the search space (IF/Prolog's constraint
technology package) and you hacks the code. But wait, the code is almost
only a matter of writing down the problem; unlike the other solutions
you have seen , constraints maen that you don't need to optimise the
search according to the problem you actually have.

OK here goes (an equivalent problem - we had lying around):

solution(Solution) :-
Solution = [Nations, Colors, Books, Autos, Animals],

Nations = [USA, Canada, England, Japan, Switzerland],
Colors = [Red, Green, Yellow, Blue, White],
Books = [Donald, Genji, London, Holmes, Heidi],
Autos = [Buggy, Citroen, Van, _DeSoto, _Jeep],
Animals = [Cat, Hen, Camel, Pig, _Zebra],

domains(Solution, 1..5),

USA = Red,
England = Citroen,
Japan = 1,
Switzerland = Heidi,
Green = Buggy,
Blue = 2,
Donald = Hen,
Genji = Yellow,
Holmes = Pig,
Van = 3,
left(White, Green),
Pig ?\= 5,
neighbor(London, Camel),
neighbor(Genji, Pig),

labeling(Solution).

left(A, B) :- A ?= B + 1.

neighbor(A, B) :- left(A, B).
neighbor(A, B) :- left(B, A).

omains([], _).
domains([Class|Group], Domain) :-
Class in Domain,
all_distinct(Class),
domains(Group, Domain).

labeling([]).
labeling([Class|Group]) :-
label(Class),
labeling(Group).

: I have to solve this in C linking it with PVM (Parallel Virtual Machine).
: I know Comp.Constraints and Comp.comp.prolog are the wrong newsgroup but I
: figured it was more likely that someone had seen a similar problem in this
: newsgroup rather than a C newsgroup.

I then took a PC (pentium 75) and ran the above code:

[user] ?- X is cputime, solution(Z), Y is cputime.

X       = 0.18
Z       = [[3,5,2,1,4],[3,4,1,2,5],[3,1,5,2,4],[4,2,3,1,5],[5,3,4,2,1]]
Y       = 0.21

As you see this problem solves in 0.03 secs, beat that on any parallel
machine in the world using any programming language you care to. I think
you will find that the inherent costs of trying to perform any kind of
search on a parallel machine will not give any benefit because the
costs in handing out data and the costs in sequencing the variables
which depend on eachother are too high.

: Once I get this solved I will move onto a more general program able to
: solve many Zebra like problems.

Of course if you want to run many Zebra problems in parallel then that
is easy! - try solving a large single one though.

Hope that was interesting.

Andrew

IF/Prolog Hotline Support,

marketing: Annette Kolb
technical: Dr. Andrew R. Verden,                   IF Computer GmbH,

Tel:    +49 89 7936 0037                           D-82065 Baierbrunn,
Fax:    +49 89 7936 0039                           Germany.

World Wide Web:  http://www.biz.isar.de/ifcomputer/

Mon, 03 Aug 1998 03:00:00 GMT

 Page 1 of 1 [ 5 post ]

Relevant Pages