Resolver “Quem é dono da Zebra” programática?
https://stackoverflow.com/questions/318888
-
11-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Edit: este quebra-cabeça também é conhecido como "Riddle de Einstein"
O Quem possui o Zebra (você pode experimentar a versão online aqui ) é um exemplo de um conjunto clássico de quebra-cabeças e eu aposto que a maioria das pessoas no estouro de pilha pode resolvê-lo com caneta e papel. Mas o que seria um olhar solução programática como?
Com base nos indícios listados abaixo ...
- Há cinco casas.
- Cada casa tem sua própria cor única.
- Todos os proprietários da casa são de diferentes nacionalidades.
- Todos eles têm diferentes animais de estimação.
- todos eles bebida bebidas diferentes.
- Todos eles fumam diferentes cigarros.
- O inglês vive na casa vermelha.
- O sueco tem um cachorro.
- O dinamarquês bebe chá.
- A casa verde está no lado esquerdo da casa branca.
- Eles bebem café na casa verde.
- O homem que fuma Pall Mall tem pássaros.
- Na casa amarela que fuma Dunhill.
- Na casa do meio bebem leite.
- O norueguês vive na primeira casa.
- O homem que fuma vidas Mistura na casa ao lado da casa com os gatos.
- Na casa ao lado da casa onde eles têm um cavalo, eles fumam Dunhill.
- O homem que fuma Azul Mestre bebe cerveja.
- O alemão fuma Prince.
- O norueguês vive ao lado da casa azul.
- Eles bebem água na casa ao lado da casa onde eles fumam Blend.
... quem possui o Zebra?
Solução
Aqui está uma solução em Python com base em restrição-programação:
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()
Output:
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
É preciso 0,6 segundos (1.5GHz CPU) para encontrar a solução.
A resposta é "alemão detém zebra."
Para instalar o constraint módulo via pip:
pip instalar python-restrição
Para instalar manualmente:
-
download:
-
extracto (Linux / Mac / BSD):
$ bzip2 -CD python-restrição-1.2.tar.bz2 | tar xvf -
-
extrato (Windows, com 7zip ):
> 7z e python-restrição-1.2.tar.bz2
> 7z e python-restrição-1.2.tar -
instalar:
$ cd python-restrição-1.2
$ Python setup.py install
Outras dicas
Em Prolog, podemos instanciar o domínio apenas selecionar elementos de it :) (fazendo opções mutuamente exclusivas , para a eficiência). Usando 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).
Executa 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 Prolog é uma solução potencial. Isso é verdade, e é a solução que eu usaria. Em termos mais gerais, este é um problema perfeito para um sistema de inferência automatizada. Prolog é uma linguagem de programação lógica (e intérprete associado) que formam esse sistema a. Ele basicamente permite concluir de fatos de declarações feitas usando Primeira Ordem Logic . FOL é basicamente uma forma mais avançada da lógica proposicional. Se você decidir que não quer usar Prolog, você poderia usar um sistema semelhante de sua própria criação usando uma técnica como modus ponens para realizar a tirar as conclusões.
Você vai, naturalmente, necessidade de adicionar algumas regras sobre zebras, já que não é mencionado em qualquer lugar ... Eu acredito que a intenção é que você pode descobrir os outros 4 animais de estimação e, portanto, deduzir a última é a zebra ? Você vai querer adicionar regras que estado uma zebra é um dos animais de estimação, e cada casa só pode ter um animal de estimação. Recebendo este tipo de conhecimento "senso comum" em um sistema de inferência é o maior obstáculo ao uso da técnica como um verdadeiro AI. Existem alguns projetos de pesquisa, tais como Cyc, que estão tentando dar tal conhecimento comum através da força bruta. Eles reuniram-se com uma quantidade interessante de sucesso.
SWI-Prolog compatível:
% 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 gerar todo o ordenou n-tuplas
(housenumber, color, nationality, pet, drink, smoke)
5 ^ 6 desses, 15625, facilmente administrável. Então eu filtrar as condições booleanas simples. há dez deles, e cada um daqueles que você esperaria para filtrar 8/25 das condições (1/25 das condições contêm um sueco com um cão, 16/25 conter uma não-sueco com um não-cão) . É claro que eles não são independentes, mas depois de filtrar aqueles que lá fora não devem ser muitos esquerda.
Depois disso, você tem um problema gráfico agradável. Criar um gráfico com cada nó, que representa um dos restantes n-tuplos. Adicionar bordas para o gráfico se as duas extremidades conter duplicados em alguma posição n-tuplo ou violar quaisquer constrangimentos 'posicionais' (há cinco daqueles). De lá, você está quase em casa, procure o gráfico para um conjunto independente de cinco nós (com nenhum dos nós conectados por arestas). Se não há muitos, você poderia apenas exaustivamente gerar todos os 5-tuplas de n-tuplas e apenas filtrá-los novamente.
Este poderia ser um bom candidato para o golfe código. Alguém provavelmente pode resolvê-lo em uma linha com algo como Haskell:)
adendo: O passe filtro inicial também pode eliminar informações das restrições posicionais. Não muito (1/25), mas ainda significativo.
Outra solução Python, desta vez usando Pyke do Python (Mecanismo de Conhecimento Python). Concedido, é mais detalhado do que usando o módulo de "restrição" do Python na solução por @ J.F.Sebastian, mas fornece uma comparação interessante para quem procura em um mecanismo de conhecimento cru para este 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 completo solução usando NSolver , publicadas em < a href = "http://www.knowing.net/index.php/2005/08/08/einsteins-riddle-in-c/" rel = "nofollow noreferrer"> 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));
Aqui está uma solução simples no CLP (FD) (ver 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)).
Executá-lo, produz:
3 -? Tempo (resolver (Z)).
% 111,798 inferências, 0,016 CPU em 0.020 segundos (78% CPU, 7166493 Lips)
Z = alemão.
ES6 (Javascript) solução
Com muita ES6 geradores e uma pouco de lodash . Você vai precisar Babel para executar este.
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' } ]
Executar tempo é de cerca de 2.5s para mim, mas isso pode ser melhorado muito, alterando a ordem das regras. Decidi manter a ordem original para maior clareza.
Obrigado, isso foi um desafio legal!
Este é realmente um problema restrição problemas. Você pode fazer isso com um generalizado tipo de propagação de restrições na lógica de programação como línguas. Temos uma demo especificamente para o problema da zebra na ALE (motor de lógica atributo) do sistema:
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 / gramáticas / baby.pl
Para fazer isso de forma eficiente é outra questão.
A maneira mais fácil de resolver esses problemas por meio de programação é usar loops aninhados sobre todas as permutações e verificar para ver se satisfaz resultado os predicados na pergunta. Muitos dos predicados pode ser içado do circuito interno de alças mais exteriores, a fim de reduzir drasticamente a complexidade computacional até que a resposta pode ser calculado em um tempo razoável.
Aqui está uma solução simples F # derivada de um artigo na F # Jornal :
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 9 ms é:
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 Microsoft Solver Foundation a partir de: https: // msdn.microsoft.com/en-us/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<KeyValuePair<CspTerm, string>>();
NamedTerm House = delegate(string name) {
CspTerm x = S.CreateVariable(S.CreateIntegerInterval(1, 5), name);
termList.Add(new KeyValuePair<CspTerm, string>(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<CspTerm, string> 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 do 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<nc then color[i+1] == green else false endif | i in 1..nc]);
% The Old Gold smoker owns snails.
constraint forall ([smoke[i] == oldgold <-> 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<nc then pet[i+1] == fox else false endif) | i in 1..nc]);
% Kools are smoked in the house next to the house where the horse is kept.
constraint forall ([smoke[i] == kools -> (if i>1 then pet[i-1] == horse else false endif \/ if i<nc then pet[i+1] == horse else false endif)| i in 1..nc]);
%The Lucky Strike smoker drinks orange juice.
constraint forall ([smoke[i] == luckystrike <-> 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<nc then nationality[i+1] == nor else false endif) | i in 1..nc]);
solve satisfy;
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
Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
