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 4th 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(2) AND Fox(3)) 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(2) AND Fox(3)) 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(2) AND Fox(3)) 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) AND EnglishRed(3)
```

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!

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.

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

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)

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

Hi,

I think the wrong rule is referred to in the second sentence under “Discovering house 1’s color by elimination”. It reads “From the 3rd rule, it’s clear it cannot be Green nor Ivory”. I think it should read “From the 4th rule …”

Hi Anthony! Yes, you are correct, thanks for spotting this problem! I’ve just fixed it here.

Hello! In the first truth table how did you find out if a possibility is ok or not ?

Hi Andrei! We check for contractions. For instance, in the first row, both EnglishRed(3) and EspDog(3) are set to True, and that can’t be because house 3 can’t host both the English and the Spaniard.

Can you elaborate more on how to evaluate the big truth table? Please correct me if I’m wrong, but I was thinking it works like this:

A second thing I noticed is that from this clue:

you create this rule:

(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))

Isn’t this missing (Chester(2) AND Fox(3))

Hi! You are correct, in that first row, both EnglishRed(3) and EspDog(3) are set to True, that can’t be, because house 3 can’t host both the English and the Spaniard. The second row has no such conflicts, so it’s a valid row. In the 4th row, EnglishRed(3) and EspDog(3) are also set to True (like in the first row), so that row too is invalid. In each row, A is True when it’s set to 1, and False when set to zero. This means A is always True in rows 1-9, and False in the other rows. What we are doing here is covering all possible scenarios for A, B and the other variables, and checking which of these possibilities could actually happen. About the “next to” rule, I’m considering that the house of the Fox must be the house of the Chesterfields “+1”. I could also include (Chester(2) AND Fox(3)) and it would still make the problem solvable, though. Do you have suggestions to edit the text to make it clearer? Let me know!

Hi Wladston,

Thanks for your reply. I think it’s clear to me now. Just wanted to confirm that I was interpreting things the right way. :)

Hello,

I think there is something missing from the following statement.

“(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)”

This was written in the section called “Big truth table”

I think there should be (Chester(2) AND Fox(3)) in the model as well.

Am I missing something?

Hi! About the “next to” rule, you’re correct, that bit was missing. I’ve just edited the article to fix it, thanks!

Thank you for your response. I also bought your book “Com sci distilled”. It is awesome. It makes the complicated com sci a lot easier to me. I am new to programming. I started coding about 6 months ago. Do you have any further recommendation what book I should read?

Thanks in advance.

Thank you so much for buying my book :) I’m happy to know you enjoyed it. Well, there are tons of excellent books out there, it all depends on what you want to specialize in… I believe a nice book for this stage you are, would be one that covers some of the more technical aspects and little important details of the programming language you’re currently working with.

NOT(UkraineTea(2)) → SpainDog(5) AND Ivory(4) AND

GreenCoffee(5) AND UkranianTea(4)

This is from the “Assuming one of the variables is True to gain information”

I think there is something missing.

NOT(UkraineTea(2)) → SpainDog(5) AND Ivory(4) AND

GreenCoffee(5) AND UkranianTea(4) AND EnglishRed(3)

Yes, you are right, one variable was missing from the sentence. I’ve fixed it, thanks!

I’ve been chewing on this for a few days and finally worked through it. Thanks!

Yay! Do you have any hints on how can I make the article easier for people to follow?

hi, this article was very helpful for me, and I appreciate that. but, I have a problem. I need to change this article to a code in c++ or c language, but I do not know how . can you help me?

That can be tricky indeed. I recommend downloading the dictionary file manually, that helps a lot. Then focus only on printing the first 10 words of the dictionary. Then, expand your code to print the first 10 words with 5 characters. Then for the set, you can use the Set data structure in the C++ STL. That’s the best way to get things done: incrementally, and step-by-step.

Hello,

I’ve trouble to understand how did you establish the first big truth table. so far here are my understandings, please feel free to correct me if I were wrong.

Looking forward to hearing from you.

Regards,

Parker

Hi Parker! Yes, you are right about the things you wrote in your comment. I’ll try to better explain the steps needed to construct the table:

Step 1: Start with columns`A`

and`B`

, and two rows:`A = 1, B = 0`

and`A = 0, B = 1`

. We don’t need to include the other two states (`A = 1, B = 1`

and`A = 0, B = 0`

) because we know that`A XOR B`

is true.Step 2: Add three`UkraineTea`

columns. To cover all valid possibilities, for each of the current rows, we need to add three possible states:`UkraineTea(2) = 1`

,`UkraineTea(4) = 1`

and`UkraineTea(5) = 1`

. With this, we’ll have`2 * 3 = 6`

rows.Step 3: Add three`SpainDog`

columns. It’s the same process: for each existing column, we now have three possible valid states:`SpainDog(3) = 1`

,`SpainDog(4) = 1`

,`SpainDog(5) = 1`

. This gives us the final`6 * 3 = 18`

rows.You could in theory construct a classical truth table as explained in the book, but since we have 8 columns, the table would have

`2^8 = 256`

rows, so it’s not practical to do it by hand. I should have indeed explained in better detail the steps involved in building a truth table with`XOR`

columns–in these cases we can discard a lot of rows when creating the table.If we were creating the “classical” truth table, adding three columns would require us to add

`2^3 = 8`

new rows to cover all possibilities. Since we know the XOR of the three columns is True, we know that there are only three possible states for these columns, so we only grow our table by a factor of three. I’ll try covering this with another example in the 2nd edition of the book.Was the confusing part made clear? Let me know ;-)

Hello, thanks for the detail explanations , it’s helpful. :)

Looking forward to the second edition of your book, I bought the first edition, it’s amazing.

Hello!

I was not able to understand one aspect of all this:

How to apple filled truth table to rules…

BTW, Bought your Comp. Science Distilled book, that is how I knew about the puzzle :)

I know about other similar puzzle, where question is “whom pets are gold fishes?”. I was able that puzzle without the truth tables and boolean rules, but I wanted fully follow this new approach and actually got stuck with this part.

Thanks for your interesting book!

Thanks for getting my book :) The approach on building truth tables with XOR statements is somewhat different in this blog post. Where can I find this other simpler riddles? Maybe it would indeed be easier to introduce readers with a simpler problem, indeed.

Just want to ask that some people have solved it in much more easier terms then this comprehensive solution via inference only. Is there a possibility that we can simplify this entire solution that meets those simplified answers by others?

Hi Arsalan! The main point of this article is to present a solution that can be reached by using only boolean logic, to exemplify the fact that if you’re patient and careful, even the hardest problems can be solved with boolean logic. If you have suggestions on how we can simplify the steps that lead to the solution while also only using bolean logic, please let us know!

Hi Wladston.

I tried to solve this riddle by myself and successfully eliminated all the statements up to “Slashing one of our rules” where I got stuck and decided to take a hint. And your answer raised a few questions.

How do you know that this rule ‘tells us’ that (B xor D) is True? How did you came to that knowledge?

After analysis I came to conclusion that you probably transformed rule 5 to another equivalent form, but I fail to see how.

For me it’s not so obvious to ‘see’ that (A and B) xor (C and D) can be transformed to (A xor C) and (B xor D) to ‘tells us’ that (B xor D) must be true.

Can you clarify, please.

Thanks.

Hi Stanislav, sure! From (A and B) xor (C and D), we know either (A and B) is true, or (C and D) is true. but not both. If we don’t care about what happens to A / C, we can deduce B xor D. I know this explanation maybe wasn’t the best, so I urge you to go to https://www.dcode.fr/boolean-truth-table, and input “(A and B) xor (C and D)”. Generate the truth table, and you’ll see it’s equivalent to the truth table of “B xor D”, once you eliminate the columns for A / C. Let me know if that solves your question.

Thanks Wladston. I thought about transformations, while process in fact was simplier. Need to think about it a bit, still have few things which I don’t quite get.

And I stand corrected because my analysis was wrong. After generalizing to variables I forgot about meaning.

Original equation (A(3) and B(4)) xor ((A(4) and B(5))) models situation that ‘B is immediately right of A’ (in terms of sequence).

But after generalization and transformation to “equivalent” form, equation changed it’s meaning.

Equation (A(3) xor A(4)) and (B(4) xor B(5)) is not the same as original. Now it models ‘B is right of A’.

Thanks! Let me know if you have ideas on how we can further improve the explanation. Cheers!

Hi Stanislav, following the question Ruben asked 3 years ago, I think that I understand why row 5 is invalid in the first Big Truth Table. Having EspDog(4) and UkrTea(4) does not make A necessarily false, therefore row 5 is invalid.

In the same way, why is row 11 valid? Having EspDog(4) and UkrTea(2) does not make B necessarily false, therefor, to my understanding row 11 should be invalid, right?

I also fail to understand why rows 16 and17 are invalid. In row 16, EspDog(3) makes B false because EnglishRed(3) is not possible, UkrTea(5) also indicates that B is false because GreenCoffee(5) is not possible, but there is no reason why A is necessarily false, therefore is okay to put A as true. To my understanding row 16 should be valid.

Same thing with row 17, UkrTea(5) makes B false, and I don’t see any reason for having A as false, therefor if A is true, row 17 should also be valid.

Could you please clarify?

Many thanks.

Hi Javier,

Notice that on row 11, B is zero, meaning it is false. That’s why the line is valid, it assumes B is false!

The idea is to try all possible settings on all variables, and figure out which ones would be possible without raising any conflicts.

I think with this understanding, you’ll be able to figure out rest of the rows. Please, let me know if it still doesn’t make sense.

Thanks a lot,

why xor , why not or ,

English(2) or English(3) or English(4 ) or English(5 )

Because the Englishman can only be in one house. English(2) or English(3) would evaluate to true in case the Englishman lived in both houses 1 and 2; and that isn’t allowed by the problem.

Hello!

Can anyone please tell me why in case of the Big Truth Table #1 we’re using just clues for EspDog and UkrTea and none of the others? Why don’t we use OldSnail or JapanParliaments?

Hi Alexander! One could have chosen any of the rules that appear in the list inside the “Simplifying the model” section. We chose to model the 3rd rule from the list as a truth table, because it seemed like analyzing it would yield some information. The 5th rile would also probably yield something as well, but since it was larger, we didn’t chose to model it on a truth table, as it would make the article more difficult for readers to follow. Please let me know if you have more questions!

I understand that this example is intended to demonstrate how formal logic can be applied to solve this problem. However, there’s a much faster method involving a sheet of paper or an Excel table. Organize the table so that the rows represent the nationalities (e.g., Englishman, Ukrainian, etc.), and the columns represent all other elements (houses, drinks, etc.).

Simply work through the clues multiple times, marking cells with ‘T’ when you’re absolutely certain, and marking ‘F’ for other cells in the same column and row within that block. For instance, if the Japanese person smokes Parliament, place a ‘T’ at the intersection of the Japanese row and the Parliament column, then mark ‘F’ in the same row for all other cigarette brands and in the Parliament column for other nationalities.

Repeat this process with the list of clues until you’re left with only about 5 clues (as was the case for me). At this point, the problem becomes a manageable tree of possibilities, each with several steps (or tree depth). It becomes significantly easier to check each branch one by one, or, in the case of a computer algorithm, to traverse a tree with just a few branches, than to work through the entire ‘logic calculation’ as initially suggested.

This method—resolving the unambiguous clues first until the point of branching, thus greatly simplifying the puzzle before starting tree traversal—is my preferred approach to solving such puzzles.

Hi Marco, thank you for your comment! It seems like it’s a strategy that would work. Would you be willing to publish a guest article here in our blog?Then you can explain this alternate solution step by step, and we can link it here for everyone to know!

Please explain this table to me:

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

For example: What does “OK?” or “A and B” mean and these numbers are “1,” “2.”.

Hi! “OK” means that the line is a possibility that doesn’t violate the rules. And the number “3” in “EspDog(3)” means that the person from Spain that has the dog is in house 3. For example, in the first row of the table, notice that the B statement is set to True, and that EspDog(3) is also set to True. This is incompatible, because the statement B requires “EnglishRed(3)” to be true. That’s because the 3rd house can’t be occupied by both the person from England and the person from Spain at the same time. Did you get it?

Hello everyone At first, I solved the problem like a Sudoku and could not figure out at what point I should use the truth table, even after I decided. I was afraid of calculations :) Thanks for the detailed review of the solution using Boolean algebra

– Excuse my English

If someone is interested in my decision: starting from the stage in the article where the truth table is used, I went the other way. You can already find out who drinks water at this stage if you look at the Norwegian. He can’t drink tea, because a Ukrainian drinks it, a Norwegian can’t drink coffee, because they drink it in 4 or 5 houses, and orange juice is drunk by a person who smokes another brand of cigarettes.

Next, you can check the position of the ivory house (on 3 or 4). If on the third, then we come to a contradiction, if on the fourth, then he can easily solve the problem :)