language-agnostic - 以编程方式解决 "Who owns the Zebra"问题？

Question

编辑:这个谜题也被称为“爱因斯坦之谜”

Who owns the Zebra (you can try the online version here) 是一组经典谜题的一个例子，我敢打赌 Stack Overflow 上的大多数人都可以用笔和纸解决它。但程序化解决方案会是什么样子呢？

根据下面列出的线索...

• 有五栋房子。
• 每栋房子都有自己独特的颜色。
• 所有房主都来自不同的国籍。
• 他们都有不同的宠物。
• 他们都喝不同的饮料。
• 他们都抽不同的香烟。
• 英国人住在红房子里。
• 瑞典人有一只狗。
• 丹麦人喝茶。
• 绿房子位于白宫的左侧。
• 他们在温室里喝咖啡。
• 抽 Pall Mall 烟的人有鸟。
• 在黄色房子里，他们抽烟登喜路。
• 在中间的房子里，他们喝牛奶。
• 挪威人住在第一栋房子里。
• 抽 Blend 烟的男人住在养猫的房子旁边。
• 在他们养马的房子旁边的房子里，他们抽烟登喜路。
• 抽 Blue Master 烟的男人喝啤酒。
• 德国人抽 Prince 烟。
• 挪威人住在蓝房子旁边。
• 他们在抽 Blend 烟的房子旁边的房子里喝水。

...谁拥有斑马？

Answer 1

这是一个基于约束编程的 Python 解决方案:

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)。
答案是“德国人拥有斑马。”

<小时/>

安装constraint module通过pip: pip 安装 python-constraint

手动安装:

• 下载:

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

• 提取(Linux/Mac/BSD):

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

• 提取(Windows，使用 7zip ):

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

• 安装:

  $ cd python-constraint-1.2
  $ python setup.py安装