| 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 |
|