| 1 |
/*** |
| 2 |
!Test |
| 3 |
expected: |
| 4 |
- !Result |
| 5 |
solution: !Solution |
| 6 |
animal: [4, 1, 2, 5, 3] |
| 7 |
colour: [3, 5, 4, 1, 2] |
| 8 |
drink: [5, 2, 3, 4, 1] |
| 9 |
nation: [3, 4, 2, 1, 5] |
| 10 |
smoke: [3, 1, 2, 4, 5] |
| 11 |
***/ |
| 12 |
|
| 13 |
% WHO OWNS THE ZEBRA? |
| 14 |
% |
| 15 |
% This is a puzzle which has been circulating the net. There are a couple |
| 16 |
% different versions out there which try to be a little more politically |
| 17 |
% correct but are essentially the same problem. |
| 18 |
% 1. There are five houses, each of a different color and inhabited by |
| 19 |
% men of different nationalities, with different pets, drinks, |
| 20 |
% and cigarettes. |
| 21 |
% 2. The Englishman lives in the red house. |
| 22 |
% 3. The Spaniard owns the dog. |
| 23 |
% 4. Coffee is drunk in the green house. |
| 24 |
% 5. The Ukrainian drinks tea. |
| 25 |
% 6. The green house is immediately to the right of the ivory house. |
| 26 |
% 7. The Old Gold smoker owns snails. |
| 27 |
% 8. Kools are smoked in the yellow house. |
| 28 |
% 9. Milk is drunk in the middle house. |
| 29 |
% 10. The Norwegian lives in the first house on the left. |
| 30 |
% 11. The man who smokes Chesterfields lives in the house next to the |
| 31 |
% man with the fox. |
| 32 |
% 12. Kools are smoked in the house next to the house where the horse is |
| 33 |
% kept. |
| 34 |
% 13. The Lucky Strike smoker drinks orange juice. |
| 35 |
% 14. The Japanese smoke Parliaments. |
| 36 |
% 15. The Norwegian lives next to the blue house. |
| 37 |
% NOW, who drinks water? And who owns the zebra? |
| 38 |
|
| 39 |
% MiniZinc Version |
| 40 |
% Peter Stuckey September 30 2006 |
| 41 |
|
| 42 |
include "globals.mzn"; |
| 43 |
|
| 44 |
%enum Nationalities = { English, Spanish, Ukrainian, Norwegian, Japanese }; |
| 45 |
set of int: Nationalities = 0..4; |
| 46 |
int: English = 0; |
| 47 |
int: Spanish = 1; |
| 48 |
int: Ukrainian = 2; |
| 49 |
int: Norwegian = 3; |
| 50 |
int: Japanese = 4; |
| 51 |
%enum Colours = { Red, Green, Ivory, Yellow, Blue }; |
| 52 |
set of int: Colours = 0..4; |
| 53 |
int: Red = 0; |
| 54 |
int: Green = 1; |
| 55 |
int: Ivory = 2; |
| 56 |
int: Yellow = 3; |
| 57 |
int: Blue = 4; |
| 58 |
%enum Animals = { Dog, Fox, Horse, Zebra, Snails }; |
| 59 |
set of int: Animals = 0..4; |
| 60 |
int: Dog = 0; |
| 61 |
int: Fox = 1; |
| 62 |
int: Horse = 2; |
| 63 |
int: Zebra = 3; |
| 64 |
int: Snails = 4; |
| 65 |
%enum Drinks = { Coffee, Tea, Milk, OrangeJuice, Water }; |
| 66 |
set of int: Drinks = 0..4; |
| 67 |
int: Coffee = 0; |
| 68 |
int: Tea = 1; |
| 69 |
int: Milk = 2; |
| 70 |
int: OrangeJuice = 3; |
| 71 |
int: Water = 4; |
| 72 |
%enum Cigarettes = { OldGold, Kools, Chesterfields, LuckyStrike, |
| 73 |
% Parliaments } ; |
| 74 |
set of int: Cigarettes = 0..4; |
| 75 |
int: OldGold = 0; |
| 76 |
int: Kools = 1; |
| 77 |
int: Chesterfields = 2; |
| 78 |
int: LuckyStrike = 3; |
| 79 |
int: Parliaments = 4; |
| 80 |
|
| 81 |
set of int: Houses = 1..5; |
| 82 |
|
| 83 |
array[Nationalities] of var Houses: nation; |
| 84 |
array[Colours] of var Houses: colour; |
| 85 |
array[Animals] of var Houses: animal; |
| 86 |
array[Drinks] of var Houses: drink; |
| 87 |
array[Cigarettes] of var Houses: smoke; |
| 88 |
|
| 89 |
predicate nextto(var Houses:h1, var Houses:h2) = |
| 90 |
h1 == h2 + 1 \/ h2 == h1 + 1; |
| 91 |
|
| 92 |
predicate rightof(var Houses:h1, var Houses:h2) = |
| 93 |
h1 == h2 + 1; |
| 94 |
|
| 95 |
predicate middle(var Houses:h) = h == 3; |
| 96 |
|
| 97 |
predicate left(var Houses:h) = h = 1; |
| 98 |
|
| 99 |
constraint |
| 100 |
alldifferent(nation) /\ |
| 101 |
alldifferent(colour) /\ |
| 102 |
alldifferent(animal) /\ |
| 103 |
alldifferent(drink) /\ |
| 104 |
alldifferent(smoke) /\ |
| 105 |
nation[English] == colour[Red] /\ |
| 106 |
nation[Spanish] == animal[Dog] /\ |
| 107 |
drink[Coffee] == colour[Green] /\ |
| 108 |
nation[Ukrainian] == drink[Tea] /\ |
| 109 |
colour[Green] `rightof` colour[Ivory] /\ |
| 110 |
smoke[OldGold] == animal[Snails] /\ |
| 111 |
smoke[Kools] == colour[Yellow] /\ |
| 112 |
middle(drink[Milk]) /\ |
| 113 |
left(nation[Norwegian]) /\ |
| 114 |
smoke[Chesterfields] `nextto` animal[Fox] /\ |
| 115 |
smoke[Kools] `nextto` animal[Horse] /\ |
| 116 |
smoke[LuckyStrike] == drink[OrangeJuice] /\ |
| 117 |
nation[Japanese] == smoke[Parliaments] /\ |
| 118 |
nation[Norwegian] `nextto` colour[Blue]; |
| 119 |
|
| 120 |
solve satisfy; |
| 121 |
|
| 122 |
output [ |
| 123 |
"zebra:\n", |
| 124 |
"nation = [", |
| 125 |
show(nation[0]), ", ", |
| 126 |
show(nation[1]), ", ", |
| 127 |
show(nation[2]), ", ", |
| 128 |
show(nation[3]), ", ", |
| 129 |
show(nation[4]), "]\n", |
| 130 |
"colour = [", |
| 131 |
show(colour[0]), ", ", |
| 132 |
show(colour[1]), ", ", |
| 133 |
show(colour[2]), ", ", |
| 134 |
show(colour[3]), ", ", |
| 135 |
show(colour[4]), "]\n", |
| 136 |
"animal = [", |
| 137 |
show(animal[0]), ", ", |
| 138 |
show(animal[1]), ", ", |
| 139 |
show(animal[2]), ", ", |
| 140 |
show(animal[3]), ", ", |
| 141 |
show(animal[4]), "]\n", |
| 142 |
"drink = [", |
| 143 |
show(drink[0]), ", ", |
| 144 |
show(drink[1]), ", ", |
| 145 |
show(drink[2]), ", ", |
| 146 |
show(drink[3]), ", ", |
| 147 |
show(drink[4]), "]\n", |
| 148 |
"smoke = [", |
| 149 |
show(smoke[0]), ", ", |
| 150 |
show(smoke[1]), ", ", |
| 151 |
show(smoke[2]), ", ", |
| 152 |
show(smoke[3]), ", ", |
| 153 |
show(smoke[4]), "]\n" |
| 154 |
]; |