Solving the Zebra Puzzle with Boolean Algebra

Because anyone can solve this tricky puzzle.

|

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:

  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.

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!

Read Next

Comments

  1. 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

  2. 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

  3. 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

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

    Reply

    • 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

  5. 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

    • 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

      • 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

  6. 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

      • 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

        • 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

  7. 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

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

    Reply

  9. 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

    • 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

  10. 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.
    Reply

    • 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

      • 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

  11. 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

    • 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

Speak your mind

Your email address will not be published. Required fields are marked *