[language-agnostic] 프로그래밍 방식으로 “누가 Zebra를 소유하고 있습니까?”

Program / 글쓴이

편집 :이 퍼즐은 “아인슈타인의 수수께끼”라고도합니다.

얼룩말을 소유 한 사람 (당신은 할 수 있습니다 여기에 온라인 버전을 사용해이 ) 퍼즐의 고전적인 설정의 예를 들어 내가 스택 오버플로 대부분의 사람들이 종이와 펜을 해결할 수 있습니다 내기. 그러나 프로그래밍 솔루션은 어떻게 생겼습니까?

아래 나열된 단서를 기반으로 …

  • 다섯 집이 있습니다.
  • 각 집마다 고유 한 색상이 있습니다.
  • 모든 주택 소유자는 국적이 다릅니다.
  • 그들은 모두 다른 애완 동물이 있습니다.
  • 그들은 모두 다른 음료를 마신다.
  • 그들은 모두 다른 담배를 피 웁니다.
  • 영국인은 빨간 집에 산다.
  • 스웨덴에는 개가 있습니다.
  • 데인은 차를 마신다.
  • 그린 하우스는 백악관의 왼쪽에 있습니다.
  • 그들은 온실에서 커피를 마신다.
  • Pall Mall을 피우는 사람은 새가 있습니다.
  • 노란 집에서 그들은 던힐을 피 웁니다.
  • 중간 집에서 그들은 우유를 마신다.
  • 노르웨이 인은 첫 번째 집에 산다.
  • 담배를 피우는 사람은 고양이와 함께 집 옆집에 산다.
  • 말이있는 집 옆 집에서 던힐을 피 웁니다.
  • 블루 마스터를 피우는 사람은 맥주를 마신다.
  • 독일은 왕자를 연기가 난다.
  • 노르웨이는 청와대 옆에 산다.
  • 그들은 블렌드를 피우는 집 옆 집에서 물을 마신다.

… 얼룩말을 누가 소유합니까?

답변

제약 조건 프로그래밍을 기반으로 한 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)가 걸립니다.
대답은 “독일인은 얼룩말을 소유하고 있습니다.”

pip install python-constraint 를 통해 constraint모듈 을 설치하려면pip

수동으로 설치하려면

답변

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.

답변

한 포스터는 이미 Prolog가 잠재적 솔루션이라고 언급했습니다. 이것은 사실이며 내가 사용할 솔루션입니다. 보다 일반적인 용어로, 이것은 자동 추론 시스템에있어 완벽한 문제입니다. 프롤로그는 이러한 시스템을 구성하는 논리 프로그래밍 언어 (및 관련 인터프리터)입니다. 기본적으로 First Order Logic을 사용하여 작성된 진술에서 사실을 결론 지을 수 있습니다 . FOL은 기본적으로보다 진보 된 형태의 제안 논리입니다. Prolog를 사용하지 않기로 결정한 경우 , 결론을 도출하기 위해 modus ponens 와 같은 기술을 사용하여 유사한 자체 제작 시스템을 사용할 수 있습니다 .

물론 어디에서도 언급되지 않았기 때문에 얼룩말에 관한 규칙을 추가해야 할 것입니다 … 나는 다른 4 마리의 애완 동물을 알아 내서 마지막으로 얼룩말을 추론 할 수 있다고 생각합니다. 당신은 얼룩말이 애완 동물 중 하나이며 각 집마다 애완 동물을 가질 수 있다는 규칙을 추가하고 싶을 것입니다. 이러한 종류의 “상식”지식을 추론 시스템에 도입하는 것은이 기술을 진정한 AI로 사용하는 데있어 가장 큰 장애물입니다. Cyc과 같은 일부 연구 프로젝트는 무차별적인 힘을 통해 그러한 공통 지식을 제공하려고 시도하고 있습니다. 그들은 흥미로운 성공을 거두었습니다.

답변

SWI- 프롤로그 호환 :

% 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

답변

여기 내가 어떻게 갈 거에요. 먼저 모든 정렬 된 n 튜플을 생성합니다.

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

그 중 5 ^ 6, 15625, 쉽게 관리 할 수 ​​있습니다. 그런 다음 간단한 부울 조건을 필터링합니다. 그 중 10 개가 있고 조건의 8/25를 필터링 할 것으로 예상되는 각 조건 (1/25 조건에는 개가있는 스웨덴어가 포함되어 있고 16/25에는 개가 아닌 스웨덴어가 포함되어 있음) . 물론 그것들은 독립적이지 않지만 그것들을 걸러 낸 후에는 많은 것이 남아 있지 않아야합니다.

그 후에는 멋진 그래프 문제가 있습니다. 나머지 n- 튜플 중 하나를 나타내는 각 노드로 그래프를 작성하십시오. 두 개의 끝이 일부 n- 튜플 위치에 중복을 포함하거나 ‘위치’제약 조건을 위반하는 경우 그래프에 가장자리를 추가합니다 (이 중 5 개가 있음). 거의 모든 곳에서 그래프를 검색하여 독립적 인 5 개 노드 세트 (가장자리에 연결된 노드가없는)를 찾으십시오. 너무 많지 않은 경우 n 튜플의 5 튜플을 모두 철저하게 생성하고 다시 필터링 할 수 있습니다.

이것은 코드 골프에 대한 좋은 후보가 될 수 있습니다. 누군가는 아마도 haskell과 같은 것을 한 줄로 해결할 수 있습니다 🙂

나중에 생각할 사항 : 초기 필터 패스는 위치 제약 조건에서 정보를 제거 할 수도 있습니다. 많지 않지만 (1/25) 여전히 중요합니다.

답변

이번에는 Python의 PyKE (Python Knowledge Engine)를 사용하는 또 다른 Python 솔루션입니다. 물론, @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.

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

답변

다음은 C #의 Einstein ‘s Riddle에 게시 된 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));