lemon-project-template-glpk

comparison deps/glpk/examples/zebra.mod @ 11:4fc6ad2fb8a6

find changesets by author, revision, files, or words in the commit message
Test GLPK in src/main.cc
author Alpar Juttner <alpar@cs.elte.hu>
date Sun, 06 Nov 2011 21:43:29 +0100
parents
children
comparison
equal deleted inserted replaced
-1:000000000000 0:124e88f1d0a9
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;