[解決済み] シマウマは誰のものか」をプログラムで解決する？

質問

Edit: このパズルは、アインシュタインの謎（Einstein's Riddle）とも呼ばれます。

このパズルは シマウマは誰のもの？ (あなたは オンライン版を試すにはこちら は古典的なパズルの一例で、Stack Overflowにいるほとんどの人がペンと紙で解くことができるに違いありません。しかし、プログラムによる解決策はどのようなものでしょうか?

以下に挙げるヒントに基づいて...

• 5つの家があります。
• 各家にはそれぞれ固有の色があります。
• すべての家の所有者は異なった国籍である。
• 彼らはすべて異なるペットを飼っています。
• 彼らはすべて異なる飲み物を飲む。
• 彼らは皆、異なる煙草を吸う。
• イギリス人は赤い家に住んでいる。
• スウェーデン人は犬を飼っている。
• デーン人は紅茶を飲む。
• 緑の家は、白い家の左側にあります。
• 緑の家でコーヒーを飲む。
• ポールモールを吸っている人は鳥を飼っている。
• 黄色い家で、彼らはダンヒルを吸う。
• 真ん中の家では、彼らは牛乳を飲む。
• 最初の家にノルウェー人が住んでいます。
• ブレンドの煙草を吸う男は、猫のいる家の隣の家に住んでいる。
• 馬を飼っている家の隣の家では、ダンヒルを吸っている。
• ブルーマスターを吸っている人は、ビールを飲む。
• ドイツ人はプリンスを吸っている。
• ノルウェー人は青い家の隣に住んでいます。
• 彼らはブレンドを吸う家の隣の家で水を飲みます。

...シマウマの持ち主は？

どのように解決するには？

制約プログラミングに基づく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 モジュール を経由して pip : pip install 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 | tar xvf -.

• を展開する (Windowsでは 7zip ):

  7z で python-constraint-1.2.tar.bz2 を圧縮します。
  
  > 7z python-constraint-1.2.tar。

• をインストールします。

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