Courses/CS 460/Fall 2006/Wolf-Goat-Cabbage
From CSWiki
[edit] Code
A farmer wishes to transfer (by boat) a wolf, a goat, and a cabbage from the left bank of a river to the right bank. If left unsupervised, the wolf will eat the goat and the goat will eat the cabbage, but nothing will happen as long as the farmer is near.
Beside the farmer there is only room for one item in the boat.
The initial state might be represented as fwgc| (all on the left).
The goal state might be represented as |fwgc (all on the right).
This problem is a challenge for constaint programming because we don't know in advance how many intermediate states are required.
We use iterative deepending to determine the number of states.
Here is one of the many pages on which one can play this game.
package examples;
import choco.Constraint;
import choco.Problem;
import choco.integer.IntDomainVar;
public class WGC {
public static void main(String[] args) {
// Since we start on the left bank and end on the right
// there must be an even number of states. Let i be
// the number of states, including the start and end states.
for (int i = 2; i <= 32; i += 2) if (canSolveIn(i)) return;
}
/** Can wgc be solved in numberOfStates states? */
private static boolean canSolveIn(int numberOfStates) {
// Create the problem.
Problem wgc_problem = new Problem();
// Create an array of numberOfStates states. The start
// state and the end state are fixed. The intermediate
// states are unknown as yet.
WGC_State[] states = new WGC_State[numberOfStates];
for (int j = 0; j < numberOfStates; j++) {
// Create state[j]. Pass the index of the final state.
states[j] = new WGC_State(wgc_problem, j, numberOfStates-1);
// The State method oneStepTo() returns the constraint
// that requires the argument state to be a valid
// successor of itself.
if (j > 0) wgc_problem.post(states[j-1].oneStepTo(wgc_problem, states[j]));
}
boolean result = wgc_problem.solve();
printStateTransitions(result, states);
return result;
}
private static void printStateTransitions(boolean solved, WGC_State[] states) {
System.out.print((solved? "S" : "Not s") + "olved in " + states.length + " states: ");
for (int j = 0; j < states.length; j++) {
if (j > 0) {
if ( states[j-1].isInstantiated()
|| states[j].isInstantiated()
|| !states[j-1].canTransitionTo(states[j]))
System.out.print(" -/-> ");
else System.out.print(" --> ");
}
System.out.print(states[j]);
}
System.out.println();
}
private static class WGC_State {
int farmer;
IntDomainVar wolf, goat, cabbage;
public WGC_State(Problem problem, int index, int lastState) {
// The farmer alternates between left and right.
farmer = index % 2;
wolf = createWGC_IntVar(problem, index, lastState, "wolf");
goat = createWGC_IntVar(problem, index, lastState, "goat");
cabbage = createWGC_IntVar(problem, index, lastState, "cabbage");
}
private void addElt(StringBuffer left, StringBuffer right, char c, int pos) {
(pos == 0 ? left : right).append(c);
}
public boolean canTransitionTo(WGC_State next) {
return
farmer != next.farmer &&
(
(wolf == next.wolf && goat == next.goat && cabbage == next.cabbage) ||
(wolf != next.wolf && goat == next.goat && cabbage == next.cabbage) ||
(wolf == next.wolf && goat != next.goat && cabbage == next.cabbage) ||
(wolf == next.wolf && goat == next.goat && cabbage != next.cabbage)
);
}
/** Create an IntVar for the wolf, goat, or cabbage. */
private IntDomainVar createWGC_IntVar(Problem problem,
int index, int lastState,
String name) {
// Must end with all elements on the right bank (1).
// Must start with all elements on the left bank (0).
return problem.makeEnumIntVar(name + "[" + index + "]",
index == lastState ? 1 : 0, index == 0 ? 0 : 1);
}
public boolean isInstantiated() {
return wolf.isInstantiated() && goat.isInstantiated() && cabbage.isInstantiated();
}
/** A state is valid if the farmer is with either (a) the goat or
* (b) both the wolf and cabbage.
* @return the constraint
*/
public Constraint isValid(Problem problem) {
return
problem.or(problem.eq(goat, farmer),
problem.and(problem.eq(wolf, farmer),
problem.eq(cabbage, farmer)));
}
/** This constraint says that the next state is a valid trasition from this
* one. A transition is valid if the next state is valid and if at most
* one of the wolf, goat, and cabbage has changed. We don't have to
* check to be sure the farmer has changed. That was set up when the
* states were defined. In any case, that would be a test that
* would be made at the Java level since farmer is an instance
* variable and not an IntDomainVar.
* @param problem the problem. We need this because we need to
* know in which problem the constraints are being created. (Seems
* strange. One should be able to create a constraint outside a
* problem and then post it to the relevant problem.)
* @param next the next state
* @return the constraint
*/
public Constraint oneStepTo(Problem problem, WGC_State next) {
return
problem.and(
next.isValid(problem),
problem.or(
new Constraint[] {
// None of wgc has changed.
problem.and(problem.eq(wolf, next.wolf),
problem.eq(goat, next.goat),
problem.eq(cabbage, next.cabbage)),
// Only the wolf has changed.
problem.and(problem.neq(wolf, next.wolf),
problem.eq(goat, next.goat),
problem.eq(cabbage, next.cabbage)),
// Only the goat has changed.
problem.and(problem.eq(wolf, next.wolf),
problem.neq(goat, next.goat),
problem.eq(cabbage, next.cabbage)),
// Only the cabbage has changed.
problem.and(problem.eq(wolf, next.wolf),
problem.eq(goat, next.goat),
problem.neq(cabbage, next.cabbage))}));
}
@Override
public String toString() {
StringBuffer left = new StringBuffer();
StringBuffer right = new StringBuffer();
if (!(wolf.isInstantiated() && goat.isInstantiated() && cabbage.isInstantiated()))
return "?";
addElt(left, right, 'f', farmer);
addElt(left, right, 'w', wolf.getVal());
addElt(left, right, 'g', goat.getVal());
addElt(left, right, 'c', cabbage.getVal());
return left + "|" + right;
}
}
}
[edit] Outout
As currently written either the code has a bug or Choco has a bug. It concludes that the problem can't be solved in two states. But then it runs into this exception deep in the bowels of Choco.
Not solved in 2 states: fwgc| -/-> |fwgc Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1 at choco.bool.LargeDisjunction.checkStatus(LargeDisjunction.java:64) at choco.bool.LargeDisjunction.awakeOnInst(LargeDisjunction.java:148) at choco.bool.BinConjunction.awakeOnInst(BinConjunction.java:57) at choco.integer.var.IntVarEvent.propagateInstEvent(IntVarEvent.java:215) at choco.integer.var.IntVarEvent.propagateEvent(IntVarEvent.java:172) at choco.prop.VarEventQueue.propagateSomeEvents(VarEventQueue.java:54) at choco.AbstractProblem.propagate(AbstractProblem.java:260) at choco.search.AssignVar.goDownBranch(AssignVar.java:62) at choco.search.AbstractGlobalSearchSolver.nextSolution(AbstractGlobalSearchSolver.java:371) at choco.search.AbstractGlobalSearchSolver.incrementalRun(AbstractGlobalSearchSolver.java:149) at choco.Solver.launch(Solver.java:144) at choco.Problem.solve(Problem.java:458) at examples.WGC.canSolveIn(WGC.java:42) at examples.WGC.main(WGC.java:30)
In fact, the problem can be solved in 8 states. If one gives it 8 states from the start, one gets the same exception.
