alpar@9: /* ZEBRA, Who Owns the Zebra? */ alpar@9: alpar@9: /* Written in GNU MathProg by Andrew Makhorin */ alpar@9: alpar@9: ######################################################################## alpar@9: # The Zebra Puzzle is a well-known logic puzzle. alpar@9: # alpar@9: # It is often called "Einstein's Puzzle" or "Einstein's Riddle" alpar@9: # because it is said to have been invented by Albert Einstein as a boy, alpar@9: # with the common claim that Einstein said "only 2 percent of the alpar@9: # world's population can solve". It is also sometimes attributed to alpar@9: # Lewis Carroll. However, there is no known evidence for Einstein's or alpar@9: # Carroll's authorship. alpar@9: # alpar@9: # There are several versions of this puzzle. The version below is alpar@9: # quoted from the first known publication in Life International alpar@9: # magazine on December 17, 1962. alpar@9: # alpar@9: # 1. There are five houses. alpar@9: # 2. The Englishman lives in the red house. alpar@9: # 3. The Spaniard owns the dog. alpar@9: # 4. Coffee is drunk in the green house. alpar@9: # 5. The Ukrainian drinks tea. alpar@9: # 6. The green house is immediately to the right of the ivory house. alpar@9: # 7. The Old Gold smoker owns snails. alpar@9: # 8. Kools are smoked in the yellow house. alpar@9: # 9. Milk is drunk in the middle house. alpar@9: # 10. The Norwegian lives in the first house. alpar@9: # 11. The man who smokes Chesterfields lives in the house next to the alpar@9: # man with the fox. alpar@9: # 12. Kools are smoked in the house next to the house where the horse alpar@9: # is kept. alpar@9: # 13. The Lucky Strike smoker drinks orange juice. alpar@9: # 14. The Japanese smokes Parliaments. alpar@9: # 15. The Norwegian lives next to the blue house. alpar@9: # alpar@9: # Now, who drinks water? Who owns the zebra? alpar@9: # alpar@9: # In the interest of clarity, it must be added that each of the five alpar@9: # houses is painted a different color, and their inhabitants are of alpar@9: # different national extractions, own different pets, drink different alpar@9: # beverages and smoke different brands of American cigarettes. One alpar@9: # other thing: In statement 6, right means your right. alpar@9: # alpar@9: # (From Wikipedia, the free encyclopedia.) alpar@9: ######################################################################## alpar@9: alpar@9: set HOUSE := { 1..5 }; alpar@9: alpar@9: set COLOR := { "blue", "green", "ivory", "red", "yellow" }; alpar@9: alpar@9: set NATIONALITY := { "Englishman", "Japanese", "Norwegian", "Spaniard", alpar@9: "Ukranian" }; alpar@9: alpar@9: set DRINK := { "coffee", "milk", "orange_juice", "tea", "water" }; alpar@9: alpar@9: set SMOKE := { "Chesterfield", "Kools", "Lucky_Strike", "Old_Gold", alpar@9: "Parliament" }; alpar@9: alpar@9: set PET := { "dog", "fox", "horse", "snails", "zebra" }; alpar@9: alpar@9: var color{HOUSE, COLOR}, binary; alpar@9: c1{h in HOUSE}: sum{c in COLOR} color[h,c] = 1; alpar@9: c2{c in COLOR}: sum{h in HOUSE} color[h,c] = 1; alpar@9: alpar@9: var nationality{HOUSE, NATIONALITY}, binary; alpar@9: n1{h in HOUSE}: sum{n in NATIONALITY} nationality[h,n] = 1; alpar@9: n2{n in NATIONALITY}: sum{h in HOUSE} nationality[h,n] = 1; alpar@9: alpar@9: var drink{HOUSE, DRINK}, binary; alpar@9: d1{h in HOUSE}: sum{d in DRINK} drink[h,d] = 1; alpar@9: d2{d in DRINK}: sum{h in HOUSE} drink[h,d] = 1; alpar@9: alpar@9: var smoke{HOUSE, SMOKE}, binary; alpar@9: s1{h in HOUSE}: sum{s in SMOKE} smoke[h,s] = 1; alpar@9: s2{s in SMOKE}: sum{h in HOUSE} smoke[h,s] = 1; alpar@9: alpar@9: var pet{HOUSE, PET}, binary; alpar@9: p1{h in HOUSE}: sum{p in PET} pet[h,p] = 1; alpar@9: p2{p in PET}: sum{h in HOUSE} pet[h,p] = 1; alpar@9: alpar@9: /* the Englishman lives in the red house */ alpar@9: f2{h in HOUSE}: nationality[h,"Englishman"] = color[h,"red"]; alpar@9: alpar@9: /* the Spaniard owns the dog */ alpar@9: f3{h in HOUSE}: nationality[h,"Spaniard"] = pet[h,"dog"]; alpar@9: alpar@9: /* coffee is drunk in the green house */ alpar@9: f4{h in HOUSE}: drink[h,"coffee"] = color[h,"green"]; alpar@9: alpar@9: /* the Ukrainian drinks tea */ alpar@9: f5{h in HOUSE}: nationality[h,"Ukranian"] = drink[h,"tea"]; alpar@9: alpar@9: /* the green house is immediately to the right of the ivory house */ alpar@9: f6{h in HOUSE}: alpar@9: color[h,"green"] = if h = 1 then 0 else color[h-1,"ivory"]; alpar@9: alpar@9: /* the Old Gold smoker owns snails */ alpar@9: f7{h in HOUSE}: smoke[h,"Old_Gold"] = pet[h,"snails"]; alpar@9: alpar@9: /* Kools are smoked in the yellow house */ alpar@9: f8{h in HOUSE}: smoke[h,"Kools"] = color[h,"yellow"]; alpar@9: alpar@9: /* milk is drunk in the middle house */ alpar@9: f9: drink[3,"milk"] = 1; alpar@9: alpar@9: /* the Norwegian lives in the first house */ alpar@9: f10: nationality[1,"Norwegian"] = 1; alpar@9: alpar@9: /* the man who smokes Chesterfields lives in the house next to the man alpar@9: with the fox */ alpar@9: f11{h in HOUSE}: alpar@9: (1 - smoke[h,"Chesterfield"]) + alpar@9: (if h = 1 then 0 else pet[h-1,"fox"]) + alpar@9: (if h = 5 then 0 else pet[h+1,"fox"]) >= 1; alpar@9: alpar@9: /* Kools are smoked in the house next to the house where the horse is alpar@9: kept */ alpar@9: f12{h in HOUSE}: alpar@9: (1 - smoke[h,"Kools"]) + alpar@9: (if h = 1 then 0 else pet[h-1,"horse"]) + alpar@9: (if h = 5 then 0 else pet[h+1,"horse"]) >= 1; alpar@9: alpar@9: /* the Lucky Strike smoker drinks orange juice */ alpar@9: f13{h in HOUSE}: smoke[h,"Lucky_Strike"] = drink[h,"orange_juice"]; alpar@9: alpar@9: /* the Japanese smokes Parliaments */ alpar@9: f14{h in HOUSE}: nationality[h,"Japanese"] = smoke[h,"Parliament"]; alpar@9: alpar@9: /* the Norwegian lives next to the blue house */ alpar@9: f15{h in HOUSE}: alpar@9: (1 - nationality[h,"Norwegian"]) + alpar@9: (if h = 1 then 0 else color[h-1,"blue"]) + alpar@9: (if h = 5 then 0 else color[h+1,"blue"]) >= 1; alpar@9: alpar@9: solve; alpar@9: alpar@9: printf "\n"; alpar@9: printf "HOUSE COLOR NATIONALITY DRINK SMOKE PET\n"; alpar@9: for {h in HOUSE} alpar@9: { printf "%5d", h; alpar@9: printf{c in COLOR: color[h,c]} " %-6s", c; alpar@9: printf{n in NATIONALITY: nationality[h,n]} " %-11s", n; alpar@9: printf{d in DRINK: drink[h,d]} " %-12s", d; alpar@9: printf{s in SMOKE: smoke[h,s]} " %-12s", s; alpar@9: printf{p in PET: pet[h,p]} " %-6s", p; alpar@9: printf "\n"; alpar@9: } alpar@9: printf "\n"; alpar@9: alpar@9: end;