Zebra Puzzle

From Wikipedia, the free encyclopedia

The Zebra Puzzle is a well-known logic puzzle.

It is often called "Einstein's Puzzle" or "Einstein's Riddle" because it is said to have been invented by Albert Einstein as a boy. Some claim that Einstein said "only 2 percent of the world's population can solve it". It is also sometimes attributed to Lewis Carroll. However, there is no known evidence for Einstein's or Carroll's authorship.

There are several versions of this puzzle. The version below is quoted from the first known publication in Life International magazine on December 17, 1962. The March 25, 1963, issue contained the solution given below and the names of several hundred solvers from around the world.

Contents 1 The original puzzle 2 Discussion 3 Solution 3.1 Right-to-left solution 4 Other versions 5 References 6 External links

[edit] The original puzzle

1. There are five houses.
2. The Englishman lives in the red house.
3. The Spaniard owns the dog.
4. Coffee is drunk in the green house.
5. The Ukrainian drinks tea.
6. The green house is immediately to the right of the ivory house.
7. The Old Gold smoker owns snails.
8. Kools are smoked in the yellow house.
9. Milk is drunk in the middle house.
10. The Norwegian lives in the first house.
11. The man who smokes Chesterfields lives in the house next to the man with the fox.
12. Kools are smoked in the house next to the house where the horse is kept.
13. The Lucky Strike smoker drinks orange juice.
14. The Japanese smokes Parliaments.
15. The Norwegian lives next to the blue house.

Now, who drinks water? Who owns the zebra?

In the interest of clarity, it must be added that each of the five houses is painted a different color, and their inhabitants are of different national extractions, own different pets, drink different beverages and smoke different brands of American cigarettes. In statement 6, right refers to the reader's right.

[edit] Discussion

The premises leave out some details, notably that the houses are in a row.

Since neither water nor a zebra is mentioned in the clues, there exists a reductive solution to the puzzle, namely that no one owns a zebra or drinks water. If, however, the questions are read as “Given that one resident drinks water, which is it?” and “Given that one resident owns a zebra, which is it?” then the puzzle becomes a non-trivial challenge to inferential logic. (A frequent variant of the puzzle asks “Who owns the fish?”)

It is possible not only to deduce the answers to the two questions but to figure out who lives where, in what color house, keeping what pet, drinking what drink, and smoking what brand of cigarettes.

Rule 12 leads to a contradiction. It should have read "Kools are smoked in a house next to the house where the horse is kept." (Note "a" instead of "the.") The text above has been kept as it is, as it is meant to be a presentation of the text of the puzzle as originally published.

Rule 11 suffers from a similar problem as that just described regarding rule 12.

[edit] Solution

house	1	2	3	4	5
color	yellow	blue	red	ivory	green
nationality	Norwegian	Ukrainian	Englishman	Spaniard	Japanese
drink	water	tea	milk	orange juice	coffee
smoke	Kools	Chesterfield	Old Gold	Lucky Strike	Parliament
pet	fox	horse	snails	dog	zebra

Here are some deductive steps that you can follow to derive the solution. A useful method is to try to fit known relationships into a table and eliminate possibilities. Key deductions are in italics.

STEP 1

We are told the Norwegian lives in the 1st house (10). It does not matter whether this is counted from the left or from the right. We just need to know the order, not the direction.

From (10) and (15), the 2nd house is Blue. What color is the 1st house? Not Green or Ivory, because they have to be next to each other (6). Not Red, because the Englishman lives there (2). Therefore the 1st house is Yellow.

It follows that Kools are smoked in the 1st house (8) and the Horse is kept in the 2nd house (12).

So what is drunk by the Norwegian in the 1st, Yellow, Kools-filled house? Not Tea since the Ukrainian drinks that (5). Not Coffee since that is drunk in the Green house (4). Not Milk since that is drunk in the 3rd house (9). Not Orange Juice since the drinker of Orange Juice smokes Lucky Strikes (13). Therefore it is Water (the missing beverage) that is drunk by the Norwegian.

STEP 2

So what is smoked in the 2nd, Blue house where we know a Horse is also kept?

Not Kools which are smoked in the 1st house (8). Not Old Gold since that house must have Snails (7).

Let's suppose Lucky Strikes are smoked here, which means Orange Juice is drunk here (13). Then consider: Who lives here? Not the Norwegian since he lives in the 1st House (10). Not the Englishman since he lives in a Red house (2). Not the Spaniard since he owns a dog (3). Not the Ukrainian since he drinks tea (4). Not the Japanese who smokes Parliaments (14). Since this is an impossible situation, Lucky Strikes are not smoked in the 2nd house.

Let's suppose Parliaments are smoked here, which means the Japanese man lives here (14). Then consider: What is drunk here? Not Tea since the Ukrainian drinks that (4). Not Coffee since that is drunk in the Green house (4). Not Milk since that is drunk in the 3rd house (9). Not Orange Juice since the drinker of that smokes Lucky Strike (13). Again, since this is an impossible situation, Parliaments are not smoked in the 2nd house.

Therefore, Chesterfields are smoked in the 2nd house.

So who smokes Chesterfields and keeps a Horse in the 2nd, Blue house? Not the Norwegian who lives in the 1st House (10). Not the Englishman who lives in a Red house (2). Not the Spaniard who owns a dog (3). Not the Japanese who smokes Parliaments (14). Therefore, the Ukrainian lives in the 2nd House, where he drinks Tea (5).

STEP 3

Since Chesterfields are smoked in the 2nd house, we know from (11) that the Fox is kept in either the 1st house or the 3rd house.

Let us first assume that the Fox is kept in the 3rd house. Then consider: what is drunk by the man who smokes Old Golds and keeps Snails (7)? We have already ruled out Water and Tea from the above steps. It cannot be Orange Juice since the drinker of that smokes Lucky Strikes (13). It cannot be Milk because that is drunk in the 3rd house (9), where we have assumed a Fox is kept. This leaves Coffee, which we know is drunk in the Green house (4).

So if the Fox is kept in the 3rd house, then someone smokes Old Golds, keeps Snails and drinks Coffee in a Green house. Who can this person be? Not the Norwegian who lives in the 1st house (10). Not the Ukrainian who drinks Tea (5). Not the Englishman who lives in a Red house (2). Not the Japanese who smokes Parliaments (14). Not the Spaniard who owns a Dog (3).

This is impossible. So it follows that the Fox is not kept in the 3rd house, but in the 1st house.

STEP 4

From what we have found so far, we know that Coffee and Orange Juice are drunk in the 4th and 5th houses. It doesn't matter which is drunk in which; we will just call them the Coffee house and the Orange Juice house.

So where does the man who smokes Old Gold and keeps Snails live? Not the Orange Juice house since Lucky Strike is smoked there (13).

Suppose this man lives in the Coffee house. Then we have someone who smokes Old Gold, keeps Snails and drinks Coffee in a Green (4) house. Again, by the same reasoning in STEP 3, this is impossible.

Therefore, the Old Gold-smoking, Snail-keeping man lives in the 3rd house.

It follows that Parliaments are smoked in the Green, Coffee-drinking house, by the Japanese man (14). This means the Spaniard must be the one who drinks Orange Juice, smokes Lucky Strikes and keeps a Dog. By extension, the Englishman must live in the 3rd house, which is Red. By process of elimination, the Spaniard's house is the Ivory one.

By now we have filled in every 'blank' except one, and it is clear that the Japanese is the one who keeps the Zebra.

[edit] Right-to-left solution

The above solution assumed that the first house is the leftmost house. If we assume that the first house is the rightmost house, we find the following solution. Again the Japanese keeps the Zebra, and the Norwegian drinks water.

house	5	4	3	2	1
color	ivory	green	red	blue	yellow
nationality	Spaniard	Japanese	Englishman	Ukrainian	Norwegian
drink	orange juice	coffee	milk	tea	water
smoke	Lucky Strike	Parliament	Old Gold	Chesterfield	Kools
pet	dog	zebra	snails	horse	fox

[edit] Other versions

There are two versions of the puzzle:^[1]

• The British lives in the red house.
• The Swedish keeps dogs as pets.
• The Danish drinks tea.
• The green house is on the left of the white house.
• The green homeowner drinks coffee.
• The person who smokes Pall Mall rears birds.
• The owner of the yellow house smokes Dunhill.
• The man living in the center house drinks milk.
• The Norwegian lives in the first house.
• The man who smokes Blend lives next to the one who keeps cats.
• The man who keeps the horse lives next to the man who smokes Dunhill.
• The owner who smokes Bluemaster drinks beer.
• The German smokes prince.
• The Norwegian lives next to the blue house.
• The man who smokes Blend has a neighbor who drinks water.

Question: Who owns the fish?

1. The Englishman lives in the red house

2. The Spaniard owns the dog

3. coffee is drunk in the green house

4. The Ukrainian drinks tea

5. The green house is immediately to the right of the ivory house

6. The ford driver owns the snail

7. A Toyota driver lives in the yellow house

8. Milk is drunk in the middle house

9. The Norwegian lives in the first house to the left

10. The man who drives the Chevy lives in the house next to the man with the fox

11. A Toyota is parked next to the house where the horse is kept

12. The dodge owner drinks orange juice

13. The Japanese owns a Porche

14. The Norwegian lives next to the blue house

Differences to the original puzzle:

1. Some colors, nationalities, cigarette brands and pets are substituted for other ones and the clues are given in different order. These do not change the "logic" of the puzzle.
2. One rule says that the green house is on the left of the white house, instead of on the right of it. This change has the same effect as numbering the houses from right to left instead of left to right (see section Right-to-left solution above). It results only in swapping of the two corresponding houses with all their properties, but makes the puzzle a bit easier.
3. The clue "The man who smokes Blend has a neighbor who drinks water" is redundant and therefore makes the puzzle even less difficult. Originally, this clue was only in form of the question "Who drinks water?"

When given to children, the cigarette brands are often replaced by snacks eaten in each house^[2] or some other set of clues.

[edit] References

1. ^ Einstein's Riddle!, naute.com
2. ^ i.e. in this 2004 forum post

[edit] External links

• Generator of logic puzzles similar to the Zebra Puzzle
• SWI Prolog Solution
• Oz/Mozart Solution
• Common Lisp and C/C++ solutions
• C# solution
• English solution (PDF) - structured as a group activity for teaching English as a foreign language