[9] | 1 | /* ZEBRA, Who Owns the Zebra? */ |
---|
| 2 | |
---|
| 3 | /* Written in GNU MathProg by Andrew Makhorin <mao@gnu.org> */ |
---|
| 4 | |
---|
| 5 | ######################################################################## |
---|
| 6 | # The Zebra Puzzle is a well-known logic puzzle. |
---|
| 7 | # |
---|
| 8 | # It is often called "Einstein's Puzzle" or "Einstein's Riddle" |
---|
| 9 | # because it is said to have been invented by Albert Einstein as a boy, |
---|
| 10 | # with the common claim that Einstein said "only 2 percent of the |
---|
| 11 | # world's population can solve". It is also sometimes attributed to |
---|
| 12 | # Lewis Carroll. However, there is no known evidence for Einstein's or |
---|
| 13 | # Carroll's authorship. |
---|
| 14 | # |
---|
| 15 | # There are several versions of this puzzle. The version below is |
---|
| 16 | # quoted from the first known publication in Life International |
---|
| 17 | # magazine on December 17, 1962. |
---|
| 18 | # |
---|
| 19 | # 1. There are five houses. |
---|
| 20 | # 2. The Englishman lives in the red house. |
---|
| 21 | # 3. The Spaniard owns the dog. |
---|
| 22 | # 4. Coffee is drunk in the green house. |
---|
| 23 | # 5. The Ukrainian drinks tea. |
---|
| 24 | # 6. The green house is immediately to the right of the ivory house. |
---|
| 25 | # 7. The Old Gold smoker owns snails. |
---|
| 26 | # 8. Kools are smoked in the yellow house. |
---|
| 27 | # 9. Milk is drunk in the middle house. |
---|
| 28 | # 10. The Norwegian lives in the first house. |
---|
| 29 | # 11. The man who smokes Chesterfields lives in the house next to the |
---|
| 30 | # man with the fox. |
---|
| 31 | # 12. Kools are smoked in the house next to the house where the horse |
---|
| 32 | # is kept. |
---|
| 33 | # 13. The Lucky Strike smoker drinks orange juice. |
---|
| 34 | # 14. The Japanese smokes Parliaments. |
---|
| 35 | # 15. The Norwegian lives next to the blue house. |
---|
| 36 | # |
---|
| 37 | # Now, who drinks water? Who owns the zebra? |
---|
| 38 | # |
---|
| 39 | # In the interest of clarity, it must be added that each of the five |
---|
| 40 | # houses is painted a different color, and their inhabitants are of |
---|
| 41 | # different national extractions, own different pets, drink different |
---|
| 42 | # beverages and smoke different brands of American cigarettes. One |
---|
| 43 | # other thing: In statement 6, right means your right. |
---|
| 44 | # |
---|
| 45 | # (From Wikipedia, the free encyclopedia.) |
---|
| 46 | ######################################################################## |
---|
| 47 | |
---|
| 48 | set HOUSE := { 1..5 }; |
---|
| 49 | |
---|
| 50 | set COLOR := { "blue", "green", "ivory", "red", "yellow" }; |
---|
| 51 | |
---|
| 52 | set NATIONALITY := { "Englishman", "Japanese", "Norwegian", "Spaniard", |
---|
| 53 | "Ukranian" }; |
---|
| 54 | |
---|
| 55 | set DRINK := { "coffee", "milk", "orange_juice", "tea", "water" }; |
---|
| 56 | |
---|
| 57 | set SMOKE := { "Chesterfield", "Kools", "Lucky_Strike", "Old_Gold", |
---|
| 58 | "Parliament" }; |
---|
| 59 | |
---|
| 60 | set PET := { "dog", "fox", "horse", "snails", "zebra" }; |
---|
| 61 | |
---|
| 62 | var color{HOUSE, COLOR}, binary; |
---|
| 63 | c1{h in HOUSE}: sum{c in COLOR} color[h,c] = 1; |
---|
| 64 | c2{c in COLOR}: sum{h in HOUSE} color[h,c] = 1; |
---|
| 65 | |
---|
| 66 | var nationality{HOUSE, NATIONALITY}, binary; |
---|
| 67 | n1{h in HOUSE}: sum{n in NATIONALITY} nationality[h,n] = 1; |
---|
| 68 | n2{n in NATIONALITY}: sum{h in HOUSE} nationality[h,n] = 1; |
---|
| 69 | |
---|
| 70 | var drink{HOUSE, DRINK}, binary; |
---|
| 71 | d1{h in HOUSE}: sum{d in DRINK} drink[h,d] = 1; |
---|
| 72 | d2{d in DRINK}: sum{h in HOUSE} drink[h,d] = 1; |
---|
| 73 | |
---|
| 74 | var smoke{HOUSE, SMOKE}, binary; |
---|
| 75 | s1{h in HOUSE}: sum{s in SMOKE} smoke[h,s] = 1; |
---|
| 76 | s2{s in SMOKE}: sum{h in HOUSE} smoke[h,s] = 1; |
---|
| 77 | |
---|
| 78 | var pet{HOUSE, PET}, binary; |
---|
| 79 | p1{h in HOUSE}: sum{p in PET} pet[h,p] = 1; |
---|
| 80 | p2{p in PET}: sum{h in HOUSE} pet[h,p] = 1; |
---|
| 81 | |
---|
| 82 | /* the Englishman lives in the red house */ |
---|
| 83 | f2{h in HOUSE}: nationality[h,"Englishman"] = color[h,"red"]; |
---|
| 84 | |
---|
| 85 | /* the Spaniard owns the dog */ |
---|
| 86 | f3{h in HOUSE}: nationality[h,"Spaniard"] = pet[h,"dog"]; |
---|
| 87 | |
---|
| 88 | /* coffee is drunk in the green house */ |
---|
| 89 | f4{h in HOUSE}: drink[h,"coffee"] = color[h,"green"]; |
---|
| 90 | |
---|
| 91 | /* the Ukrainian drinks tea */ |
---|
| 92 | f5{h in HOUSE}: nationality[h,"Ukranian"] = drink[h,"tea"]; |
---|
| 93 | |
---|
| 94 | /* the green house is immediately to the right of the ivory house */ |
---|
| 95 | f6{h in HOUSE}: |
---|
| 96 | color[h,"green"] = if h = 1 then 0 else color[h-1,"ivory"]; |
---|
| 97 | |
---|
| 98 | /* the Old Gold smoker owns snails */ |
---|
| 99 | f7{h in HOUSE}: smoke[h,"Old_Gold"] = pet[h,"snails"]; |
---|
| 100 | |
---|
| 101 | /* Kools are smoked in the yellow house */ |
---|
| 102 | f8{h in HOUSE}: smoke[h,"Kools"] = color[h,"yellow"]; |
---|
| 103 | |
---|
| 104 | /* milk is drunk in the middle house */ |
---|
| 105 | f9: drink[3,"milk"] = 1; |
---|
| 106 | |
---|
| 107 | /* the Norwegian lives in the first house */ |
---|
| 108 | f10: nationality[1,"Norwegian"] = 1; |
---|
| 109 | |
---|
| 110 | /* the man who smokes Chesterfields lives in the house next to the man |
---|
| 111 | with the fox */ |
---|
| 112 | f11{h in HOUSE}: |
---|
| 113 | (1 - smoke[h,"Chesterfield"]) + |
---|
| 114 | (if h = 1 then 0 else pet[h-1,"fox"]) + |
---|
| 115 | (if h = 5 then 0 else pet[h+1,"fox"]) >= 1; |
---|
| 116 | |
---|
| 117 | /* Kools are smoked in the house next to the house where the horse is |
---|
| 118 | kept */ |
---|
| 119 | f12{h in HOUSE}: |
---|
| 120 | (1 - smoke[h,"Kools"]) + |
---|
| 121 | (if h = 1 then 0 else pet[h-1,"horse"]) + |
---|
| 122 | (if h = 5 then 0 else pet[h+1,"horse"]) >= 1; |
---|
| 123 | |
---|
| 124 | /* the Lucky Strike smoker drinks orange juice */ |
---|
| 125 | f13{h in HOUSE}: smoke[h,"Lucky_Strike"] = drink[h,"orange_juice"]; |
---|
| 126 | |
---|
| 127 | /* the Japanese smokes Parliaments */ |
---|
| 128 | f14{h in HOUSE}: nationality[h,"Japanese"] = smoke[h,"Parliament"]; |
---|
| 129 | |
---|
| 130 | /* the Norwegian lives next to the blue house */ |
---|
| 131 | f15{h in HOUSE}: |
---|
| 132 | (1 - nationality[h,"Norwegian"]) + |
---|
| 133 | (if h = 1 then 0 else color[h-1,"blue"]) + |
---|
| 134 | (if h = 5 then 0 else color[h+1,"blue"]) >= 1; |
---|
| 135 | |
---|
| 136 | solve; |
---|
| 137 | |
---|
| 138 | printf "\n"; |
---|
| 139 | printf "HOUSE COLOR NATIONALITY DRINK SMOKE PET\n"; |
---|
| 140 | for {h in HOUSE} |
---|
| 141 | { printf "%5d", h; |
---|
| 142 | printf{c in COLOR: color[h,c]} " %-6s", c; |
---|
| 143 | printf{n in NATIONALITY: nationality[h,n]} " %-11s", n; |
---|
| 144 | printf{d in DRINK: drink[h,d]} " %-12s", d; |
---|
| 145 | printf{s in SMOKE: smoke[h,s]} " %-12s", s; |
---|
| 146 | printf{p in PET: pet[h,p]} " %-6s", p; |
---|
| 147 | printf "\n"; |
---|
| 148 | } |
---|
| 149 | printf "\n"; |
---|
| 150 | |
---|
| 151 | end; |
---|