this repo has no description
dekker.one
1% wolfgoatetc.mzn
2% ft=zinc ts=4 sw=4 et
3%
4% RUNS ON mzn20_fd
5% RUNS ON mzn-fzn_fd
6% RUNS ON mzn20_mip
7%
8% XXX why is lazyfd so slow with this?
9%
10% The wolf, goat, and cabbage problem.
11%
12% A farmer has to transport his wolf, goat, and cabbage from his farm, across
13% the river in his rowboat, to the market on the far bank. He can carry only
14% one item at a time in his boat. He cannot leave the wolf alone with the
15% goat or the goat alone with the cabbage.
16
17set of int: loc = 1..3;
18loc: farm = 1;
19loc: boat = 2;
20loc: market = 3;
21
22set of int: obj = 0..3;
23obj: F = 0;
24obj: W = 1;
25obj: G = 2;
26obj: C = 3;
27
28int: max_steps = 15;
29
30set of int: step = 1..max_steps;
31
32array [step, obj] of var loc: L;
33
34% Initial conditions.
35%
36constraint L[1, W] = farm;
37constraint L[1, G] = farm;
38constraint L[1, C] = farm;
39constraint L[1, F] = farm;
40
41% The goal: move the wolf, goat, and cabbage to the market.
42%
43var step: solved;
44
45constraint
46 L[solved, W] = market
47/\ L[solved, G] = market
48/\ L[solved, C] = market;
49
50% We can't leave the wolf alone with the goat
51% or the goat alone with the cabbage.
52%
53constraint
54 forall (s in step) (
55 L[s, F] = L[s, G]
56 \/ ( L[s, G] != L[s, C]
57 /\ L[s, G] != L[s, W]
58 )
59 );
60
61% The actions. At every step the farmer moves from one bank to the other;
62% he may take something with him.
63%
64constraint
65 forall (s in step diff {max_steps - 1, max_steps} where s mod 2 = 1) (
66 exists (x in {W, G, C, F}, a, b in {farm, market} where a != b) (
67 move(s, x, a, b)
68 )
69 );
70
71% Each move goes via the boat. Any object not moving stays where it is.
72%
73predicate move(step: s, obj: x, loc: from, loc: to) =
74 L[s, F] = from
75/\ L[s, x] = from
76/\ L[s + 1, F] = boat
77/\ L[s + 1, x] = boat
78/\ L[s + 2, F] = to
79/\ L[s + 2, x] = to
80/\ forall (y in {W, G, C} diff {x}) (
81 L[s + 1, y] = L[s, y]
82 /\ L[s + 2, y] = L[s, y]
83 );
84
85% The plan is the move (other than the farmer) at each step.
86%
87array [step] of var obj: A =
88 [ bool2int(s < solved) *
89 ( W * bool2int(L[s, W] != L[s + 1, W])
90 + G * bool2int(L[s, G] != L[s + 1, G])
91 + C * bool2int(L[s, C] != L[s + 1, C])
92 )
93 | s in step diff {max_steps}
94 ] ++ [0];
95
96solve
97 :: int_search(
98 [L[s, x] | s in step, x in obj],
99 input_order, indomain_min, complete
100 )
101 minimize solved;
102
103output [
104 "A = ", show(A), ";\n",
105 "solved = ", show(solved), ";"
106];