Zebra Puzzle

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. It is often claimed that only 2% of the population can solve it. The puzzle is also sometimes attributed to Lewis Carroll. However, there is no known evidence for Einstein's or Carroll's authorship and the Life International puzzle cited below mentions brands of cigarette, such as Kools, that did not exist during Carroll's lifetime or Einstein's boyhood.

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

Text of the Life International 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 cigarets [sic]. One other thing: in statement 6, right means your right.

— Life International, December 17, 1962

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. However, it is not possible to deduce the answer without making an assumption that is not part of the original rule set.

Since the clues mention neither water nor a zebra, a reductive solution exists—namely that no one owns a zebra or drinks water. If, however, you read the questions as, "Given that one resident drinks water, which is it?" and, "Given that one resident owns a zebra, which is it?"—the puzzle poses a significant challenge to inferential logic. (A frequent variant of the puzzle asks "Who owns the fish?".)

Rule 12 leads to a contradiction, and should strictly have been written as "Kools are smoked in a house next to the house where the horse is kept," as opposed to the house—since the implies that there is only one house next to the house with the horse, meaning it is either the leftmost or the rightmost house. Similarly, the solution is unique even if we don't assume there is only one house next to the fox in clue 11. However, in this case, it is extra unnecessary information, rather than a contradiction, as in clue 12.

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 deductive steps that can 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 first house (10). We count from left to right, which is itself an assumption.

From (10) and (15), the second house is blue. What color is the first house? Not green or ivory, because they must be next to each other (6 and the second house is blue). Not red, because the Englishman lives there (2). Therefore the first house is yellow.

It follows that Kools are smoked in the first house (8) and the Horse is kept in the second house (12).

So what is drunk by the Norwegian in the first, 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 third 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 second, blue house where we know a Horse is also kept?

Not Kools that are smoked in the first 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 first 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 second 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 (5). Not coffee since that is drunk in the green house (4). Not milk since that is drunk in the third 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 second house.

Therefore, Chesterfields are smoked in the second house.

So who smokes Chesterfields and keeps a Horse in the second, blue house? Not the Norwegian who lives in the first 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 second House, where he drinks tea(5)!

Step 3

Since Chesterfields are smoked in the second house, we know from (11) that the fox is kept in either the first house or the third house.

Let us first assume that the fox is kept in the third 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 third 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 third 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 first 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 third house, but in the first house.

Step 4

From what we have found so far, we know that coffee and orange juice are drunk in the fourth and fifth houses. It doesn't matter which is drunk in which; we 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 third 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 third house, which is red. By process of elimination, the Spaniard's house is the ivory one.

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

Another method:

Now we are left with House number 4 and 5. For simplicity let's first check what are the possible answers for house 4 and 5:

• Colors - Green, Ivory
• Nationality - Spaniard, Japanese
• Drinks - Orange juice, Coffee
• Smokes - Parliament, Lucky Strike
• Pets - Dog, Zebra

If we continue to follow our simple logic of deduction, by (6) we can say that the fourth house cannot be Green-colored, as it must be next to the Ivory-colored house, which makes the fourth House Ivory-colored. Therefore the only option left is that the House is 5 and color is Green. So the fifth House is Green.

Similarly by (4) - Coffee is drunk in fifth House, the Green House. Therefore Orange juice, the only drink left, must be drunk in fourth House. By (13) fourth House Person smokes Lucky Strike, which implies that the fifth House Person smokes Parliaments. By (14), the fifth House Person is Japanese, which makes the fourth House Person Spanish. By (3), the fourth House owner owns a Dog, which makes the only remaining animal Zebra for the fifth house.

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. In fact, everything is the same apart from the characters' house numbers.

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

A different method of solving the puzzle

The above solution uses a trial and error approach in several places. It requires assumptions that prove correct or incorrect. An alternate method does not rely on testing assumptions but can prove each step from information already known.

First complete step one above.

Most of the items that have not yet been allocated to a house can be paired using the information in the question. A few remain unpaired (Ivory, Zebra, Fox, Horse and Chesterfield).

It can be seen that there are three unknowns in house two, the nationality, drink and cigarette. These unknowns must be either one pair and one unpaired item or three unpaired items.

Excluding pairs and unpaired items that contain a color or animal (as these are already known for house two) we are left with:

Ukrainian – Tea (5)

Orange Juice – Lucky Strike (13)

Japanese – Parliament (14)

Chesterfield

As Chesterfield is the only single, and there must be a single, Chesterfields must be smoked in house two. Then, eliminating the pairs with a cigarette, only Ukrainian– Tea is left, so these must be in house two also.

We are told that "The man who smokes Chesterfields lives in the house next to the man with the fox" (11), therefore the fox must be at house one.

The only thing we know about house three is that milk is drunk there. The four unknown facts must consist of 2 pairs. Nothing is known about houses four or five so they must each contain two pairs and one single item. There are two single items that have not yet been allocated to a house (Ivory and Zebra). Ivory must be to the left of Green (6) so house five cannot be Ivory. Therefore house four is Ivory and house five has a Zebra.

As the Green house is to the right of Ivory the Green house must be house five. As coffee is drunk in the Green house we know that Coffee is drunk in house five also.

House three is now the only house for which the color hasn’t been identified and so it must be Red, and therefore lived in by the English man (2). Then, taking the four unused pairs and eliminating those that contain one of the categories already known for house three we can see that house three must have Snails and Old Gold.

The same procedure can be followed to complete the information for house five and the two remaining pairs must relate to house four.

Alternative approach using a more narrative style

This method is similar in spirit with the one described in the enclosing section: use only the known facts from the list and use deduction only to obtain the solution (no trial and error). But instead of relying on reasoning about paired and unpaired facts, we use a more narrative style.

The only assumption (aside from the missing drink and animal being water and zebra, respectively) we need to make is about the ordering of houses. We assume left to right ordering (i.e. the first house is the leftmost one), but the reasoning can easily be adapted for the other way round.

Step 1

Same as step 1 above.

Step 2

Who can live in the second, the blue, house? First, we note that the Japanese cannot drink water (as we deduced the Norwegian drinks this), nor tea (5) nor orange juice (13), as he does not smoke Lucky Strike. So, the Japanese drinks either coffee (4) or milk (9), which also means he is either in the green house or in the middle house - and we know the second house (the blue one) is neither green nor in the middle. So, the Japanese cannot reside in the blue house, which leaves us only with the Ukrainian.

So what does the Ukrainian smoke? It cannot be Kool (8 taken by Norwegian), nor Old Gold (7 we now know the Ukrainian owns the horse), nor Lucky Strike (13, 5 the Ukrainian drinks tea), nor Parliaments (14). Thus he smokes Chesterfields.

Step 3

We can now assign the remaining 2 cigarette brands to the respective nationality: Since Old Gold is smoked by the snails owner (7), the Spaniard cannot smoke the brand (3 he owns a dog). Thus the English smokes Old Gold (and owns snails) and the Spaniard smokes Lucky Strike.

Step 4

We deduced in the previous step that the Spaniard smokes Lucky Strike, which implies he drinks orange juice (13). With this, the only unassigned drinks left are coffee and milk. Since the Englishman lives in the red house (2), he cannot be the one drinking coffee in the green house (4). Thus, the Englishman drinks milk in the middle house (9), which is red (2). And so, the Japanese drinks coffee in the green house (4).

Now we assigned all the drinks, and we also can assign the missing houses. We just concluded that the Englishman lives in the middle, red house and the Japanese in the green house. The ivory house is the only one left unassigned, and it must be the Spaniard's. Furthermore, since the green house is to the right of the ivory house (6) it is the last (i.e. rightmost) house, and we now have the order of houses (from left to right): yellow, blue, red, ivory, green.

Step 5

What is left to do is to assign the remaining 2 animals (fox, zebra) to their respective owners (Norwegian, Japanese) (we deduced in step 2 that the Ukrainian owns the horse, and in step 3 that the Englishman owns snails, and we already know that the Spaniard owns a dog (3)).

We know that the "man who smokes Chesterfields lives in the house next to the man with the fox" (11). The Ukrainian smokes Chesterfields and is neighbors with the Norwegian, but not with the Japanese. Thus, the Norwegian owns the fox and the Japanese owns the zebra.

Sudoku like solution

There is one very simple, but time consuming solution. It looks like solving Sudoku. You have to create a table for all possible parameters assuming the houses are in a line.

1	2	3	4	5	Order of the houses
N1	N1	N1	N1	N1	- nationality
N2	N2	N2	N2	N2	- nationality
N3	N3	N3	N3	N3	- nationality
N4	N4	N4	N4	N4	- nationality
N5	N5	N5	N5	N5	- nationality
CB1	CB1	CB1	CB1	CB1	- cigarette brand
CB2	CB2	CB2	CB2	CB2	- cigarette brand
CB3	CB3	CB3	CB3	CB3	- cigarette brand
CB4	CB4	CB4	CB4	CB4	- cigarette brand
CB5	CB5	CB5	CB5	CB5	- cigarette brand

... and you continue like this until you add all the remaining possibilities ( 5 rows for each ). After this you just circulate through the rules until you delete all remaining conflicts. Example: You know that nationality 1 lives in the first house, so you delete second to fifth N1s in the first row in the nationality quadrant, and also since there can only be one nationality in one house, you delete N2 to N5 in the first column of this quadrant. You continue this way, deleting possibilities proven not possible until you know every position. This is simple, but time consuming.

Other versions

Other versions of the puzzle have one or more of the following differences to the Life International puzzle:

1. Some colors, nationalities, cigarette brands, drinks, 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. It is also important to note that the omission of the word immediately, as in immediately to the left/right of the white house, leads to multiple solutions to the puzzle.
3. In versions where Blend replaces Chesterfields, the clue "The man who smokes Blend has a neighbor who drinks water" is redundant and therefore makes the puzzle even easier. In the Life International version, this clue was only in form of the question "Who drinks water?"
4. In other versions, the smokes are replaced by cars or sports.

External links

• corresponding entry on Opencog's wiki
• programming task on Rosetta code