Solving "Who owns the Zebra" programmatically?

Question

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

The Who owns the Zebra 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?

Answer 1

Sounds like a job for declarative programming! Prolog, anyone? ...

Answer 2

Here's a solution using NSolver: Einstein’s Riddle in C#

Here is an excerpt:

//The green house's owner drinks coffee
Post(greenHouse.Eq(coffee));
//The person who smokes Pall Mall rears birds 
Post(pallMall.Eq(birds));
//The owner of the yellow house smokes Dunhill 
Post(yellowHouse.Eq(dunhill));

Answer 3

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.

Answer 4

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.

Answer 5

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:

• download:

  $ wget http://labix.org/download/python-constraint/python-constraint-1.1.tar.bz2

• extract:

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

• install:

  $ cd python-constraint-1.1

  $ python setup.py install

Answer 6

Here is a Prolog solution: http://en.literateprograms.org/Zebra_Puzzle_(Prolog). This page contains a link to another Prolog solution as well.

Answer 7

In PAIP (Chapter 11), Norvig solves the zebra puzzle using a Prolog embedded in Lisp.

Answer 8

This is really a constraint solving problem. You can do it with a generalized kind of constraint propagation in logic-programming like languages. We have a demo specifically for the Zebra problem in the ALE (attribute logic engine) system:

http://www.cs.toronto.edu/~gpenn/ale.html

Here's the link to the coding of a simplified Zebra puzzle:

http://www.cs.toronto.edu/~gpenn/ale/files/grammars/baby.pl

To do this efficiently is another matter.