Résoudre « À qui appartient le zèbre » par programmation ?

Question

Edit: ce jeu est également connu comme "l'Énigme d'Einstein"

De la à Qui appartient le Zèbre est un exemple d'un jeu classique de casse-tête et je parie que la plupart des gens sur un Débordement de Pile peut le résoudre avec un stylo et du papier. Mais ce serait une solution de programmation?

Basé sur les indices énumérés ci-dessous...

• Il y a cinq maisons.
• Chaque maison a sa propre couleur.
• Tous les propriétaires de la maison sont de nationalités différentes.
• Qu'ils ont tous des animaux de compagnie.
• Ils boivent tous de différentes boissons.
• Ils ont tous la fumée des cigarettes différentes.
• L'anglais vit dans la maison rouge.
• Le Suédois a un chien.
• Le Danois boit du thé.
• La maison verte est à gauche de la maison blanche.
• Ils boivent du café dans la maison verte.
• L'homme qui fume des Pall Mall a des oiseaux.
• Dans la maison jaune ils fument Dunhill.
• Dans le milieu de la maison, ils boivent du lait.
• Le norvégien vit dans la première maison.
• L'homme qui fume des Blend vit dans la maison à côté de la maison avec des chats.
• Dans la maison à côté de la maison où ils ont un cheval, ils fument Dunhill.
• L'homme qui fume des Blue Master boit de la bière.
• L'allemand fume des Prince.
• Le norvégien habite à côté de la maison bleue.
• Ils boivent de l'eau dans la maison à côté de la maison où ils fument Mélange.

...à qui appartient le Zèbre?

Answer 1

Voici une solution en Python basée sur la contrainte de programmation:

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

Sortie:

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

Il faut 0.6 secondes (CPU 1.5 GHz) pour trouver la solution.
La réponse est "allemand possède zebra".

---

Pour installer l' constraint module de:

• télécharger:

  $ wget http://labix.org/download/python-constraint/python-constraint-1.1.tar.bz2

• extrait:

  $ bzip2 -cd python-contrainte-1.1.le goudron.bz2 | tar xvf -

• installer:

  $ cd python-contrainte-1.1

  $ python setup.py installer

Answer 2

En Prolog, nous pourrons instancier le domaine simplement en sélectionnant des éléments * d’elle  :) (des choix mutuellement exclusifs*, pour une efficacité). À l’aide de SWI-Prolog,

Fonctionne tout à fait instantanément :

Answer 3

Une affiche déjà mentionné que Prolog est une solution potentielle. C'est vrai, et c'est la solution que j'allais utiliser. En termes plus généraux, ceci est un problème pour un système automatisé système d'inférence. Prolog est un langage de programmation logique (et associés interprète), qui constituent un système. Il permet essentiellement de la conclusion de faits à partir des déclarations faites à l'aide de Logique du Premier Ordre. FOL est essentiellement une forme plus avancée de la logique propositionnelle. Si vous décidez que vous ne voulez pas utiliser Prolog, vous pouvez utiliser un système similaire de votre propre création à l'aide d'une technique telle que le modus ponens pour effectuer les en tirer les conclusions.

Vous aurez, bien sûr, besoin d'ajouter quelques règles concernant les zèbres, car il n'est pas mentionné nulle part... je crois que le but est que vous pouvez comprendre que les 4 autres animaux de compagnie et ainsi déduire le dernier est le zèbre? Vous aurez envie d'ajouter des règles que l'état d'un zèbre est l'un des animaux de compagnie, et chaque maison peut avoir qu'un seul animal de compagnie. Obtenir ce genre de "sens commun" de connaissances dans un système d'inférence est l'obstacle majeur à l'utilisation de la technique comme une vrai IA. Il y a certains projets de recherche, tels que le Cyc, qui tentent de donner de telles commun de connaissances par le biais de la force brute. Ils ont rencontré un intéressant quantité de succès.

Answer 4

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

À l'interprète:

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

Answer 5

Voici comment je voudrais aller à ce sujet. D'abord je voudrais générer tous commandés n-tuples

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

5^6, 15625, facilement gérable. Puis je filtre le simple booléen conditions. il y a une dizaine d'entre eux, et chacun de ceux que vous attendez pour filtrer 8/25 des conditions (1/25 des conditions de contenir un Suédois avec un chien, 16/25 contenir un non-Suédois avec un non-chien). Bien sûr, ils ne sont pas indépendants, mais après filtrage ceux là ne devraient pas être nombreux à gauche.

Après cela, vous avez un joli problème graphique. Créer un graphique avec chaque nœud représentant de l'un des n-uplets. Ajouter les arêtes du graphe si les deux extrémités contenir des doublons dans certains n-tuple de position ou violer toute "position" des contraintes (il y en a cinq de ceux-ci). À partir de là, vous êtes près de la maison, recherche dans le graphe un ensemble indépendant de cinq nœuds (avec aucun des nœuds reliés par des arêtes). Si il n'y a pas de trop, vous pourriez peut-être juste générer de manière exhaustive tous les 5-n-uplets de n-tuples et juste de filtrer de nouveau.

Ce pourrait être un bon candidat pour le code de golf. Quelqu'un peut probablement résoudre dans une ligne avec quelque chose comme haskell :)

après coup: Le filtre initial pass pouvez également supprimer des informations à partir de la position de contraintes. Pas beaucoup (1/25), mais tout de même significatif.