lemon-project-template-glpk
diff deps/glpk/examples/zebra.mod @ 9:33de93886c88
Import GLPK 4.47
author | Alpar Juttner <alpar@cs.elte.hu> |
---|---|
date | Sun, 06 Nov 2011 20:59:10 +0100 |
parents | |
children |
line diff
1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 1.2 +++ b/deps/glpk/examples/zebra.mod Sun Nov 06 20:59:10 2011 +0100 1.3 @@ -0,0 +1,151 @@ 1.4 +/* ZEBRA, Who Owns the Zebra? */ 1.5 + 1.6 +/* Written in GNU MathProg by Andrew Makhorin <mao@gnu.org> */ 1.7 + 1.8 +######################################################################## 1.9 +# The Zebra Puzzle is a well-known logic puzzle. 1.10 +# 1.11 +# It is often called "Einstein's Puzzle" or "Einstein's Riddle" 1.12 +# because it is said to have been invented by Albert Einstein as a boy, 1.13 +# with the common claim that Einstein said "only 2 percent of the 1.14 +# world's population can solve". It is also sometimes attributed to 1.15 +# Lewis Carroll. However, there is no known evidence for Einstein's or 1.16 +# Carroll's authorship. 1.17 +# 1.18 +# There are several versions of this puzzle. The version below is 1.19 +# quoted from the first known publication in Life International 1.20 +# magazine on December 17, 1962. 1.21 +# 1.22 +# 1. There are five houses. 1.23 +# 2. The Englishman lives in the red house. 1.24 +# 3. The Spaniard owns the dog. 1.25 +# 4. Coffee is drunk in the green house. 1.26 +# 5. The Ukrainian drinks tea. 1.27 +# 6. The green house is immediately to the right of the ivory house. 1.28 +# 7. The Old Gold smoker owns snails. 1.29 +# 8. Kools are smoked in the yellow house. 1.30 +# 9. Milk is drunk in the middle house. 1.31 +# 10. The Norwegian lives in the first house. 1.32 +# 11. The man who smokes Chesterfields lives in the house next to the 1.33 +# man with the fox. 1.34 +# 12. Kools are smoked in the house next to the house where the horse 1.35 +# is kept. 1.36 +# 13. The Lucky Strike smoker drinks orange juice. 1.37 +# 14. The Japanese smokes Parliaments. 1.38 +# 15. The Norwegian lives next to the blue house. 1.39 +# 1.40 +# Now, who drinks water? Who owns the zebra? 1.41 +# 1.42 +# In the interest of clarity, it must be added that each of the five 1.43 +# houses is painted a different color, and their inhabitants are of 1.44 +# different national extractions, own different pets, drink different 1.45 +# beverages and smoke different brands of American cigarettes. One 1.46 +# other thing: In statement 6, right means your right. 1.47 +# 1.48 +# (From Wikipedia, the free encyclopedia.) 1.49 +######################################################################## 1.50 + 1.51 +set HOUSE := { 1..5 }; 1.52 + 1.53 +set COLOR := { "blue", "green", "ivory", "red", "yellow" }; 1.54 + 1.55 +set NATIONALITY := { "Englishman", "Japanese", "Norwegian", "Spaniard", 1.56 + "Ukranian" }; 1.57 + 1.58 +set DRINK := { "coffee", "milk", "orange_juice", "tea", "water" }; 1.59 + 1.60 +set SMOKE := { "Chesterfield", "Kools", "Lucky_Strike", "Old_Gold", 1.61 + "Parliament" }; 1.62 + 1.63 +set PET := { "dog", "fox", "horse", "snails", "zebra" }; 1.64 + 1.65 +var color{HOUSE, COLOR}, binary; 1.66 +c1{h in HOUSE}: sum{c in COLOR} color[h,c] = 1; 1.67 +c2{c in COLOR}: sum{h in HOUSE} color[h,c] = 1; 1.68 + 1.69 +var nationality{HOUSE, NATIONALITY}, binary; 1.70 +n1{h in HOUSE}: sum{n in NATIONALITY} nationality[h,n] = 1; 1.71 +n2{n in NATIONALITY}: sum{h in HOUSE} nationality[h,n] = 1; 1.72 + 1.73 +var drink{HOUSE, DRINK}, binary; 1.74 +d1{h in HOUSE}: sum{d in DRINK} drink[h,d] = 1; 1.75 +d2{d in DRINK}: sum{h in HOUSE} drink[h,d] = 1; 1.76 + 1.77 +var smoke{HOUSE, SMOKE}, binary; 1.78 +s1{h in HOUSE}: sum{s in SMOKE} smoke[h,s] = 1; 1.79 +s2{s in SMOKE}: sum{h in HOUSE} smoke[h,s] = 1; 1.80 + 1.81 +var pet{HOUSE, PET}, binary; 1.82 +p1{h in HOUSE}: sum{p in PET} pet[h,p] = 1; 1.83 +p2{p in PET}: sum{h in HOUSE} pet[h,p] = 1; 1.84 + 1.85 +/* the Englishman lives in the red house */ 1.86 +f2{h in HOUSE}: nationality[h,"Englishman"] = color[h,"red"]; 1.87 + 1.88 +/* the Spaniard owns the dog */ 1.89 +f3{h in HOUSE}: nationality[h,"Spaniard"] = pet[h,"dog"]; 1.90 + 1.91 +/* coffee is drunk in the green house */ 1.92 +f4{h in HOUSE}: drink[h,"coffee"] = color[h,"green"]; 1.93 + 1.94 +/* the Ukrainian drinks tea */ 1.95 +f5{h in HOUSE}: nationality[h,"Ukranian"] = drink[h,"tea"]; 1.96 + 1.97 +/* the green house is immediately to the right of the ivory house */ 1.98 +f6{h in HOUSE}: 1.99 + color[h,"green"] = if h = 1 then 0 else color[h-1,"ivory"]; 1.100 + 1.101 +/* the Old Gold smoker owns snails */ 1.102 +f7{h in HOUSE}: smoke[h,"Old_Gold"] = pet[h,"snails"]; 1.103 + 1.104 +/* Kools are smoked in the yellow house */ 1.105 +f8{h in HOUSE}: smoke[h,"Kools"] = color[h,"yellow"]; 1.106 + 1.107 +/* milk is drunk in the middle house */ 1.108 +f9: drink[3,"milk"] = 1; 1.109 + 1.110 +/* the Norwegian lives in the first house */ 1.111 +f10: nationality[1,"Norwegian"] = 1; 1.112 + 1.113 +/* the man who smokes Chesterfields lives in the house next to the man 1.114 + with the fox */ 1.115 +f11{h in HOUSE}: 1.116 + (1 - smoke[h,"Chesterfield"]) + 1.117 + (if h = 1 then 0 else pet[h-1,"fox"]) + 1.118 + (if h = 5 then 0 else pet[h+1,"fox"]) >= 1; 1.119 + 1.120 +/* Kools are smoked in the house next to the house where the horse is 1.121 + kept */ 1.122 +f12{h in HOUSE}: 1.123 + (1 - smoke[h,"Kools"]) + 1.124 + (if h = 1 then 0 else pet[h-1,"horse"]) + 1.125 + (if h = 5 then 0 else pet[h+1,"horse"]) >= 1; 1.126 + 1.127 +/* the Lucky Strike smoker drinks orange juice */ 1.128 +f13{h in HOUSE}: smoke[h,"Lucky_Strike"] = drink[h,"orange_juice"]; 1.129 + 1.130 +/* the Japanese smokes Parliaments */ 1.131 +f14{h in HOUSE}: nationality[h,"Japanese"] = smoke[h,"Parliament"]; 1.132 + 1.133 +/* the Norwegian lives next to the blue house */ 1.134 +f15{h in HOUSE}: 1.135 + (1 - nationality[h,"Norwegian"]) + 1.136 + (if h = 1 then 0 else color[h-1,"blue"]) + 1.137 + (if h = 5 then 0 else color[h+1,"blue"]) >= 1; 1.138 + 1.139 +solve; 1.140 + 1.141 +printf "\n"; 1.142 +printf "HOUSE COLOR NATIONALITY DRINK SMOKE PET\n"; 1.143 +for {h in HOUSE} 1.144 +{ printf "%5d", h; 1.145 + printf{c in COLOR: color[h,c]} " %-6s", c; 1.146 + printf{n in NATIONALITY: nationality[h,n]} " %-11s", n; 1.147 + printf{d in DRINK: drink[h,d]} " %-12s", d; 1.148 + printf{s in SMOKE: smoke[h,s]} " %-12s", s; 1.149 + printf{p in PET: pet[h,p]} " %-6s", p; 1.150 + printf "\n"; 1.151 +} 1.152 +printf "\n"; 1.153 + 1.154 +end;