In this post, we’ll tackle one the most famous puzzles in the world: The Zebra Puzzle, also known as Einstein’s riddle. Legend goes that Einstein invented the riddle himself, and that only 2% of people are able to solve it. I call bullshit on that.

It’s already widely accepted that Einstein didn’t invent the riddle. This post aims to show that with a little help from logic, everyone on Earth can reach the solution.

To follow this step by step, you’re expected to be familiar with boolean
algebra, especially the `XOR`

operator, and the notion of truth tables.

For a neat first contact with logic and boolean algebra, you can read my book **Computer Science Distilled**. It’s a slim intro to computer science that includes all these basic principles every programmer should know. Check it out!

Without further ado, let’s get to the problem. You’re given 15 clues and two questions:

- There are five houses.
- The Englishman lives in the red house.
- The Spaniard owns the dog.
- Coffee is drunk in the green house.
- The Ukrainian drinks tea.
- The green house is immediately to the right of the ivory house.
- The Old Gold smoker owns snails.
- Kools are smoked in the yellow house.
- Milk is drunk in the middle house.
- The Norwegian lives in the first house.
- The man who smokes Chesterfields lives in the house next to the man with the fox.
- Kools are smoked in the house next to the house where the horse is kept.
- The Lucky Strike smoker drinks orange juice.
- The Japanese smokes Parliaments.
- The Norwegian lives next to the blue house.

Who drinks water? Who owns the zebra?

## Mapping clues to boolean statements

We’ll use boolean variables that map attributes to house numbers. For instance,
clue #10 says “The Norwegian lives in the first house”. We represent this by
writing `Norway(1) ↔ True`

.

To model the riddle, we’ll make extensive use of the `XOR`

operator. For instance, we
don’t know where the Englishman lives, but we do know this statement is `True`

:

`English(2) XOR English(3) XOR English(4) XOR English(5)`

Because the Englishman must live in only one of the five houses (and we know it’s not the first one, because of clue #10).

### First 5 clues

Using the `XOR`

operator, we can easily model the first 5 clues:

`EnglishRed(1) XOR EnglishRed(2) XOR EnglishRed(3) XOR EnglishRed(4) XOR EnglishRed(5)`

`SpainDog(1) XOR SpainDog(2) XOR SpainDog(3) XOR SpainDog(4) XOR SpainDog(5)`

`GreenCoffee(1) XOR GreenCoffe(2) XOR GreenCoffe(3) XOR GreenCoffe(4) XOR GreenCoffe(5)`

`UkraineTea(1) XOR UkraineTea(2) XOR UkraineTea(3) XOR UkraineTea(4) XOR UkraineTea(5)`

### The 6th Clue

The 6th clue limits the possibilities of the Ivory house, and ties it to the Green one:

`(Ivory(1) AND GreenCoffe(2)) XOR (Ivory(2) AND GreenCoffe(3)) XOR (Ivory(3) AND GreenCoffe(4)) XOR (Ivory(4) AND GreenCoffee(5))`

### Clues 7 and 8

Our model is starting to become intimidatingly big, but let’s fear not and continue, adding rules for clue #7 and #8:

`OldSnail(1) XOR OldSnail(2) XOR OldSnail(3) XOR OldSnail(4) XOR OldSnail(5)`

`KoolsYellow(1) XOR KoolsYellow(2) XOR KoolsYellow(3) XOR KoolsYellow(4) XOR KoolsYellow(5)`

## Clues with literal knowledge

Next, clues 9, 10 and 15 give literal knowledge of the houses. Let’s represent that with a table:

1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|

? | Blue | ? | ? | ? |

Norway | ? | ? | ? | ? |

? | ? | Milk | ? | ? |

? | ? | ? | ? | ? |

? | ? | ? | ? | ? |

Using this knowledge, we can start to simplify our rules. For example, we now know the Norwegian lives in the first house, so `EnglishRed(1)`

can never be `True`

. For that reason, we can remove this term from the first rule. Following this reasoning, we simplify our model to this:

`EnglishRed(3) XOR EnglishRed(4) XOR EnglishRed(5)`

`SpainDog(2) XOR SpainDog(3) XOR SpainDog(4) XOR SpainDog(5)`

`GreenCoffee(1) XOR GreenCoffe(4) XOR GreenCoffe(5)`

`UkraineTea(2) XOR UkraineTea(4) XOR UkraineTea(5)`

`(Ivory(3) AND GreenCoffe(4)) XOR (Ivory(4) AND GreenCoffee(5))`

`OldSnail(1) XOR OldSnail(2) XOR OldSnail(3) XOR OldSnail(4) XOR OldSnail(5)`

`KoolsYellow(1) XOR KoolsYellow(3) XOR KoolsYellow(4) XOR KoolsYellow(5)`

## Slashing one of our rules

Take a close look at the 5th rule of our model. It says:

`(Ivory(3) AND GreenCoffe(4)) XOR (Ivory(4) AND GreenCoffee(5))`

This also tells us that `GreenCoffe(4) XOR GreenCoffee(5)`

is `True`

. This implies `GreenCoffee(1)`

must be False. Hence the 3rd rule of our model is redundant:

`GreenCoffee(1) XOR GreenCoffe(4) XOR GreenCoffe(5)`

Its information is already expressed by the 5th rule. We can thus rewrite our rules without this redundancy:

`EnglishRed(3) XOR EnglishRed(4) XOR EnglishRed(5)`

`SpainDog(2) XOR SpainDog(3) XOR SpainDog(4) XOR SpainDog(5)`

`UkraineTea(2) XOR UkraineTea(4) XOR UkraineTea(5)`

`(Ivory(3) AND GreenCoffe(4)) XOR (Ivory(4) AND GreenCoffee(5))`

`OldSnail(1) XOR OldSnail(2) XOR OldSnail(3) XOR OldSnail(4) XOR OldSnail(5)`

`KoolsYellow(1) XOR KoolsYellow(3) XOR KoolsYellow(4) XOR KoolsYellow(5)`

# Discovering house 1’s color by elimination

From the 1st rule, we see house 1 cannot be Red. From the 3rd rule, it’s clear it cannot be Green nor Ivory. And it can’t be Blue also, because that’s house 2’s color. This means house 1 can only be Yellow. Let’s update our table with this knowledge, and simplify our rules:

1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|

Yellow | Blue | ? | ? | ? |

Norway | ? | ? | ? | ? |

? | ? | Milk | ? | ? |

Kools | ? | ? | ? | ? |

? | ? | ? | ? | ? |

`EnglishRed(3) XOR EnglishRed(4) XOR EnglishRed(5)`

`SpainDog(2) XOR SpainDog(3) XOR SpainDog(4) XOR SpainDog(5)`

`UkraineTea(2) XOR UkraineTea(4) XOR UkraineTea(5)`

`(Ivory(3) AND GreenCoffe(4)) XOR (Ivory(4) AND GreenCoffee(5))`

`OldSnail(2) XOR OldSnail(3) XOR OldSnail(4) XOR OldSnail(5)`

## Mapping the remaining clues

At this point, we still have to consider clues 11—14. From our current state, rule 12 translates directly to new information. Let’s add it to the table:

1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|

Yellow | Blue | ? | ? | ? |

Norway | ? | ? | ? | ? |

? | ? | Milk | ? | ? |

Kools | ? | ? | ? | ? |

? | Horse | ? | ? | ? |

This new data in the table is used to further simplify our model:

`EnglishRed(3) XOR EnglishRed(4) XOR EnglishRed(5)`

`SpainDog(3) XOR SpainDog(4) XOR SpainDog(5)`

`UkraineTea(2) XOR UkraineTea(4) XOR UkraineTea(5)`

`(Ivory(3) AND GreenCoffe(4)) XOR (Ivory(4) AND GreenCoffee(5))`

`OldSnail(3) XOR OldSnail(4) XOR OldSnail(5)`

And here are the new rules from clues 11, 13 and 14:

`(Chester(2) AND Fox(1)) XOR (Chester(3) AND Fox(4)) XOR (Chester(4) AND Fox(3)) XOR (Chester(4) AND Fox(5)) XOR (Chester(5) AND Fox(4)`

`LuckyJuice(2) XOR LuckyJuice(4) XOR LuckyJuice(5)`

`JapanParliaments(2) XOR JapanParliaments(3) XOR JapanParliaments(4) XOR JapanParliaments(5)`

We’re done with the clues. Now we’ll use boolean algebra to transform our rules until they lead us to the solution.

## Simplifying the model

The 1st and the 4th rule can be combined: in the case the 3rd house is Ivory, then by the 4th rule, house #4 is green, and then there would be only house #5 left for red. Combining the rules,

`SpainDog(3) XOR SpainDog(4) XOR SpainDog(5)`

`UkraineTea(2) XOR UkraineTea(4) XOR UkraineTea(5)`

`(Ivory(3) AND GreenCoffe(4) AND EnglishRed(5)) XOR (Ivory(4) AND GreenCoffee(5) AND EnglishRed(3))`

`OldSnail(3) XOR OldSnail(4) XOR OldSnail(5)`

`(Chester(2) AND Fox(1)) XOR (Chester(3) AND Fox(4)) XOR (Chester(4) AND Fox(3)) XOR (Chester(4) AND Fox(5)) XOR (Chester(5) AND Fox(4)`

`LuckyJuice(2) XOR LuckyJuice(4) XOR LuckyJuice(5)`

`JapanParliaments(2) XOR JapanParliaments(3) XOR JapanParliaments(4) XOR JapanParliaments(5)`

## Big Truth Table

Since many or these terms are related via `XOR`

, the table can cover all valid
possibilities with less lines. Let’s mark lines that contains variables that
are incompatible with each other.

Rows A and B represent the validity of these two terms (taken from our 3rd rule):

- A:
`Ivory(3) AND GreenCoffe(4) AND EnglishRed(5)`

- B:
`Ivory(4) AND GreenCoffe(5) AND EnglishRed(3)`

OK? | EspDog(3) | EspDog(4) | EspDog(5) | UkrTea(2) | UkrTea(4) | UkrTea(5) | A | B |
---|---|---|---|---|---|---|---|---|

x | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 1 |

YES | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 1 |

YES | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 1 |

x | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 |

x | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 |

YES | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 1 |

x | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 1 |

x | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 1 |

x | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 1 |

YES | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 |

YES | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 0 |

x | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 0 |

x | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 0 |

x | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 |

x | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 0 |

x | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 0 |

x | 0 | 1 | 0 | 0 | 0 | 1 | 1 | 0 |

x | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 0 |

In all valid configurations, `UkraineTea(5)`

is `False`

, so we can remove that possibility from the model. Simplifying the rules:

`SpainDog(3) XOR SpainDog(4) XOR SpainDog(5)`

`UkraineTea(2) XOR UkraineTea(4)`

`(Ivory(3) AND GreenCoffe(4) AND EnglishRed(5)) XOR (Ivory(4) AND GreenCoffee(5) AND EnglishRed(3))`

`OldSnail(3) XOR OldSnail(4) XOR OldSnail(5)`

`(Chester(2) AND Fox(1)) XOR (Chester(3) AND Fox(4)) XOR (Chester(4) AND Fox(3)) XOR (Chester(4) AND Fox(5)) XOR (Chester(5) AND Fox(4)`

`LuckyJuice(2) XOR LuckyJuice(4) XOR LuckyJuice(5)`

`JapanParliaments(2) XOR JapanParliaments(3) XOR JapanParliaments(4) XOR JapanParliaments(5)`

## Assuming one of the variables is True to gain information

In the previous truth table, notice that there is only one line where `UkraineTea(2)`

is false. This line thus tells us that:

```
NOT(UkraineTea(2)) → SpainDog(5) AND Ivory(4) AND
GreenCoffee(5) AND UkranianTea(4)
```

If `UkraineTea(2)`

were to be false, we’d get a lot of info. So let’s suppose
`UkraineTea(2)`

is indeed false, and test if a solution can be found that way.
Let’s update the table with the information we’d directly gain:

1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|

Yellow | Blue | Red | Ivory | Green |

Norway | ? | English | Ukraine | Spain |

? | Juice | Milk | Tea | Coffee |

Kools | Lucky | ? | ? | ? |

? | Horse | ? | ? | Dog |

You see, now `LuckyJuice(4)`

and `LuckyJuice(5)`

cannot be true, meaning `LuckyJuice(2)`

must be true. However,
house #2 is the only left for Japan, which must be together with Parliaments.
We can’t fit Japan in any houses, meaning the problem cannot be solved down
this path.

This can only mean one thing: that the assumption we made is false. By
discovering this contradiction, we now know that `UkraineTea(2)`

is `True`

. So let’s
backtrack, add that info to the table and simplify our rules:

1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|

Yellow | Blue | ? | ? | ? |

Norway | Ukraine | ? | ? | ? |

? | Tea | Milk | ? | ? |

Kools | ? | ? | ? | ? |

? | Horse | ? | ? | ? |

`SpainDog(3) XOR SpainDog(4) XOR SpainDog(5)`

`(Ivory(3) AND GreenCoffe(4) AND EnglishRed(5)) XOR (Ivory(4) AND GreenCoffee(5) AND EnglishRed(3))`

`OldSnail(3) XOR OldSnail(4) XOR OldSnail(5)`

`LuckyJuice(4) XOR LuckyJuice(5)`

`JapanParliaments(3) XOR JapanParliaments(4) XOR JapanParliaments(5)`

## Finding more stuff by elimination

Notice juice and coffee are both only assignable to either house 4 or 5. This means house 1 must be the one that drinks water. We’ve solved the first part of the puzzle!

In a similar reasoning, the only available smoke to house #2 is Chester, since Lucky/Parliaments/Old must be given to among houses 3/4/5.

Updating our table, and simplifying our rules:

1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|

Yellow | Blue | ? | ? | ? |

Norway | Ukraine | ? | ? | ? |

Water | Tea | Milk | ? | ? |

Kools | Chester | ? | ? | ? |

? | Horse | ? | ? | ? |

`SpainDog(3) XOR SpainDog(4) XOR SpainDog(5)`

`(Ivory(3) AND GreenCoffe(4) AND EnglishRed(5)) XOR (Ivory(4) AND GreenCoffee(5) AND EnglishRed(3))`

`OldSnail(3) XOR OldSnail(4) XOR OldSnail(5)`

`Fox(1) XOR Fox(3)`

`LuckyJuice(4) XOR LuckyJuice(5)`

`JapanParliaments(3) XOR JapanParliaments(4) XOR JapanParliaments(5)`

## Trying another big truth table

Let’s make another truth table, with all smoke-related variables:

OK? | JpaPar(3) | JpaPar(4) | JpaPar(5) | OldSnail(3) | OldSnail(4) | OldSnail(5) | LuckyJuice(4) | LuckyJuice(5) |
---|---|---|---|---|---|---|---|---|

x | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 1 |

YES | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 |

x | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 1 |

YES | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 1 |

x | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 |

x | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 1 |

x | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 1 |

x | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 1 |

x | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 1 |

x | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 |

x | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 0 |

YES | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 0 |

x | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 0 |

x | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 |

x | 0 | 1 | 0 | 0 | 0 | 1 | 1 | 0 |

YES | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 0 |

x | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 0 |

x | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 0 |

Notice `JapanParliaments(4)`

is only valid in one line, so we can write:

`JapanParliaments(4) → OldSnail(3) AND LuckyJuice(5)`

If `JapanParliaments(4)`

is part of the solution, we gain a lot of knowledge. So
again, let’s assume it’s true and see if we find a solution. Directly adding
the new info to the table:

1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|

Yellow | Blue | Ivory | Green | Red |

Norway | Ukraine | ? | Japan | English |

Water | Tea | Milk | Coffee | Juice |

Kools | Chester | Old | Parliaments | Lucky |

? | Horse | Snail | ? | ? |

With juice in house 5, coffee can only go to house 4. With this,

`Ivory(3) AND GreenCoffe(4) AND EnglishRed(5)`

Would have to be true. With English on house 5, the only house left for the
Spanish is house #3. But the Spanish can’t go to house 3, because the snail
must be on it, and we know the Spanish has the dog. Therefore, this is another
contradiction: `JapanParliaments(4)`

must be `False`

.

Let’s backtrack once more, and incorporate this new info:

1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|

Yellow | Blue | ? | ? | ? |

Norway | Ukraine | ? | ? | ? |

Water | Tea | Milk | ? | ? |

Kools | Chester | ? | ? | ? |

? | Horse | ? | ? | ? |

`SpainDog(3) XOR SpainDog(4) XOR SpainDog(5)`

`(Ivory(3) AND GreenCoffe(4) AND EnglishRed(5)) XOR (Ivory(4) AND GreenCoffee(5) AND EnglishRed(3))`

`OldSnail(3) XOR OldSnail(4) XOR OldSnail(5)`

`Fox(1) XOR Fox(3)`

`LuckyJuice(4) XOR LuckyJuice(5)`

`JapanParliaments(3) XOR JapanParliaments(5)`

At this point, the riddle is nearly solved.

## Getting to the solution

Now, both the Japanese and the English must be on either house 3 or 5. This leaves only house 4 to the Spaniard:

1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|

Yellow | Blue | ? | ? | ? |

Norway | Ukraine | ? | Spain | ? |

Water | Tea | Milk | ? | ? |

Kools | Chester | ? | ? | ? |

? | Horse | ? | Dog | ? |

`(Ivory(3) AND GreenCoffe(4) AND EnglishRed(5)) XOR (Ivory(4) AND GreenCoffee(5) AND EnglishRed(3))`

`OldSnail(3) XOR OldSnail(5)`

`Fox(1) XOR Fox(3)`

`LuckyJuice(4) XOR LuckyJuice(5)`

`JapanParliaments(3) XOR JapanParliaments(5)`

Similarly, now we know that the Old smoker and the Parliaments smoker must be on houses 3/5. This means the Lucky smoker can only be on house 4:

1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|

Yellow | Blue | ? | ? | ? |

Norway | Ukraine | ? | Spain | ? |

Water | Tea | Milk | Juice | ? |

Kools | Chester | ? | Lucky | ? |

? | Horse | ? | Dog | ? |

`(Ivory(3) AND GreenCoffe(4) AND EnglishRed(5)) XOR (Ivory(4) AND GreenCoffee(5) AND EnglishRed(3))`

`OldSnail(3) XOR OldSnail(5)`

`Fox(1) XOR Fox(3)`

`JapanParliaments(3) XOR JapanParliaments(5)`

With this, there is only one place left for coffee: house 5. This means the following statement is true:

`EnglishRed(3) AND Ivory(4) AND GreenCoffee(5)`

Completing the table,

1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|

Yellow | Blue | Red | Ivory | Green |

Norway | Ukraine | English | Spain | ? |

Water | Tea | Milk | Juice | Coffee |

Kools | Chester | ? | Lucky | ? |

? | Horse | ? | Dog | ? |

Now there is only one place left for Japan, so:

1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|

Yellow | Blue | Red | Ivory | Green |

Norway | Ukraine | English | Spain | Japan |

Water | Tea | Milk | Juice | Coffee |

Kools | Chester | ? | Lucky | Parliaments |

? | Horse | ? | Dog | ? |

With this, now there is only one place left for the Old smoker and the Snail,

1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|

Yellow | Blue | Red | Ivory | Green |

Norway | Ukraine | English | Spain | Japan |

Water | Tea | Milk | Juice | Coffee |

Kools | Chester | Old Gold | Lucky | Parliaments |

? | Horse | Snail | Dog | ? |

That forces the fox to house 1. Finally, the zebra can only be on house 5:

1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|

Yellow | Blue | Red | Ivory | Green |

Norway | Ukraine | English | Spain | Japan |

Water | Tea | Milk | Juice | Coffee |

Kools | Chester | Old Gold | Lucky | Parliaments |

Fox | Horse | Snail | Dog | Zebra |

Voila! How did you like this solution? Do you have any suggestion to make it better? Did you get stuck or didn’t understand a particular step? Let me know in the comments below!

ong hf

Hi Wladston, I have a question on the second big truth table: can Lucky Strike and Parliament exist at house 5 at the same time? I am referring to the 4th and 5th YES in the table.

Wladston Filho

That is correct, Ong Hf! Thank you for spotting it. I fixed these two lines on the table.

carletex

Hi! I think there is a mistake in:

“To model the riddle, we’ll make extensive use of the XOR operator. For instance, we don’t know where the Englishman lives, but we do know this statement is True:

English(2) XOR English(2) XOR English(3) XOR English(5)”

I think it should be: English(2) XOR English(3) XOR English(4) XOR English(5)

Wladston Filho

You are right, @cartelex! Thanks for the heads up. I’ve fixed it :)