解决“谁拥有斑马"以编程方式? [英] Solving "Who owns the Zebra" programmatically?

问题描述

这个难题也被称为爱因斯坦之谜"

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

• 有五个房子.
• 每所房子都有自己独特的颜色.
• 所有房主都来自不同国籍.
• 他们都有不同的宠物.
• 他们都喝不同的饮料.
• 他们都抽不同的香烟.
• 英国人住在红房子里.
• 瑞典人有一只狗.
• 丹麦人喝茶.
• 温室在白宫的左侧.
• 他们在温室里喝咖啡.
• 在颇尔购物中心吸烟的人有鸟.
• 他们在黄色的房子里抽烟登喜路.
• 他们在中间房子里喝牛奶.
• 挪威人住在第一所房子.
• 吸烟Blend的人住在有猫的房子旁边的房子里.
• 在他们有马的房子旁边的房子里，他们抽着Dunhill烟.
• 抽蓝大师烟的男人喝啤酒.
• 德国人抽王子.
• 挪威人住在蓝房子旁边.
• 他们在抽烟的房子旁边的房子里喝水.

• 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?

推荐答案

以下是基于约束编程的Python解决方案:

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

输出:

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

找到解决方案需要0.6秒(CPU 1.5GHz).
答案是德国人拥有斑马线".

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

要通过pip安装 constraint模块: pip安装python-constraint

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

要手动安装:

• 下载:

• download:

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

解压缩(Linux/Mac/BSD):

extract (Linux/Mac/BSD):

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

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

解压缩(Windows，带有 7zip ):

extract (Windows, with 7zip):

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

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

安装:

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

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

这篇关于解决“谁拥有斑马"以编程方式?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！