Algorithmensammlung: Spezielle Probleme: Das Zebrarätsel

Aus Wikibooks
Zur Navigation springen Zur Suche springen

Algorithmensammlung: Spezielle Probleme


Das Zebrarätsel[Bearbeiten]

Das  Zebrarätsel ist ein oft wiedergegebenes Rätsel aus der Gruppe der Logicals, das also durch logische Schlüsse gelöst werden kann.

Formula[Bearbeiten]

domain Declarations
{
    HouseNumber ::= /*left*/ {1, 2, 3, 4, 5} /*right*/.
    Color ::= {"Red", "Green", "Ivory", "Yellow", "Blue"}.
    Nationality ::= {"Englishman", "Spaniard", "Ukrainian", "Japanese", "Norwegian"}.
    Drink ::= {"Coffee", "Tea", "Milk", "Orange juice", "Water"}.    
    Smoke ::= {"Old Gold", "Chesterfield", "Kools", "Lucky Strike", "Parliament"}.
    Pet ::= {"Dog", "Snails", "Fox", "Horse", "Zebra"}.

    primitive House ::= (number:HouseNumber, color:Color, nationality:Nationality, drink:Drink, smoke:Smoke, pet:Pet).

    // There are five [different] houses.
    HousesAreDifferent := h1 is House, h2 is House, h3 is House, h4 is House, h5 is House, 
                       h1.number != h2.number, h1.number != h3.number, h1.number != h4.number, h1.number != h5.number, 
                       h2.number != h3.number, h2.number != h4.number, h2.number != h5.number, 
                       h3.number != h4.number, h3.number != h5.number, 
                       h4.number != h5.number, 
                       h1.color != h2.color, h1.color != h3.color, h1.color != h4.color, h1.color != h5.color, 
                       h2.color != h3.color, h2.color != h4.color, h2.color != h5.color, 
                       h3.color != h4.color, h3.color != h5.color, 
                       h4.color != h5.color, 
                       h1.nationality != h2.nationality, h1.nationality != h3.nationality, h1.nationality != h4.nationality, h1.nationality != h5.nationality, 
                       h2.nationality != h3.nationality, h2.nationality != h4.nationality, h2.nationality != h5.nationality, 
                       h3.nationality != h4.nationality, h3.nationality != h5.nationality, 
                       h4.nationality != h5.nationality, 
                       h1.drink != h2.drink, h1.drink != h3.drink, h1.drink != h4.drink, h1.drink != h5.drink, 
                       h2.drink != h3.drink, h2.drink != h4.drink, h2.drink != h5.drink, 
                       h3.drink != h4.drink, h3.drink != h5.drink, 
                       h4.drink != h5.drink, 
                       h1.smoke != h2.smoke, h1.smoke != h3.smoke, h1.smoke != h4.smoke, h1.smoke != h5.smoke, 
                       h2.smoke != h3.smoke, h2.smoke != h4.smoke, h2.smoke != h5.smoke, 
                       h3.smoke != h4.smoke, h3.smoke != h5.smoke, 
                       h4.smoke != h5.smoke, 
                       h1.pet != h2.pet, h1.pet != h3.pet, h1.pet != h4.pet, h1.pet != h5.pet, 
                       h2.pet != h3.pet, h2.pet != h4.pet, h2.pet != h5.pet, 
                       h3.pet != h4.pet, h3.pet != h5.pet, 
                       h4.pet != h5.pet.
    conforms := HousesAreDifferent.
}

domain Hints extends Declarations
{
    // The Englishman lives in the red house.
    hint1 := h is House, h.nationality = "Englishman", h.color = "Red".
    
    // The Spaniard owns the dog.
    hint2 := h is House, h.nationality = "Spaniard", h.pet = "Dog". 

    // Coffee is drunk in the green house.
    hint3 := h is House, h.drink = "Coffee", h.color = "Green".

    // The Ukrainian drinks tea.
    hint4 := h is House, h.nationality = "Ukrainian", h.drink = "Tea".
    
    // The green house is immediately to the right of the ivory house.
    hint5 := h is House, i is House, h.color = "Green", h.number = i.number+1, i.color="Ivory". 
    
    // The Old Gold smoker owns snails.
    hint6 := h is House, h.smoke = "Old Gold", h.pet = "Snails". 
    
    // Kools are smoked in the yellow house.
    hint7 := h is House, h.smoke = "Kools", h.color = "Yellow". 
    
    // Milk is drunk in the middle house.
    hint8 := h is House, h.drink = "Milk", h.number = 3.
    
    // The Norwegian lives in the first house.
    hint9 := h is House, h.nationality = "Norwegian", h.number = 1. 
    
    // The man who smokes Chesterfields lives in the house next to the man with the fox.
    hint10_1 := h is House, i is House, h.smoke = "Chesterfield", h.number = i.number+1, i.pet = "Fox". 
    hint10_2 := h is House, i is House, h.smoke = "Chesterfield", h.number = i.number-1, i.pet = "Fox". 
    
    // Kools are smoked in a house next to the house where the horse is kept. 
    hint11_1 := h is House, i is House, h.smoke = "Kools", h.number = i.number + 1, i.pet = "Horse".
    hint11_2 := h is House, i is House, h.smoke = "Kools", h.number = i.number - 1, i.pet = "Horse".
    
    // The Lucky Strike smoker drinks orange juice.
    hint12 := h is House, h.smoke="Lucky Strike", h.drink = "Orange juice". 
    
    // The Japanese smokes Parliaments.
    hint13 := h is House, h.nationality = "Japanese", h.smoke = "Parliament". 
    
    // The Norwegian lives next to the blue house.
    hint14_1 := h is House, i is House, h.nationality = "Norwegian", h.number = i.number + 1, i.color = "Blue". 
    hint14_2 := h is House, i is House, h.nationality = "Norwegian", h.number = i.number - 1, i.color = "Blue". 
    
    conforms := hint1 & hint2 & hint3 & hint4 & hint5 & hint6 & hint7 & hint8 & hint9 & (hint10_1 | hint10_2) & 
                (hint11_1 | hint11_2) & hint12 & hint13 & (hint14_1 | hint14_2).
}

partial model ZebraPuzzle of Hints
{
 // House(number, color, nationality, drink, smoke, pet).
    House(1,_,_,_,_,_)
    House(2,_,_,_,_,_) 
    House(3,_,_,_,_,_)
    House(4,_,_,_,_,_)
    House(5,_,_,_,_,_)
}

Für Formula ist eine Onlineimplementierung verfügbar.

Prolog[Bearbeiten]

    erstes(E,[E|_]).
    mittleres(M,[_,_,M,_,_]).

    links(A,B,[A,B|_]).
    links(A,B,[_|R]) :- links(A,B,R).

    neben(A,B,L) :- links(A,B,L);links(B,A,L).

    run :-
        X = [_,_,_,_,_],                                /* Es gibt (nebeneinander) 5 (noch unbekannte) Häuser */
        member([rot,brite,_,_,_],X),                    /* Der Brite lebt im roten Haus */
        member([_,schwede,_,_,hund],X),                 /* Der Schwede hält einen Hund */
        member([_,daene,tee,_,_],X),                    /* Der Däne trinkt gern Tee */
        links([gruen,_,_,_,_],[weiss,_,_,_,_],X),       /* Das grüne Haus steht links vom weißen Haus */
        member([gruen,_,kaffee,_,_],X),                 /* Der Besitzer des grünen Hauses trinkt Kaffee */
        member([_,_,_,pallmall,vogel],X),               /* Die Person, die Pall Mall raucht, hält einen Vogel */
        mittleres([_,_,milch,_,_],X),                   /* Der Mann, der im mittleren Haus wohnt, trinkt Milch */
        member([gelb,_,_,dunhill,_],X),                 /* Der Besitzer des gelben Hauses raucht Dunhill */
        erstes([_,norweger,_,_,_],X),                   /* Der Norweger wohnt im 1. Haus */
        neben([_,_,_,marlboro,_],[_,_,_,_,katze],X),    /* Der Marlboro-Raucher wohnt neben dem, der eine Katze hält */
        neben([_,_,_,_,pferd],[_,_,_,dunhill,_],X),     /* Der Mann, der ein Pferd hält, wohnt neben dem, der Dunhill raucht */
        member([_,_,bier,winfield,_],X),                /* Der Winfield-Raucher trinkt gern Bier */
        neben([_,norweger,_,_,_],[blau,_,_,_,_],X),     /* Der Norweger wohnt neben dem blauen Haus */
        member([_,deutsche,_,rothmans,_],X),            /* Der Deutsche raucht Rothmans */
        neben([_,_,_,marlboro,_],[_,_,wasser,_,_],X),   /* Der Marlboro-Raucher hat einen Nachbarn, der Wasser trinkt */
        member([_,N,_,_,fisch],X),                      /* Der mit der Nationalität N hat einen Fisch */
        write(X),nl,                                    /* Ausgabe aller Häuser */
        write('Der '),write(N),write(' hat einen Fisch als Haustier.'),nl.   /* Antwort auf die Frage */