this repo has no description
dekker.one
1% RUNS ON mzn20_fd
2% RUNS ON mzn-fzn_fd
3% RUNS ON mzn20_fd_linear
4% RUNS ON mzn20_mip
5%-----------------------------------------------------------------------------%
6% The wolf, goat, cabbage problem
7%
8% A farmer has to take a wolf, goat and cabbage across a bridge
9% He can only take one thing at a time
10% The wolf and goat can't be left together alone (without the farmer)
11% The goat and cabbage can't be left alone together
12%-----------------------------------------------------------------------------%
13
14% horizon is the maximum number of steps that might be required in the plan
15int: horizon = 20;
16
17%-----------------------------------------------------------------------------%
18
19% -1..1 represent the three locations:
20% -1 is on the left bank of the river
21% 0 is on the bridge
22% 1 is on the right bank
23% A boolean, for each object, time and location,
24% holds if the object is at the location at that time
25array [1..horizon,-1..1] of var bool: wolf;
26array [1..horizon,-1..1] of var bool: goat;
27array [1..horizon,-1..1] of var bool: cabbage;
28array [1..horizon,-1..1] of var bool: farmer;
29
30%-----------------------------------------------------------------------------%
31
32% Things can only move from bank to bridge, or from bridge to bank, in one step
33constraint forall(t in 2..horizon,loc1 in -1..1,loc2 in -1..1)
34 (wolf[t-1,loc1] /\ wolf[t,loc2] -> loc1-loc2<2 /\ loc2-loc1<2);
35
36constraint forall(t in 2..horizon,loc1 in -1..1,loc2 in -1..1)
37 (goat[t-1,loc1] /\ goat[t,loc2] -> loc1-loc2<2 /\ loc2-loc1<2);
38
39constraint forall(t in 2..horizon,loc1 in -1..1,loc2 in -1..1)
40 (cabbage[t-1,loc1] /\ cabbage[t,loc2] -> loc1-loc2<2 /\ loc2-loc1<2);
41
42constraint forall(t in 2..horizon,loc1 in -1..1,loc2 in -1..1)
43 (farmer[t-1,loc1] /\ farmer[t,loc2] -> loc1-loc2<2 /\ loc2-loc1<2);
44
45% Can't leave wolf and goat, or goat and cabbage, together
46constraint (forall(t in 1..horizon,loc in -1..1)
47 ( (wolf[t,loc] /\ goat[t,loc] -> farmer[t,loc])
48 /\
49 (goat[t,loc] /\ cabbage[t,loc] -> farmer[t,loc])
50 ) );
51
52% The wolf is somewhere at each time point, and is only in one place
53constraint forall(t in 1..horizon)
54 (exists(loc in -1..1)
55 (wolf[t,loc] /\ forall(loc2 in -1..1 where loc2!=loc)
56 (not wolf[t,loc2])
57 )
58 );
59% Similarly for the goat, cabbage and farmer...
60constraint forall(t in 1..horizon)
61 (exists(loc in -1..1)
62 (goat[t,loc] /\ forall(loc2 in -1..1 where loc2!=loc)
63 (not goat[t,loc2])
64 )
65 );
66constraint forall(t in 1..horizon)
67 (exists(loc in -1..1)
68 (cabbage[t,loc] /\ forall(loc2 in -1..1 where loc2!=loc)
69 (not cabbage[t,loc2])
70 )
71 );
72constraint forall(t in 1..horizon)
73 (exists(loc in -1..1)
74 (farmer[t,loc] /\ forall(loc2 in -1..1 where loc2!=loc)
75 (not farmer[t,loc2])
76 )
77 );
78
79% The wolf can ony be on the bridge if:
80% (a) The farmer is on the bridge, and neither the goat nor the cabbage is
81% (b) The farmer was previously on the same bank as the wolf
82% (c) The farmer goes subsequently to the same bank as the wolf
83constraint forall(t in 2..horizon-1)
84 ((wolf[t,0] -> farmer[t,0] /\ not goat[t,0] /\ not cabbage[t,0]
85 /\ (wolf[t-1,1] <-> farmer[t-1,1]) /\ not farmer[t-1,0]
86 /\ (wolf[t+1,1] <-> farmer[t+1,1]) /\ not farmer[t+1,0])
87 /\
88% Similarly for the cabbage
89 (cabbage[t,0] -> farmer[t,0] /\ not goat[t,0] /\ not wolf[t,0]
90 /\ (cabbage[t-1,1] <-> farmer[t-1,1]) /\ not farmer[t-1,0]
91 /\ (cabbage[t+1,1] <-> farmer[t+1,1]) /\ not farmer[t+1,0])
92 /\
93% and for the goat
94 (goat[t,0] -> farmer[t,0] /\ not wolf[t,0] /\ not cabbage[t,0]
95 /\ (goat[t-1,1] <-> farmer[t-1,1]) /\ not farmer[t-1,0]
96 /\ (goat[t+1,1] <-> farmer[t+1,1]) /\ not farmer[t+1,0])
97 );
98
99% The animals all start on the right bank and finish on the left bank
100constraint
101 (wolf[1,1] /\ goat[1,1] /\ cabbage[1,1]
102 /\
103 wolf[horizon,-1] /\ goat[horizon,-1] /\ cabbage[horizon,-1]
104 );
105
106
107solve ::bool_search(array1d(1..3*horizon,wolf)++array1d(1..3*horizon,goat)++array1d(1..3*horizon,cabbage)++array1d(1..3*horizon,farmer), input_order, indomain_max, complete) satisfy;
108
109%-----------------------------------------------------------------------------%
110
111output [
112 "wolf : ", show(wolf), "\n",
113 "goat : ", show(goat), "\n",
114 "cabbage : ", show(cabbage), "\n",
115 "farmer : ", show(farmer), "\n"
116];
117
118%-----------------------------------------------------------------------------%
119%-----------------------------------------------------------------------------%
120