Einstein’s Puzzle (einstein)

Run LPL Code  ,  PDF Document

Problem

Albert Einstein supposedly wrote this quiz. The puzzle is as follows:

1. There are 5 houses in five different colors.

2. In each house lives a person with a different nationality.

3. These 5 owners drink a certain drink, smoke a certain brand of tobacco and keep a certain pet.

4. No owner has the same pet, smokes the same tobacco, or drinks the same drink.

The question is: Who owns the fish supposing the following 15 conditions hold?

1. The Briton lives in the red house

2. The Swede keeps dogs as pets

3. The Dane drinks tea

4. The green house is adjacent on the left of the white house

5. The green house owner drinks coffee

6. The person who smokes Pall-Mall raises birds

7. The owner of the yellow house smokes Dunhill

8. The man living in the house right in the center drinks milk

9. The Norwegian lives in the first house

10. The man who smokes Marlboros lives next to the one who keeps cats

11. The man who keeps horses lives next to the one who smokes Dunhill

12. The owner who smokes Bluemaster drinks juice

13. The German smokes Prince

14. The Norwegian lives next to the blue house

15. The man who smokes Marlboro has a neighbor who drinks water.

Modeling Steps

The rules seem to suggest that the five houses are ordered in a line, since they use words like left next to and first. Hence, we define five positions and try to assign the five attributes (nationality, color, animal, beverage, and cigar) to the five positions. (Instead of “positions” we may imagine five parcel of land with the houses aligned in a line, and we try to place the five attributes on them.)

We introduce a variable for each attribute defining a permutation. For example, the variable A_a is a variable indexed by a set of nationalities :

The word alldiff means that the variables are integer and their values are different for each a. Since the values are bounded by [1..5], this notation can be used for a permutation. The assignment A₃ = 2, for example, means that the Briton (A₃) is at position (in house) 2.

For each attribute, a similar variable –defining a permutation– is introduced. The 15 rules are now easy to write as constraints. Rule 1 (The Briton lives in the red house) can be stated as follows: “The house of the Briton (=A₃) must be the same as the house that is red (=B₃)”.

model einstein "Einstein's Puzzle"; 
 
  set a := [Norwegian, Dane, Briton, Swede, German]; 
 
      b := [yellow blue red green white]; 
 
      c := [cat bird dog horse fish]; 
 
      d := [coffee tea milk juice water]; 
 
      e := [Dunhill Marlboro 'Pall-Mall' Bluemaster Prince]; 
 
  alldiff variable 
 
     A{a} [1..5]; B{b} [1..5]; C{c} [1..5]; 
 
     D{d} [1..5]; E{e} [1..5]; 
 
  constraint 
 
     R1:  A[3]=B[3];  -- or: A['Briton'] = B['red']; 
 
     R2:  A[4]=C[3]; 
 
     R3:  A[2]=D[2]; 
 
     R4:  B[4]+1=B[5]; 
 
     R5:  B[4]=D[1]; 
 
     R6:  E[3]=C[2]; 
 
     R7:  D[3]=3; 
 
     R8:  B[1]=E[1]; 
 
     R9:  A[1]=1; 
 
     R10: E[2]=C[1]+1 or E[2]=C[1]-1; 
 
     R11: C[4]=E[1]+1 or C[4]=E[1]-1; 
 
     R12: E[4]=D[4]; 
 
     R13: B[2]=2;     -- A[1]=B[2]+1 or A[1]=B[2]-1; 
 
     R14: A[5]=E[5]; 
 
     R15: E[2]=D[5]+1 or E[2]=D[5]-1; 
 
  solve; 
 
  Write{a|A[a]=C[5]}('The %s owns the fish' n', a); 
 
end

Solution

This puzzle can be solved easily, supposing we are proceeding in a systematic way. We draw five houses on a piece of paper in a linear array and place (writing) the attributes into the houses one after the other.

Supposing that “the first” means “the leftmost”, rule 9 says to place the Norwegian in the first house. Rule 13 says to place “blue” in the second house (the second house is blue). Rule 7 says to place “milk” in the third house. Rule 4 says that the white house is right to the green one and green is in the same than “coffee” (according to rule 5), then “green” must be assigned to house 4 and “white” to house 5 (see Figure 1).

Next, since the Briton must be in the “red” house, this means that they are in house 3 (rule 1), and then “yellow” and “Dunhill” are in house 1 (rule 8). It follows that according to rule 11 “horse” must be in house 2 (see Figure 2).

Now, the Dane drinks tea (rule 3). Hence, he can only be in house 2 or 5. However, the Swede has a dog (rule 2), so he cannot be in house 2. Therefore The Dane must be in house 2 and the Swede in house 5. But this means that the German is in house 4 and Prince too (rule 14). Furthermore, the juice-drinker who smokes Bluemaster must be in house 5 (see Figure 3).

Since the bird-keeper smokes Pall-Mall (rule 6), he must live in house 3. And so we are left with one possibility for “Marlboro” (house 2). Since the cat is left or right to Marlboro (rule 10), the cat must be in house 1. And finally the “fish” is in house 4. Hence the German has the fish, which solves the puzzle (see Figure 4).

In applying the rules in a certain well given order, and by some trivial steps, we can solve the puzzle easily. The key to the solution is to apply the rules in a given order as shown and to do certain “bookkeeping”. There is no need to “branch” or to consider alternative solution pathes. It is remarkable that the puzzle can be solved in a linear straightforward way.

Questions

1. Is there another solution to the puzzle?

2. Apparently it is assumed that the order of the houses is to be counted left to right. Thus the condition “the Norwegian lives in the first house” would presume that the Norwegian lives in the leftmost house. However, there is another solution of the problem, if we assume a “right-to-left” ordering and “the first” means “the rightmost”. Find the solution!

3. One also could argue that rule 4 does not say that the green house is immediately left to the white house. It just says that the green house is anywhere left to the white house. Change the formulation accordingly!

Answers

1. No! It is the unique solution (under the given constraints). To convince yourself, add the constraint that the German does not own the fish (C₅≠A₅) and solve it. The solver says that the problem now is infeasible, saying that there is no solution, when the fish is not owned by the German.

2. The only requirement we need to change is rule 9 (R9). Instead of A₁ = 1, we state it as A₁ = 5. However, now there is no solution.

3. All we need to do is to change R4 from (B₄+1 = B₅) to (B₄+1 ≤ B₅). In this case, the solution is not unique anymore. The fish could also be owned by the Norwegian or the Dane.

References