COIN-OR::LEMON - Graph Library

source: lemon-project-template-glpk/deps/glpk/examples/zebra.mod

subpack-glpk
Last change on this file was 9:33de93886c88, checked in by Alpar Juttner <alpar@…>, 13 years ago

Import GLPK 4.47

File size: 5.1 KB
Line 
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
48set HOUSE := { 1..5 };
49
50set COLOR := { "blue", "green", "ivory", "red", "yellow" };
51
52set NATIONALITY := { "Englishman", "Japanese", "Norwegian", "Spaniard",
53      "Ukranian" };
54
55set DRINK := { "coffee", "milk", "orange_juice", "tea", "water" };
56
57set SMOKE := { "Chesterfield", "Kools", "Lucky_Strike", "Old_Gold",
58      "Parliament" };
59
60set PET := { "dog", "fox", "horse", "snails", "zebra" };
61
62var color{HOUSE, COLOR}, binary;
63c1{h in HOUSE}: sum{c in COLOR} color[h,c] = 1;
64c2{c in COLOR}: sum{h in HOUSE} color[h,c] = 1;
65
66var nationality{HOUSE, NATIONALITY}, binary;
67n1{h in HOUSE}: sum{n in NATIONALITY} nationality[h,n] = 1;
68n2{n in NATIONALITY}: sum{h in HOUSE} nationality[h,n] = 1;
69
70var drink{HOUSE, DRINK}, binary;
71d1{h in HOUSE}: sum{d in DRINK} drink[h,d] = 1;
72d2{d in DRINK}: sum{h in HOUSE} drink[h,d] = 1;
73
74var smoke{HOUSE, SMOKE}, binary;
75s1{h in HOUSE}: sum{s in SMOKE} smoke[h,s] = 1;
76s2{s in SMOKE}: sum{h in HOUSE} smoke[h,s] = 1;
77
78var pet{HOUSE, PET}, binary;
79p1{h in HOUSE}: sum{p in PET} pet[h,p] = 1;
80p2{p in PET}: sum{h in HOUSE} pet[h,p] = 1;
81
82/* the Englishman lives in the red house */
83f2{h in HOUSE}: nationality[h,"Englishman"] = color[h,"red"];
84
85/* the Spaniard owns the dog */
86f3{h in HOUSE}: nationality[h,"Spaniard"] = pet[h,"dog"];
87
88/* coffee is drunk in the green house */
89f4{h in HOUSE}: drink[h,"coffee"] = color[h,"green"];
90
91/* the Ukrainian drinks tea */
92f5{h in HOUSE}: nationality[h,"Ukranian"] = drink[h,"tea"];
93
94/* the green house is immediately to the right of the ivory house */
95f6{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 */
99f7{h in HOUSE}: smoke[h,"Old_Gold"] = pet[h,"snails"];
100
101/* Kools are smoked in the yellow house */
102f8{h in HOUSE}: smoke[h,"Kools"] = color[h,"yellow"];
103
104/* milk is drunk in the middle house */
105f9: drink[3,"milk"] = 1;
106
107/* the Norwegian lives in the first house */
108f10: nationality[1,"Norwegian"] = 1;
109
110/* the man who smokes Chesterfields lives in the house next to the man
111   with the fox */
112f11{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 */
119f12{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 */
125f13{h in HOUSE}: smoke[h,"Lucky_Strike"] = drink[h,"orange_juice"];
126
127/* the Japanese smokes Parliaments */
128f14{h in HOUSE}: nationality[h,"Japanese"] = smoke[h,"Parliament"];
129
130/* the Norwegian lives next to the blue house */
131f15{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
136solve;
137
138printf "\n";
139printf "HOUSE  COLOR   NATIONALITY  DRINK         SMOKE         PET\n";
140for {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}
149printf "\n";
150
151end;
Note: See TracBrowser for help on using the repository browser.