Solving the Zebra Puzzle with Boolean Algebra

Because anyone can solve this tricky puzzle.

May 27, 2021May 26, 2017 by Wladston Filho

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.

XOR gates look a little bit like Zebras. I think.

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

Wladston Filho

About the author: Wlad holds a master's degree in computer science, and is the author of Computer Science Distilled and Computer Science Unleashed, which explain the basics of using computers to solve interesting problems.

44 thoughts on “Solving the Zebra Puzzle with Boolean Algebra”

ong hf

8 years ago at

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.
Reply
- Wladston Filho
  
  8 years ago at
  
  That is correct, Ong Hf! Thank you for spotting it. I fixed these two lines on the table.
  Reply
carletex

7 years ago at

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)
Reply
- Wladston Filho
  
  7 years ago at
  
  You are right, @cartelex! Thanks for the heads up. I’ve fixed it :)
  Reply
Anthony

7 years ago at

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 …”
Reply
- Wladston Filho
  
  7 years ago at
  
  Hi Anthony! Yes, you are correct, thanks for spotting this problem! I’ve just fixed it here.
  Reply
Andrei

7 years ago at

Hello! In the first truth table how did you find out if a possibility is ok or not ?
Reply
- Wladston Filho
  
  7 years ago at
  
  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.
  Reply
Ruben

7 years ago at
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:
1. For the first 9 rows we’re trying to confirm that A evaluates to false and B evaluates to true.
2. For the last 9 rows we’re trying to confirm that A evaluates to true and B evaluates to false.
3. The first row is invalid, because B evaluates to false because EspDog(3) causes EnglishRed(3) to be false.
4. The second row is valid, because neither EspDog(4) nor UkrTea(2) cause B to be false. A isn’t necessarily true either with these values so I’m guessing that’s why this row is valid?
5. With this logic I’m wondering why row 5 is invalid. In this row EspDog(4) and UkrTea(4) are true, but that doesn’t make B false nor does it make A true right?
A second thing I noticed is that from this clue:
1. The man who smokes Chesterfields lives in the house next to the man with the fox.
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))
Reply
- Wladston Filho
  
  7 years ago at
  
  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!
  Reply
  - Ruben
    
    7 years ago at
    
    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. :)
    Reply
Title

7 years ago at

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?
Reply
- Wladston Filho
  
  7 years ago at
  
  Hi! About the “next to” rule, you’re correct, that bit was missing. I’ve just edited the article to fix it, thanks!
  Reply
  - Title
    
    7 years ago at
    
    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.
    Reply
    - Wladston Filho
      
      7 years ago at
      
      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.
      Reply
Title

7 years ago at

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)
Reply
- Wladston Filho
  
  7 years ago at
  
  Yes, you are right, one variable was missing from the sentence. I’ve fixed it, thanks!
  Reply
Jeff

7 years ago at

I’ve been chewing on this for a few days and finally worked through it. Thanks!
Reply
- Wladston Filho
  
  7 years ago at
  
  Yay! Do you have any hints on how can I make the article easier for people to follow?
  Reply
Amir

7 years ago at

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?
Reply
- Wladston Filho
  
  7 years ago at
  
  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.
  Reply
Parker

7 years ago at
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.
- the big truth table was established according to the followings:
  - 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))
- you simplified the third rule as A XOR B, where
  - A represents the Ivory(3) AND GreenCoffe(4) AND EnglishRed(5), and
  - B represents the Ivory(4) AND GreenCoffe(5) AND EnglishRed(3)
- so there’re total 8 variables, I understood that you assumed A is false and B is true for the first 9 rows, then reverse their value for the last 9 rows.
- then I’m confused how did you establish all the possibilities for the rest of 6 propositions, and also confused why their values are in different patterns, where the true value of EspDog were placed diagonally, and the value of UkrTea were placed in different ways.
- these seems a little bit different from the concept of truth table from your book.
Looking forward to hearing from you.

Regards,
Parker
Reply
- Wladston Filho
  
  7 years ago at
  
  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 ;-)
  Reply
  - Parker
    
    7 years ago at
    
    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.
    Reply
Kote Isaev

7 years ago at

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!
Reply
- Wladston Filho
  
  6 years ago at
  
  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.
  Reply
Arsalan Ali

4 years ago at

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?
Reply
- Wladston Filho
  
  4 years ago at
  
  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!
  Reply
Stanislav

4 years ago at

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.
Reply
- Wladston Filho
  
  4 years ago at
  
  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.
  Reply
  - Stanislav
    
    4 years ago at
    
    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’.
    Reply
    - Wladston Filho
      
      4 years ago at
      
      Thanks! Let me know if you have ideas on how we can further improve the explanation. Cheers!
      Reply
Javier

4 years ago at

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.
Reply
- Wladston Filho
  
  4 years ago at
  
  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,
  Reply
motasem

3 years ago at

why xor , why not or ,
English(2) or English(3) or English(4 ) or English(5 )
Reply
- Wladston Filho
  
  3 years ago at
  
  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.
  Reply
Alexander

1 year ago at

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?
Reply
- Wladston Filho
  
  1 year ago at
  
  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!
  Reply
Marco

10 months ago at

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.
Reply
- Wladston Filho
  
  10 months ago at
  
  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!
  Reply
Vadym Boiko

6 months ago at

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.”.
Reply
- Wladston Filho
  
  6 months ago at
  
  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?
  Reply
Andrew

3 months ago at

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
Reply
Andrew

3 months ago at

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 :)
Reply