Resolvendo “Quem é dono da Zebra” programaticamente?

Edit: este enigma também é conhecido como “enigma de Einstein”

O Who é dono da Zebra (você pode experimentar a versão online aqui ) é um exemplo de um conjunto clássico de quebra-cabeças e aposto que a maioria das pessoas no Stack Overflow pode resolvê-lo com papel e caneta. Mas como seria uma solução programática?

Baseado nas pistas listadas abaixo …

  • Existem cinco casas.
  • Cada casa tem sua própria cor única.
  • Todos os proprietários de casas são de diferentes nacionalidades.
  • Todos eles têm animais de estimação diferentes.
  • Todos bebem bebidas diferentes.
  • Todos fumam cigarros diferentes.
  • O homem inglês mora na casa vermelha.
  • O sueco tem um cachorro.
  • O dinamarquês bebe chá.
  • A casa verde fica no lado esquerdo da casa branca.
  • Eles bebem café na casa verde.
  • O homem que fuma Pall Mall tem pássaros.
  • Na casa amarela eles fumam Dunhill.
  • Na casa do meio eles bebem leite.
  • O norueguês vive na primeira casa.
  • O homem que fuma Blend mora na casa ao lado da casa com gatos.
  • Na casa ao lado da casa onde eles têm um cavalo, eles fumam Dunhill.
  • O homem que fuma Blue Master bebe cerveja.
  • O alemão fuma Prince.
  • O norueguês mora ao lado da casa azul.
  • Eles bebem água na casa ao lado da casa onde fumam Blend.

… quem é dono da zebra?

Aqui está uma solução em Python baseada em programação de restrições:

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

Saída:

 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 

Demora 0,6 segundos (CPU 1.5GHz) para encontrar a solução.
A resposta é “o alemão é dono da zebra”.


Para instalar o módulo de constraint via pip : pip install python-constraint

Para instalar manualmente:

No Prolog, podemos instanciar o domínio apenas selecionando elementos dele 🙂 (fazendo escolhas mutuamente exclusivas , para eficiência). Usando o 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). 

Corre bastante instantaneamente:

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

Um cartaz já mencionou que o Prolog é uma solução potencial. Isso é verdade e é a solução que eu usaria. Em termos mais gerais, esse é um problema perfeito para um sistema de inferência automatizado. Prolog é uma linguagem de programação lógica (e intérprete associado) que forma tal sistema. Basicamente, permite concluir fatos a partir de declarações feitas usando a lógica de primeira ordem . A FOL é basicamente uma forma mais avançada de lógica proposicional. Se você decidir que não quer usar o Prolog, você pode usar um sistema similar de sua própria criação usando uma técnica como o modus ponens para realizar as conclusões.

É claro que você precisará adicionar algumas regras sobre as zebras, já que elas não são mencionadas em nenhum lugar … Acredito que a intenção é que você possa descobrir os outros 4 animais de estimação e, assim, deduzir que o último é a zebra? Você vai querer adicionar regras que afirmam que uma zebra é um dos animais de estimação, e cada casa só pode ter um animal de estimação. Conseguir esse tipo de conhecimento do “senso comum” em um sistema de inferência é o maior obstáculo para usar a técnica como uma IA verdadeira. Existem alguns projetos de pesquisa, como o Cyc, que estão tentando dar esse conhecimento comum através da força bruta. Eles encontraram uma quantidade interessante de sucesso.

Compatível com 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). 

No intérprete:

 ?- get_zebra(Street, Who). Street = ... Who = german 

Aqui está como eu iria sobre isso. Primeiro, eu geraria todas as n-uplas ordenadas

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

5 ^ 6 desses, 15625, facilmente gerenciáveis. Então eu filtraria as condições booleanas simples. há dez deles, e cada um deles espera filtrar 8/25 das condições (1/25 das condições contêm um sueco com um cachorro, 16/25 contêm um não-sueco com um não-cão) . É claro que eles não são independentes, mas depois de filtrar os que estão por aí, não devem restar muitos.

Depois disso, você tem um bom problema gráfico. Crie um gráfico com cada nó representando uma das n-uplas restantes. Adicione bordas ao gráfico se as duas extremidades contiverem duplicatas em alguma posição n-tupla ou violar qualquer restrição ‘posicional’ (há cinco delas). De lá você está quase em casa, procure no gráfico por um conjunto independente de cinco nós (com nenhum dos nós conectados pelas bordas). Se não houver muitos, você poderia apenas gerar exaustivamente todas as 5-tuplas de n-tuplas e apenas filtrá-las novamente.

Este poderia ser um bom candidato para o golfe de código. Alguém provavelmente pode resolvê-lo em uma linha com algo como haskell 🙂

reflection tardia: a passagem inicial do filtro também pode eliminar informações das restrições posicionais. Não muito (1/25), mas ainda assim significativo.

Outra solução Python, desta vez usando o PyKE Python (Python Knowledge Engine). É mais detalhado do que usar o módulo “constraint” do Python na solução do @JFSebastian, mas ele fornece uma comparação interessante para qualquer pessoa que esteja pesquisando um mecanismo de conhecimento bruto para esse tipo de problema.

clues.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 (na verdade maior, mas esta é a essência)

 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 

Exemplo de saída:

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

Fonte: https://github.com/DreadPirateShawn/pyke-who-owns-zebra

Aqui está um trecho da solução completa usando o NSolver , postado no Riddle de Einstein em C # :

 // 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)); 

No PAIP (Capítulo 11), Norvig resolve o quebra-cabeça zebra usando um Prolog embutido em Lisp .

Aqui está uma solução direta no CLP (FD) (veja também clpfd ):

 :- use_module(library(clpfd)). solve(ZebraOwner) :- maplist( init_dom(1..5), [[British, Swedish, Danish, Norwegian, German], % Nationalities [Red, Green, Blue, White, Yellow], % Houses [Tea, Coffee, Milk, Beer, Water], % Beverages [PallMall, Blend, Prince, Dunhill, BlueMaster], % Cigarettes [Dog, Birds, Cats, Horse, Zebra]]), % Pets British #= Red, % Hint 1 Swedish #= Dog, % Hint 2 Danish #= Tea, % Hint 3 Green #= White - 1 , % Hint 4 Green #= Coffee, % Hint 5 PallMall #= Birds, % Hint 6 Yellow #= Dunhill, % Hint 7 Milk #= 3, % Hint 8 Norwegian #= 1, % Hint 9 neighbor(Blend, Cats), % Hint 10 neighbor(Horse, Dunhill), % Hint 11 BlueMaster #= Beer, % Hint 12 German #= Prince, % Hint 13 neighbor(Norwegian, Blue), % Hint 14 neighbor(Blend, Water), % Hint 15 memberchk(Zebra-ZebraOwner, [British-british, Swedish-swedish, Danish-danish, Norwegian-norwegian, German-german]). init_dom(R, L) :- all_distinct(L), L ins R. neighbor(X, Y) :- (X #= (Y - 1)) #\/ (X #= (Y + 1)). 

Executando, produz:

3? – hora (resolver (Z)).
% 111.798 inferências, 0.016 CPU em 0.020 segundos (78% da CPU, 7166493 Lips)
Z = alemão

Solução ES6 (Javascript)

Com muitos geradores ES6 e um pouco de lodash . Você precisará do Babel para executar isso.

 var _ = require('lodash'); function canBe(house, criteria) { for (const key of Object.keys(criteria)) if (house[key] && house[key] !== criteria[key]) return false; return true; } function* thereShouldBe(criteria, street) { for (const i of _.range(street.length)) yield* thereShouldBeAtIndex(criteria, i, street); } function* thereShouldBeAtIndex(criteria, index, street) { if (canBe(street[index], criteria)) { const newStreet = _.cloneDeep(street); newStreet[index] = _.assign({}, street[index], criteria); yield newStreet; } } function* leftOf(critA, critB, street) { for (const i of _.range(street.length - 1)) { if (canBe(street[i], critA) && canBe(street[i+1], critB)) { const newStreet = _.cloneDeep(street); newStreet[i ] = _.assign({}, street[i ], critA); newStreet[i+1] = _.assign({}, street[i+1], critB); yield newStreet; } } } function* nextTo(critA, critB, street) { yield* leftOf(critA, critB, street); yield* leftOf(critB, critA, street); } const street = [{}, {}, {}, {}, {}]; // five houses // Btw: it turns out we don't need uniqueness constraint. const constraints = [ s => thereShouldBe({nation: 'English', color: 'red'}, s), s => thereShouldBe({nation: 'Swede', animal: 'dog'}, s), s => thereShouldBe({nation: 'Dane', drink: 'tea'}, s), s => leftOf({color: 'green'}, {color: 'white'}, s), s => thereShouldBe({drink: 'coffee', color: 'green'}, s), s => thereShouldBe({cigarettes: 'PallMall', animal: 'birds'}, s), s => thereShouldBe({color: 'yellow', cigarettes: 'Dunhill'}, s), s => thereShouldBeAtIndex({drink: 'milk'}, 2, s), s => thereShouldBeAtIndex({nation: 'Norwegian'}, 0, s), s => nextTo({cigarettes: 'Blend'}, {animal: 'cats'}, s), s => nextTo({animal: 'horse'}, {cigarettes: 'Dunhill'}, s), s => thereShouldBe({cigarettes: 'BlueMaster', drink: 'beer'}, s), s => thereShouldBe({nation: 'German', cigarettes: 'Prince'}, s), s => nextTo({nation: 'Norwegian'}, {color: 'blue'}, s), s => nextTo({drink: 'water'}, {cigarettes: 'Blend'}, s), s => thereShouldBe({animal: 'zebra'}, s), // should be somewhere ]; function* findSolution(remainingConstraints, street) { if (remainingConstraints.length === 0) yield street; else for (const newStreet of _.head(remainingConstraints)(street)) yield* findSolution(_.tail(remainingConstraints), newStreet); } for (const streetSolution of findSolution(constraints, street)) { console.log(streetSolution); } 

Resultado:

 [ { color: 'yellow', cigarettes: 'Dunhill', nation: 'Norwegian', animal: 'cats', drink: 'water' }, { nation: 'Dane', drink: 'tea', cigarettes: 'Blend', animal: 'horse', color: 'blue' }, { nation: 'English', color: 'red', cigarettes: 'PallMall', animal: 'birds', drink: 'milk' }, { color: 'green', drink: 'coffee', nation: 'German', cigarettes: 'Prince', animal: 'zebra' }, { nation: 'Swede', animal: 'dog', color: 'white', cigarettes: 'BlueMaster', drink: 'beer' } ] 

O tempo de execução é de cerca de 2,5s para mim, mas isso pode ser muito melhor, alterando a ordem das regras. Eu decidi manter a ordem original para maior clareza.

Obrigado, este foi um desafio legal!

Este é realmente um problema de resolução de restrições. Você pode fazê-lo com um tipo generalizado de propagação de restrição em linguagens de programação lógica. Temos uma demonstração específica para o problema da Zebra no sistema ALE (mecanismo de lógica de atributos):

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

Aqui está o link para a codificação de um quebra-cabeça Zebra simplificado:

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

Fazer isso de maneira eficiente é outro assunto.

A maneira mais fácil de resolver tais problemas programaticamente é usar loops nesteds em todas as permutações e verificar se o resultado satisfaz os predicados da pergunta. Muitos dos predicados podem ser hasteados do loop interno for loops externos, a fim de reduzir drasticamente a complexidade computacional até que a resposta possa ser computada em um tempo razoável.

Aqui está uma simples solução F # derivada de um artigo no F # Journal :

 let rec distribute y xs = match xs with | [] -> [[y]] | x::xs -> (y::x::xs)::[for xs in distribute y xs -> x::xs] let rec permute xs = match xs with | [] | [_] as xs -> [xs] | x::xs -> List.collect (distribute x) (permute xs) let find xs x = List.findIndex ((=) x) xs + 1 let eq xs x ys y = find xs x = find ys y let nextTo xs x ys y = abs(find xs x - find ys y) = 1 let nations = ["British"; "Swedish"; "Danish"; "Norwegian"; "German"] let houses = ["Red"; "Green"; "Blue"; "White"; "Yellow"] let drinks = ["Milk"; "Coffee"; "Water"; "Beer"; "Tea"] let smokes = ["Blend"; "Prince"; "Blue Master"; "Dunhill"; "Pall Mall"] let pets = ["Dog"; "Cat"; "Zebra"; "Horse"; "Bird"] [ for nations in permute nations do if find nations "Norwegian" = 1 then for houses in permute houses do if eq nations "British" houses "Red" && find houses "Green" = find houses "White"-1 && nextTo nations "Norwegian" houses "Blue" then for drinks in permute drinks do if eq nations "Danish" drinks "Tea" && eq houses "Green" drinks "Coffee" && 3 = find drinks "Milk" then for smokes in permute smokes do if eq houses "Yellow" smokes "Dunhill" && eq smokes "Blue Master" drinks "Beer" && eq nations "German" smokes "Prince" && nextTo smokes "Blend" drinks "Water" then for pets in permute pets do if eq nations "Swedish" pets "Dog" && eq smokes "Pall Mall" pets "Bird" && nextTo pets "Cat" smokes "Blend" && nextTo pets "Horse" smokes "Dunhill" then yield nations, houses, drinks, smokes, pets ] 

A saída obtida em 9ms é:

 val it : (string list * string list * string list * string list * string list) list = [(["Norwegian"; "Danish"; "British"; "German"; "Swedish"], ["Yellow"; "Blue"; "Red"; "Green"; "White"], ["Water"; "Tea"; "Milk"; "Coffee"; "Beer"], ["Dunhill"; "Blend"; "Pall Mall"; "Prince"; "Blue Master"], ["Cat"; "Horse"; "Bird"; "Zebra"; "Dog"])] 

O exemplo da Microsoft Solver Foundation em: https://msdn.microsoft.com/pt-br/library/ff525831%28v=vs.93%29.aspx?f=255&MSPPError=-2147217396

 delegate CspTerm NamedTerm(string name); public static void Zebra() { ConstraintSystem S = ConstraintSystem.CreateSolver(); var termList = new List>(); NamedTerm House = delegate(string name) { CspTerm x = S.CreateVariable(S.CreateIntegerInterval(1, 5), name); termList.Add(new KeyValuePair(x, name)); return x; }; CspTerm English = House("English"), Spanish = House("Spanish"), Japanese = House("Japanese"), Italian = House("Italian"), Norwegian = House("Norwegian"); CspTerm red = House("red"), green = House("green"), white = House("white"), blue = House("blue"), yellow = House("yellow"); CspTerm dog = House("dog"), snails = House("snails"), fox = House("fox"), horse = House("horse"), zebra = House("zebra"); CspTerm painter = House("painter"), sculptor = House("sculptor"), diplomat = House("diplomat"), violinist = House("violinist"), doctor = House("doctor"); CspTerm tea = House("tea"), coffee = House("coffee"), milk = House("milk"), juice = House("juice"), water = House("water"); S.AddConstraints( S.Unequal(English, Spanish, Japanese, Italian, Norwegian), S.Unequal(red, green, white, blue, yellow), S.Unequal(dog, snails, fox, horse, zebra), S.Unequal(painter, sculptor, diplomat, violinist, doctor), S.Unequal(tea, coffee, milk, juice, water), S.Equal(English, red), S.Equal(Spanish, dog), S.Equal(Japanese, painter), S.Equal(Italian, tea), S.Equal(1, Norwegian), S.Equal(green, coffee), S.Equal(1, green - white), S.Equal(sculptor, snails), S.Equal(diplomat, yellow), S.Equal(3, milk), S.Equal(1, S.Abs(Norwegian - blue)), S.Equal(violinist, juice), S.Equal(1, S.Abs(fox - doctor)), S.Equal(1, S.Abs(horse - diplomat)) ); bool unsolved = true; ConstraintSolverSolution soln = S.Solve(); while (soln.HasFoundSolution) { unsolved = false; System.Console.WriteLine("solved."); StringBuilder[] houses = new StringBuilder[5]; for (int i = 0; i < 5; i++) houses[i] = new StringBuilder(i.ToString()); foreach (KeyValuePair kvp in termList) { string item = kvp.Value; object house; if (!soln.TryGetValue(kvp.Key, out house)) throw new InvalidProgramException( "can't find a Term in the solution: " + item); houses[(int)house - 1].Append(", "); houses[(int)house - 1].Append(item); } foreach (StringBuilder house in houses) { System.Console.WriteLine(house); } soln.GetNext(); } if (unsolved) System.Console.WriteLine("No solution found."); else System.Console.WriteLine( "Expected: the Norwegian drinking water and the Japanese with the zebra."); } 

Esta é uma solução MiniZinc para o quebra-cabeça zebra conforme definido na Wikipedia:

 include "globals.mzn"; % Zebra puzzle int: nc = 5; % Colors int: red = 1; int: green = 2; int: ivory = 3; int: yellow = 4; int: blue = 5; array[1..nc] of var 1..nc:color; constraint alldifferent([color[i] | i in 1..nc]); % Nationalities int: eng = 1; int: spa = 2; int: ukr = 3; int: nor = 4; int: jap = 5; array[1..nc] of var 1..nc:nationality; constraint alldifferent([nationality[i] | i in 1..nc]); % Pets int: dog = 1; int: snail = 2; int: fox = 3; int: horse = 4; int: zebra = 5; array[1..nc] of var 1..nc:pet; constraint alldifferent([pet[i] | i in 1..nc]); % Drinks int: coffee = 1; int: tea = 2; int: milk = 3; int: orange = 4; int: water = 5; array[1..nc] of var 1..nc:drink; constraint alldifferent([drink[i] | i in 1..nc]); % Smokes int: oldgold = 1; int: kools = 2; int: chesterfields = 3; int: luckystrike = 4; int: parliaments = 5; array[1..nc] of var 1..nc:smoke; constraint alldifferent([smoke[i] | i in 1..nc]); % The Englishman lives in the red house. constraint forall ([nationality[i] == eng <-> color[i] == red | i in 1..nc]); % The Spaniard owns the dog. constraint forall ([nationality[i] == spa <-> pet[i] == dog | i in 1..nc]); % Coffee is drunk in the green house. constraint forall ([color[i] == green <-> drink[i] == coffee | i in 1..nc]); % The Ukrainian drinks tea. constraint forall ([nationality[i] == ukr <-> drink[i] == tea | i in 1..nc]); % The green house is immediately to the right of the ivory house. constraint forall ([color[i] == ivory -> if i pet[i] == snail | i in 1..nc]); % Kools are smoked in the yellow house. constraint forall ([smoke[i] == kools <-> color[i] == yellow | i in 1..nc]); % Milk is drunk in the middle house. constraint drink[3] == milk; % The Norwegian lives in the first house. constraint nationality[1] == nor; % The man who smokes Chesterfields lives in the house next to the man with the fox. constraint forall ([smoke[i] == chesterfields -> (if i>1 then pet[i-1] == fox else false endif \/ if i (if i>1 then pet[i-1] == horse else false endif \/ if i drink[i] == orange | i in 1..nc]); % The Japanese smokes Parliaments. constraint forall ([nationality[i] == jap <-> smoke[i] == parliaments | i in 1..nc]); % The Norwegian lives next to the blue house. constraint forall ([color[i] == blue -> (if i > 1 then nationality[i-1] == nor else false endif \/ if i 

Solução:

 Compiling zebra.mzn Running zebra.mzn color = array1d(1..5 ,[4, 5, 1, 3, 2]); nationality = array1d(1..5 ,[4, 3, 1, 2, 5]); pet = array1d(1..5 ,[3, 4, 2, 1, 5]); drink = array1d(1..5 ,[5, 2, 3, 4, 1]); smoke = array1d(1..5 ,[2, 3, 1, 4, 5]); ---------- Finished in 47msec 
Intereting Posts