Solving "Who owns the Zebra" programmatically?

Question

Edit: this puzzle is also known as "Einstein's Riddle"

The Who owns the Zebra (you can try the online version here) is an example of a classic set of puzzles and I bet that most people on Stack Overflow can solve it with pen and paper. But what would a programmatic solution look like?

Based on the clues listed below...

• There are five houses.
• Each house has its own unique color.
• All house owners are of different nationalities.
• They all have different pets.
• They all drink different drinks.
• They all smoke different cigarettes.
• The English man lives in the red house.
• The Swede has a dog.
• The Dane drinks tea.
• The green house is on the left side of the white house.
• They drink coffee in the green house.
• The man who smokes Pall Mall has birds.
• In the yellow house they smoke Dunhill.
• In the middle house they drink milk.
• The Norwegian lives in the first house.
• The man who smokes Blend lives in the house next to the house with cats.
• In the house next to the house where they have a horse, they smoke Dunhill.
• The man who smokes Blue Master drinks beer.
• The German smokes Prince.
• The Norwegian lives next to the blue house.
• They drink water in the house next to the house where they smoke Blend.

...who owns the Zebra?

Solution 1

Here's a solution in Python based on constraint-programming:

from constraint import AllDifferentConstraint, InSetConstraint, Problem

# variables
colors        = "blue red green white yellow".split()
nationalities = "Norwegian German Dane Swede English".split()
pets          = "birds dog cats horse zebra".split()
drinks        = "tea coffee milk beer water".split()
cigarettes    = "Blend, Prince, Blue Master, Dunhill, Pall Mall".split(", ")

# There are five houses.
minn, maxn = 1, 5
problem = Problem()
# value of a variable is the number of a house with corresponding property
variables = colors + nationalities + pets + drinks + cigarettes
problem.addVariables(variables, range(minn, maxn+1))

# Each house has its own unique color.
# All house owners are of different nationalities.
# They all have different pets.
# They all drink different drinks.
# They all smoke different cigarettes.
for vars_ in (colors, nationalities, pets, drinks, cigarettes):
    problem.addConstraint(AllDifferentConstraint(), vars_)

# In the middle house they drink milk.
#NOTE: interpret "middle" in a numerical sense (not geometrical)
problem.addConstraint(InSetConstraint([(minn + maxn) // 2]), ["milk"])
# The Norwegian lives in the first house.
#NOTE: interpret "the first" as a house number
problem.addConstraint(InSetConstraint([minn]), ["Norwegian"])
# The green house is on the left side of the white house.
#XXX: what is "the left side"? (linear, circular, two sides, 2D house arrangment)
#NOTE: interpret it as 'green house number' + 1 == 'white house number'
problem.addConstraint(lambda a,b: a+1 == b, ["green", "white"])

def add_constraints(constraint, statements, variables=variables, problem=problem):
    for stmt in (line for line in statements if line.strip()):
        problem.addConstraint(constraint, [v for v in variables if v in stmt])

and_statements = """
They drink coffee in the green house.
The man who smokes Pall Mall has birds.
The English man lives in the red house.
The Dane drinks tea.
In the yellow house they smoke Dunhill.
The man who smokes Blue Master drinks beer.
The German smokes Prince.
The Swede has a dog.
""".split("\n")
add_constraints(lambda a,b: a == b, and_statements)

nextto_statements = """
The man who smokes Blend lives in the house next to the house with cats.
In the house next to the house where they have a horse, they smoke Dunhill.
The Norwegian lives next to the blue house.
They drink water in the house next to the house where they smoke Blend.
""".split("\n")
#XXX: what is "next to"? (linear, circular, two sides, 2D house arrangment)
add_constraints(lambda a,b: abs(a - b) == 1, nextto_statements)

def solve(variables=variables, problem=problem):
    from itertools  import groupby
    from operator   import itemgetter

    # find & print solutions
    for solution in problem.getSolutionIter():
        for key, group in groupby(sorted(solution.iteritems(), key=itemgetter(1)), key=itemgetter(1)):
            print key, 
            for v in sorted(dict(group).keys(), key=variables.index):
                print v.ljust(9),
            print

if __name__ == '__main__':
    solve()

Output:

1 yellow    Norwegian cats      water     Dunhill  
2 blue      Dane      horse     tea       Blend    
3 red       English   birds     milk      Pall Mall
4 green     German    zebra     coffee    Prince   
5 white     Swede     dog       beer      Blue Master

It takes 0.6 seconds (CPU 1.5GHz) to find the solution.
The answer is "German owns zebra."

---

To install the constraint module via pip: pip install python-constraint

To install manually:

• download:

  $ wget https://pypi.python.org/packages/source/p/python-constraint/python-constraint-1.2.tar.bz2#md5=d58de49c85992493db53fcb59b9a0a45

• extract (Linux/Mac/BSD):

  $ bzip2 -cd python-constraint-1.2.tar.bz2 | tar xvf -

• extract (Windows, with 7zip):

  > 7z e python-constraint-1.2.tar.bz2
  > 7z e python-constraint-1.2.tar

• install:

  $ cd python-constraint-1.2
  $ python setup.py install

Solution 2

In Prolog, we can instantiate the domain just by selecting elements from it :) (making mutually-exclusive choices, for efficiency). Using SWI-Prolog,

select([A|As],S):- select(A,S,S1),select(As,S1).
select([],_). 

left_of(A,B,C):- append(_,[A,B|_],C).  
next_to(A,B,C):- left_of(A,B,C) ; left_of(B,A,C).

zebra(Owns, HS):-     % (* house: color,nation,pet,drink,smokes *)
  HS   = [ h(_,norwegian,_,_,_),    h(blue,_,_,_,_),   h(_,_,_,milk,_), _, _], 
  select([ h(red,brit,_,_,_),       h(_,swede,dog,_,_), 
           h(_,dane,_,tea,_),       h(_,german,_,_,prince)], HS),
  select([ h(_,_,birds,_,pallmall), h(yellow,_,_,_,dunhill),
           h(_,_,_,beer,bluemaster)],                        HS), 
  left_of( h(green,_,_,coffee,_),   h(white,_,_,_,_),        HS),
  next_to( h(_,_,_,_,dunhill),      h(_,_,horse,_,_),        HS),
  next_to( h(_,_,_,_,blend),        h(_,_,cats, _,_),        HS),
  next_to( h(_,_,_,_,blend),        h(_,_,_,water,_),        HS),
  member(  h(_,Owns,zebra,_,_),                              HS).

Runs quite instantly:

?- time( (zebra(Who,HS), writeln(Who), nl, maplist(writeln,HS), nl, false 
          ; writeln("no more solutions!") )).
german

h( yellow, norwegian, cats,   water,  dunhill   )
h( blue,   dane,      horse,  tea,    blend     )
h( red,    brit,      birds,  milk,   pallmall  )
h( green,  german,    zebra,  coffee, prince    )   % (* formatted by hand *)
h( white,  swede,     dog,    beer,   bluemaster)

no more solutions!
% (* 1,706 inferences, 0.000 CPU in 0.070 seconds (0% CPU, Infinite Lips) *)
true.

Solution 3

One poster already mentioned that Prolog is a potential solution. This is true, and it's the solution I would use. In more general terms, this is a perfect problem for an automated inference system. Prolog is a logic programming language (and associated interpreter) that form such a system. It basically allows concluding of facts from statements made using First Order Logic. FOL is basically a more advanced form of propositional logic. If you decide you don't want to use Prolog, you could use a similar system of your own creation using a technique such as modus ponens to perform the draw the conclusions.

You will, of course, need to add some rules about zebras, since it isn't mentioned anywhere... I believe the intent is that you can figure out the other 4 pets and thus deduce the last one is the zebra? You'll want to add rules that state a zebra is one of the pets, and each house can only have one pet. Getting this kind of "common sense" knowledge into an inference system is the major hurdle to using the technique as a true AI. There are some research projects, such as Cyc, which are attempting to give such common knowledge through brute force. They've met with an interesting amount of success.

Solution 4

SWI-Prolog compatible:

% NOTE - This may or may not be more efficent. A bit verbose, though.
left_side(L, R, [L, R, _, _, _]).
left_side(L, R, [_, L, R, _, _]).
left_side(L, R, [_, _, L, R, _]).
left_side(L, R, [_, _, _, L, R]).

next_to(X, Y, Street) :- left_side(X, Y, Street).
next_to(X, Y, Street) :- left_side(Y, X, Street).

m(X, Y) :- member(X, Y).

get_zebra(Street, Who) :- 
    Street = [[C1, N1, P1, D1, S1],
              [C2, N2, P2, D2, S2],
              [C3, N3, P3, D3, S3],
              [C4, N4, P4, D4, S4],
              [C5, N5, P5, D5, S5]],
    m([red, english, _, _, _], Street),
    m([_, swede, dog, _, _], Street),
    m([_, dane, _, tea, _], Street),
    left_side([green, _, _, _, _], [white, _, _, _, _], Street),
    m([green, _, _, coffee, _], Street),
    m([_, _, birds, _, pallmall], Street),
    m([yellow, _, _, _, dunhill], Street),
    D3 = milk,
    N1 = norwegian,
    next_to([_, _, _, _, blend], [_, _, cats, _, _], Street),
    next_to([_, _, horse, _, _], [_, _, _, _, dunhill], Street),
    m([_, _, _, beer, bluemaster], Street),
    m([_, german, _, _, prince], Street),
    next_to([_, norwegian, _, _, _], [blue, _, _, _, _], Street),
    next_to([_, _, _, water, _], [_, _, _, _, blend], Street),
    m([_, Who, zebra, _, _], Street).

At the interpreter:

?- get_zebra(Street, Who).
Street = ...
Who = german

Solution 5

Here's how I'd go about it. First I'd generate all the ordered n-tuples

(housenumber, color, nationality, pet, drink, smoke)

5^6 of those, 15625, easily manageable. Then I'd filter out the simple boolean conditions. there's ten of them, and each of those you'd expect to filter out 8/25 of the conditions (1/25 of the conditions contain a Swede with a dog, 16/25 contain a non-Swede with a non-dog). Of course they're not independent but after filtering those out there shouldn't be many left.

After that, you've got a nice graph problem. Create a graph with each node representing one of the remaining n-tuples. Add edges to the graph if the two ends contain duplicates in some n-tuple position or violate any 'positional' constraints (there's five of those). From there you're almost home, search the graph for an independent set of five nodes (with none of the nodes connected by edges). If there's not too many, you could possibly just exhaustively generate all the 5-tuples of n-tuples and just filter them again.

This could be a good candidate for code golf. Someone can probably solve it in one line with something like haskell :)

afterthought: The initial filter pass can also eliminate information from the positional constraints. Not much (1/25), but still significant.

View more solutions

Comments

[Davnor]

Good point about the "common sense" rules. I remember getting very tied up with this years ago when interpreting the phrase "the house next to the house" - does that imply there's only one? It's not obvious.

[Adam Rosenfield]

For code golf, a solution could technically just print out the answer, making it equivalent to a "Hello world" code golf. You'd have to generalize the problem to get an interesting code golf, and this doesn't generalize trivially.

[Josh]

Dude cyc has been in dev for decades without any type of revolutionary method. Kinda sad, would be neat to see the brute force approach win out over associative models.

[Davnor]

Point taken :) My haskell is verbose but my score was out of the park anyway :)

[Karl]

There's no need to use TinyURL here, is there? They all look like rickrolls to me.

[mercator]

I wouldn't call that incorrect. The only constraint it violates is that the green house isn't left of the white house. But that's because of the way you defined that constraint and can easily be fixed. The link in the question even allows your solution given the murky definition of "left of."

[Harish2k22]

I'm not familiar with python, but I think "(minn + maxn) // 2" should read "(minn + maxn) / 2" - Thanks for the solution. I'm very impressed with the language.

[jfs]

@LFSR Consulting: '//' is always an integer division: '3//2 == 1'. '/' could be float division '3/2 == 1.5' (in Python 3.0 or in presence of 'from future import division') or could be an integer division (like in C) '3/2 == 1' on old Python version without 'from future import division'.

[Josh Smeaton]

We used CLIPS at uni to deduce this kind of information in our AI course.

[MidnightLightning]

I think your 5^6 assessment of possible solutions is off. I believe the number of possible combinations of 'i' items within 'm' categories should be (i!)^(m-1). For example, the five options for color could be arranged 5! ways. Providing the house numbers category stays in the same order, the other 5 categories could each be arranged that way as well, meaning the possible combinations are (5!)^5 or 24,883,200,000; quite a bit higher than 15,625, and making a brute-force attack much harder to tackle.

[Nick Larsen]

15,625 is accurate based on his solution strategy. If you wanted to assign every possible state for all variables, it would be much larger, but he is choosing to build only partial states, chip away at them, then use another technique to put together the final answer.

[AxA]

This is the first constraint program I looked at. As many pointed out your python implementation is impressive. It is really cute how you avoided hand codifying the constraints with the use of add_constraints(), and_statements, and nextto_statements.

[jfs]

I've fixed the expired tinyurl.

[approxiblue]

@LamonteCristo Wayback machine to the rescue.

[Ben Burns]

Is there any reason not to pip install python-constraint ? I did just that a moment ago and it appears to give the expected output.

[jfs]

@BenBurns: no reason. The answer was written in 2008. If you've tested it and it produces the same result then you could update the installation instructions and the corresponding links to the docs (it doesn't change the essential aspects of the answer -- you are free to edit it).

[false]

neighbor(X,Y) :- abs(X-Y) #= 1.

[miracle173]

I like this. I did not expect that this direct attack would be feasible.