lemon-project-template-glpk

annotate deps/glpk/examples/zebra.mod @ 9:33de93886c88

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