129

編集: このパズルは「アインシュタインのなぞなぞ」としても知られています

The Who owns the Zebra (ここでオンライン バージョンを試すことができます) は古典的なパズル セットの例であり、Stack Overflow のほとんどの人はペンと紙で解決できるに違いありません。しかし、プログラマティック ソリューションはどのようなものになるでしょうか。

以下の手がかりに基づいて...

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

...ゼブラの所有者は誰ですか?

4

15 に答える 15

164

制約プログラミングに基づく 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

手動でインストールするには:

于 2008-11-26T14:59:07.210 に答える
49

Prolog では、ドメインから要素を選択するだけでドメインをインスタンス化できます:) (効率のために、相互に排他的な選択を行います)。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).

非常に瞬時に実行されます:

?- 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.
于 2011-11-25T14:19:20.113 に答える
16

あるポスターは、Prolog が潜在的なソリューションであると既に述べています。これは真実であり、私が使用するソリューションです。より一般的に言えば、これは自動推論システムにとって完璧な問題です。Prolog は、そのようなシステムを形成する論理プログラミング言語 (および関連するインタープリター) です。基本的に、一次論理を使用して作成されたステートメントから事実を結論付けることができます。FOL は基本的に、命題論理のより高度な形式です。Prolog を使用したくない場合は、modus ponensなどの手法を使用して独自に作成した同様のシステムを使用して、結論を導き出すことができます。

もちろん、どこにも言及されていないので、シマウマに関するいくつかのルールを追加する必要があります... 意図は、他の4匹のペットを把握し、最後の1匹がシマウマであると推測できることだと思いますか? シマウマはペットの 1 つであり、各家には 1 匹のペットしか飼えないというルールを追加する必要があります。この種の「常識」の知識を推論システムに組み込むことは、この技術を真の AI として使用するための大きなハードルです。力ずくでそのような共通知識を与えようとしている Cyc などの研究プロジェクトがいくつかあります。彼らは興味深い成功を収めました。

于 2008-11-25T21:45:57.437 に答える
15

SWI-Prolog 互換:

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

通訳で：

?- get_zebra(Street, Who).
Street = ...
Who = german
于 2011-11-01T02:32:38.563 に答える
13

これが私がそれについて行く方法です。最初に、順序付けされたすべての n-タプルを生成します

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

それらの 5^6、15625、簡単に管理できます。次に、単純なブール条件を除外します。それらは 10 個あり、それぞれが条件の 8/25 を除外すると予想されます (条件の 1/25 には犬と一緒のスウェーデン人が含まれ、16/25 には犬以外の犬と一緒の非スウェーデン人が含まれます)。 . もちろん、それらは独立したものではありませんが、それらをフィルタリングした後、多くは残っていないはずです.

その後、素敵なグラフの問題があります。各ノードが残りの n タプルの 1 つを表すグラフを作成します。両端の n タプル位置に重複が含まれている場合、または「位置」制約に違反している場合は、グラフにエッジを追加します (そのうちの 5 つがあります)。そこからほぼ家に帰り、グラフを検索して、5 つのノードからなる独立したセットを探します (エッジで接続されたノードはありません)。あまり多くない場合は、n タプルの 5 タプルをすべて網羅的に生成し、それらを再度フィルタリングすることができます。

これは、コード ゴルフの有力な候補となる可能性があります。誰かがおそらくhaskellのようなもので一行で解決できるでしょう:)

後付け:最初のフィルター パスでは、位置制約から情報を削除することもできます。それほど多くはありませんが (1/25)、それでも重要です。

于 2008-11-25T21:45:50.587 に答える
9

別の Python ソリューション。今回は Python の PyKE (Python Knowledge Engine) を使用します。確かに、@JFSebastian によるソリューションで Python の「制約」モジュールを使用するよりも冗長ですが、この種の問題に対する生の知識エンジンを調べている人にとって興味深い比較を提供します。

手がかり.kfb

categories( POSITION, 1, 2, 3, 4, 5 )                                   # There are five houses.
categories( HOUSE_COLOR, blue, red, green, white, yellow )              # Each house has its own unique color.
categories( NATIONALITY, Norwegian, German, Dane, Swede, English )      # All house owners are of different nationalities.
categories( PET, birds, dog, cats, horse, zebra )                       # They all have different pets.
categories( DRINK, tea, coffee, milk, beer, water )                     # They all drink different drinks.
categories( SMOKE, Blend, Prince, 'Blue Master', Dunhill, 'Pall Mall' ) # They all smoke different cigarettes.

related( NATIONALITY, English, HOUSE_COLOR, red )    # The English man lives in the red house.
related( NATIONALITY, Swede, PET, dog )              # The Swede has a dog.
related( NATIONALITY, Dane, DRINK, tea )             # The Dane drinks tea.
left_of( HOUSE_COLOR, green, HOUSE_COLOR, white )    # The green house is on the left side of the white house.
related( DRINK, coffee, HOUSE_COLOR, green )         # They drink coffee in the green house.
related( SMOKE, 'Pall Mall', PET, birds )            # The man who smokes Pall Mall has birds.
related( SMOKE, Dunhill, HOUSE_COLOR, yellow )       # In the yellow house they smoke Dunhill.
related( POSITION, 3, DRINK, milk )                  # In the middle house they drink milk.
related( NATIONALITY, Norwegian, POSITION, 1 )       # The Norwegian lives in the first house.
next_to( SMOKE, Blend, PET, cats )                   # The man who smokes Blend lives in the house next to the house with cats.
next_to( SMOKE, Dunhill, PET, horse )                # In the house next to the house where they have a horse, they smoke Dunhill.
related( SMOKE, 'Blue Master', DRINK, beer )         # The man who smokes Blue Master drinks beer.
related( NATIONALITY, German, SMOKE, Prince )        # The German smokes Prince.
next_to( NATIONALITY, Norwegian, HOUSE_COLOR, blue ) # The Norwegian lives next to the blue house.
next_to( DRINK, water, SMOKE, Blend )                # They drink water in the house next to the house where they smoke Blend.

関係.krb

#############
# Categories

# Foreach set of categories, assert each type
categories
    foreach
        clues.categories($category, $thing1, $thing2, $thing3, $thing4, $thing5)
    assert
        clues.is_category($category, $thing1)
        clues.is_category($category, $thing2)
        clues.is_category($category, $thing3)
        clues.is_category($category, $thing4)
        clues.is_category($category, $thing5)


#########################
# Inverse Relationships

# Foreach A=1, assert 1=A
inverse_relationship_positive
    foreach
        clues.related($category1, $thing1, $category2, $thing2)
    assert
        clues.related($category2, $thing2, $category1, $thing1)

# Foreach A!1, assert 1!A
inverse_relationship_negative
    foreach
        clues.not_related($category1, $thing1, $category2, $thing2)
    assert
        clues.not_related($category2, $thing2, $category1, $thing1)

# Foreach "A beside B", assert "B beside A"
inverse_relationship_beside
    foreach
        clues.next_to($category1, $thing1, $category2, $thing2)
    assert
        clues.next_to($category2, $thing2, $category1, $thing1)


###########################
# Transitive Relationships

# Foreach A=1 and 1=a, assert A=a
transitive_positive
    foreach
        clues.related($category1, $thing1, $category2, $thing2)
        clues.related($category2, $thing2, $category3, $thing3)

        check unique($thing1, $thing2, $thing3) \
          and unique($category1, $category2, $category3)
    assert
        clues.related($category1, $thing1, $category3, $thing3)

# Foreach A=1 and 1!a, assert A!a
transitive_negative
    foreach
        clues.related($category1, $thing1, $category2, $thing2)
        clues.not_related($category2, $thing2, $category3, $thing3)

        check unique($thing1, $thing2, $thing3) \
          and unique($category1, $category2, $category3)
    assert
        clues.not_related($category1, $thing1, $category3, $thing3)


##########################
# Exclusive Relationships

# Foreach A=1, assert A!2 and A!3 and A!4 and A!5
if_one_related_then_others_unrelated
    foreach
        clues.related($category, $thing, $category_other, $thing_other)
        check unique($category, $category_other)

        clues.is_category($category_other, $thing_not_other)
        check unique($thing, $thing_other, $thing_not_other)
    assert
        clues.not_related($category, $thing, $category_other, $thing_not_other)

# Foreach A!1 and A!2 and A!3 and A!4, assert A=5
if_four_unrelated_then_other_is_related
    foreach
        clues.not_related($category, $thing, $category_other, $thingA)
        clues.not_related($category, $thing, $category_other, $thingB)
        check unique($thingA, $thingB)

        clues.not_related($category, $thing, $category_other, $thingC)
        check unique($thingA, $thingB, $thingC)

        clues.not_related($category, $thing, $category_other, $thingD)
        check unique($thingA, $thingB, $thingC, $thingD)

        # Find the fifth variation of category_other.
        clues.is_category($category_other, $thingE)
        check unique($thingA, $thingB, $thingC, $thingD, $thingE)
    assert
        clues.related($category, $thing, $category_other, $thingE)


###################
# Neighbors: Basic

# Foreach "A left of 1", assert "A beside 1"
expanded_relationship_beside_left
    foreach
        clues.left_of($category1, $thing1, $category2, $thing2)
    assert
        clues.next_to($category1, $thing1, $category2, $thing2)

# Foreach "A beside 1", assert A!1
unrelated_to_beside
    foreach
        clues.next_to($category1, $thing1, $category2, $thing2)
        check unique($category1, $category2)
    assert
        clues.not_related($category1, $thing1, $category2, $thing2)


###################################
# Neighbors: Spatial Relationships

# Foreach "A beside B" and "A=(at-edge)", assert "B=(near-edge)"
check_next_to_either_edge
    foreach
        clues.related(POSITION, $position_known, $category, $thing)
        check is_edge($position_known)

        clues.next_to($category, $thing, $category_other, $thing_other)

        clues.is_category(POSITION, $position_other)
        check is_beside($position_known, $position_other)
    assert
        clues.related(POSITION, $position_other, $category_other, $thing_other)

# Foreach "A beside B" and "A!(near-edge)" and "B!(near-edge)", assert "A!(at-edge)"
check_too_close_to_edge
    foreach
        clues.next_to($category, $thing, $category_other, $thing_other)

        clues.is_category(POSITION, $position_edge)
        clues.is_category(POSITION, $position_near_edge)
        check is_edge($position_edge) and is_beside($position_edge, $position_near_edge)

        clues.not_related(POSITION, $position_near_edge, $category, $thing)
        clues.not_related(POSITION, $position_near_edge, $category_other, $thing_other)
    assert
        clues.not_related(POSITION, $position_edge, $category, $thing)

# Foreach "A beside B" and "A!(one-side)", assert "A=(other-side)"
check_next_to_with_other_side_impossible
    foreach
        clues.next_to($category, $thing, $category_other, $thing_other)

        clues.related(POSITION, $position_known, $category_other, $thing_other)
        check not is_edge($position_known)

        clues.not_related($category, $thing, POSITION, $position_one_side)
        check is_beside($position_known, $position_one_side)

        clues.is_category(POSITION, $position_other_side)
        check is_beside($position_known, $position_other_side) \
          and unique($position_known, $position_one_side, $position_other_side)
    assert
        clues.related($category, $thing, POSITION, $position_other_side)

# Foreach "A left of B"...
#   ... and "C=(position1)" and "D=(position2)" and "E=(position3)"
# ~> assert "A=(other-position)" and "B=(other-position)+1"
left_of_and_only_two_slots_remaining
    foreach
        clues.left_of($category_left, $thing_left, $category_right, $thing_right)

        clues.related($category_left, $thing_left_other1, POSITION, $position1)
        clues.related($category_left, $thing_left_other2, POSITION, $position2)
        clues.related($category_left, $thing_left_other3, POSITION, $position3)
        check unique($thing_left, $thing_left_other1, $thing_left_other2, $thing_left_other3)

        clues.related($category_right, $thing_right_other1, POSITION, $position1)
        clues.related($category_right, $thing_right_other2, POSITION, $position2)
        clues.related($category_right, $thing_right_other3, POSITION, $position3)
        check unique($thing_right, $thing_right_other1, $thing_right_other2, $thing_right_other3)

        clues.is_category(POSITION, $position4)
        clues.is_category(POSITION, $position5)

        check is_left_right($position4, $position5) \
          and unique($position1, $position2, $position3, $position4, $position5)
    assert
        clues.related(POSITION, $position4, $category_left, $thing_left)
        clues.related(POSITION, $position5, $category_right, $thing_right)


#########################

fc_extras

    def unique(*args):
        return len(args) == len(set(args))

    def is_edge(pos):
        return (pos == 1) or (pos == 5)

    def is_beside(pos1, pos2):
        diff = (pos1 - pos2)
        return (diff == 1) or (diff == -1)

    def is_left_right(pos_left, pos_right):
        return (pos_right - pos_left == 1)

driver.py (実際にはもっと大きいですが、これが本質です)

from pyke import knowledge_engine

engine = knowledge_engine.engine(__file__)
engine.activate('relations')

try:
    natl = engine.prove_1_goal('clues.related(PET, zebra, NATIONALITY, $nationality)')[0].get('nationality')
except Exception, e:
    natl = "Unknown"
print "== Who owns the zebra? %s ==" % natl

出力例:

$ python driver.py

== Who owns the zebra? German ==

#   Color    Nationality    Pet    Drink       Smoke    
=======================================================
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 

Calculated in 1.19 seconds.

ソース: https://github.com/DreadPirateShawn/pyke-who-owns-zebra

于 2014-06-09T04:06:13.837 に答える
8

これは、 C＃のEinstein'sRiddleに投稿されたNSolverを使用した完全なソリューションからの抜粋です。

// 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));
于 2008-11-25T21:23:38.027 に答える
4

これは実際には制約解決の問題です。論理プログラミングのような言語で一般化された種類の制約伝播を使用してそれを行うことができます。ALE (属性ロジック エンジン) システムの Zebra 問題に特化したデモがあります。

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

簡略化された Zebra パズルのコーディングへのリンクは次のとおりです。

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

これを効率的に行うことは別の問題です。

于 2009-01-09T21:07:50.340 に答える