this repo has no description
dekker.one
1/***
2!Test
3expected:
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
32set of int: loc = 1..3;
33loc: farm = 1;
34loc: boat = 2;
35loc: market = 3;
36
37set of int: obj = 0..3;
38obj: F = 0;
39obj: W = 1;
40obj: G = 2;
41obj: C = 3;
42
43int: max_steps = 15;
44
45set of int: step = 1..max_steps;
46
47array [step, obj] of var loc: L;
48
49% Initial conditions.
50%
51constraint L[1, W] = farm;
52constraint L[1, G] = farm;
53constraint L[1, C] = farm;
54constraint L[1, F] = farm;
55
56% The goal: move the wolf, goat, and cabbage to the market.
57%
58var step: solved :: add_to_output;
59
60constraint
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%
68constraint
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%
79constraint
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%
88predicate 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%
102array [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
111solve
112 :: int_search(
113 [L[s, x] | s in step, x in obj],
114 input_order, indomain_min, complete
115 )
116 minimize solved;
117