Debian Codegraph @

tests/spec/unit/general/wolfgoatetc.mzn

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