Wolf,goat,Cabbage works with my changes and AcrossTheRiver
From CSWiki
Wolf, goat, cabbage
import java.util.ArrayList; import JaCoP.*; /* A farmer wants to transfer a wolf, a goat, and a cabbage from the * left bank of the river to the right bank. If left alone, 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). * * Here is one of the many pages on which one can play this game: * http://perso.orange.fr/jeux.lulu/html/anglais/loupChe/loupChe1.htm */ public class WGC_Object { public static FDstore store; public static ArrayList<FDV> fdvList; 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 <= 16; i+=2) if (canSolveIn(i)) return; } /** Can wgc be solved in numberOfStates states? */ private static boolean canSolveIn(int numberOfStates) { store = new FDstore(); fdvList = new ArrayList<FDV>(); WGC_State[] states = new WGC_State[numberOfStates]; for (int j = 0; j < numberOfStates; j++) { states[j] = new WGC_State(j, numberOfStates-1); if (j > 0) store.impose(states[j-1].oneStepTo(states[j])); } /* Search search = new Search(); search.setPrintInfo(false); boolean result = search.labeling(store, fdvList, new IndomainMin(), new Delete());*/ boolean result = Solver.searchOne(store, fdvList, new SearchOne(), new IndomainMin(),new Delete(new MostConstrainedDynamic())); 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].singleton() && states[j].singleton()) { FDstore st = new FDstore(); ArrayList<FDV> fdvL = new ArrayList<FDV>(); states[j-1].addToFDVList(); states[j].addToFDVList(); st.impose(states[j-1].oneStepTo(states[j])); /* Search search = new Search(); search.setPrintInfo(false); boolean result = search.labeling(st, fdvL, new IndomainMin(), new Delete());*/ boolean result = Solver.searchOne(store, fdvList, new SearchOne(), new IndomainMin(),new Delete(new MostConstrainedDynamic())); System.out.print(result ? " --> " : " -/-> "); } else System.out.print(" --> "); } System.out.print(states[j]); } System.out.println(); } private static class WGC_State { //int farmer; FDV wolf, goat, cabbage,farmer; public WGC_State(int index, int lastState) { // The farmer alternates between left and right. // farmer = index % 2; new Or(new XeqC(farmer,0),new XeqC(farmer,1)), // Must end with all elements on the right bank (1). // Must start with all elements on the left bank (0). farmer =new FDV(store,index == lastState ? 1 : 0, index == 0 ? 0 : 1); wolf = new FDV(store, index == lastState ? 1 : 0, index == 0 ? 0 : 1); goat = new FDV(store, index == lastState ? 1 : 0, index == 0 ? 0 : 1); cabbage = new FDV(store, index == lastState ? 1 : 0, index == 0 ? 0 : 1); addToFDVList(); } private void addElt(StringBuffer left, StringBuffer right, char c, int pos) { if (pos == 0) left.append(c); else right.append(c); } public void addToFDVList() { fdvList.add(farmer); fdvList.add(wolf); fdvList.add(goat); fdvList.add(cabbage); } /** A state is valid if the farmer is with either the goat or both the wolf and cabbage. * @return the constraint */ public Constraint isValid() { return new And(new IfThen(new XeqY(wolf,goat),new XeqY(goat,farmer)), new IfThen(new XeqY(goat, cabbage), new XeqY(cabbage, farmer))); } public Constraint oneStepTo(WGC_State next) { return new And(new Constraint[] { // At most one of wgc has changed. new Or(new Constraint[] { new And(new Constraint[] {new XeqY(wolf, next.wolf), new XeqY(goat, next.goat), new XeqY(cabbage, next.cabbage), new XneqY(farmer,next.farmer) }), new And(new Constraint[] {new XneqY(wolf, next.wolf), new XeqY(goat, next.goat), new XeqY(cabbage, next.cabbage), new XneqY(farmer,next.farmer) }), new And(new Constraint[] {new XeqY(wolf, next.wolf), new XneqY(goat, next.goat), new XeqY(cabbage, next.cabbage), new XneqY(farmer,next.farmer) }), new And(new Constraint[] {new XeqY(wolf, next.wolf), new XeqY(goat, next.goat), new XneqY(cabbage, next.cabbage), new XneqY(farmer,next.farmer) }), }), // The next state is valid. next.isValid()}); } public boolean singleton() { return wolf.singleton() && goat.singleton() && cabbage.singleton() && farmer.singleton() ; } @Override public String toString() { StringBuffer left = new StringBuffer(); StringBuffer right = new StringBuffer(); if (!(wolf.singleton() && goat.singleton() && cabbage.singleton() && farmer.singleton())) return "?"; addElt(left, right, 'f', farmer.value()); addElt(left, right, 'w', wolf.value()); addElt(left, right, 'g', goat.value()); addElt(left, right, 'c', cabbage.value()); return left + "|" + right; } } }
Across The River
import java.util.ArrayList; import JaCoP.*; public class AcrossRiver { public static FDstore store; public static ArrayList<FDV> fdvList; 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 = 10; i <= 20; i+=2) if (canSolveIn(i)) return; } /** Can wgc be solved in numberOfStates states? */ private static boolean canSolveIn(int numberOfStates) { store = new FDstore(); fdvList = new ArrayList<FDV>(); River_State[] states = new River_State[numberOfStates]; for (int j = 0; j < numberOfStates; j++) { states[j] = new River_State(j, numberOfStates-1); if (j > 0) store.impose(states[j-1].oneStepTo(states[j])); } boolean result = Solver.searchOne(store, fdvList, new SearchOne(), new IndomainMin(),new Delete(new MostConstrainedDynamic())); printStateTransitions(result, states); return result; } private static void printStateTransitions(boolean solved, River_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].singleton() && states[j].singleton()) { FDstore st = new FDstore(); ArrayList<FDV> fdvL = new ArrayList<FDV>(); states[j-1].addToFDVList(); states[j].addToFDVList(); st.impose(states[j-1].oneStepTo(states[j])); boolean result = Solver.searchOne(store, fdvL, new SearchOne(), new IndomainMin(),new Delete(new MostConstrainedDynamic())); System.out.print(result ? " --> " : " -/-> "); } else System.out.print(" --> "); } System.out.print(states[j]); } System.out.println(); } private static class River_State { //int mom, dad, cop; FDV raft; FDV mom, dad, cop; FDV girl1,girl2, boy1,boy2,thief; public River_State(int index, int lastState) { raft = new FDV(store, index == lastState ? 1 : 0, index == 0 ? 0 : 1); mom = new FDV(store, index == lastState ? 1 : 0, index == 0 ? 0 : 1); dad = new FDV(store, index == lastState ? 1 : 0, index == 0 ? 0 : 1); cop = new FDV(store, index == lastState ? 1 : 0, index == 0 ? 0 : 1); girl1 = new FDV(store, index == lastState ? 1 : 0, index == 0 ? 0 : 1); girl2 = new FDV(store, index == lastState ? 1 : 0, index == 0 ? 0 : 1); boy1 = new FDV(store, index == lastState ? 1 : 0, index == 0 ? 0 : 1); boy2 = new FDV(store, index == lastState ? 1 : 0, index == 0 ? 0 : 1); thief = new FDV(store, index == lastState ? 1 : 0, index == 0 ? 0 : 1); addToFDVList(); } private void addElt(StringBuffer left, StringBuffer right, char c, int pos) { if (pos == 0) left.append(c); else right.append(c); } public void addToFDVList() { fdvList.add(raft); fdvList.add(girl1); fdvList.add(girl2); fdvList.add(boy1); fdvList.add(boy2); fdvList.add(thief); fdvList.add(mom); fdvList.add(dad); fdvList.add(cop); } /** A state is valid if the farmer is with either the goat or both the wolf and cabbage. * @return the constraint */ /*Only 2 persons on the raft at a time The father can not stay with any of the daughters without their mother's presence The mother can not stay with any of the sons without their father's presence The thief (striped shirt) can not stay with any family member if the Policeman is not there Only the Father, the Mother and the Policeman know how to operate the raft*/ public Constraint isValid() { Constraint[] thie={ new IfThen(new XeqY(thief,dad),new XeqY(thief,cop)), new IfThen(new XeqY(thief,mom),new XeqY(thief,cop)), new IfThen(new XeqY(thief,girl1),new XeqY(thief,cop)), new IfThen(new XeqY(thief,girl2),new XeqY(thief,cop)), new IfThen(new XeqY(thief,boy1),new XeqY(thief,cop)), new IfThen(new XeqY(thief,boy2),new XeqY(thief,cop))}; Constraint[] kids={new IfThen(new XeqY(girl1,dad),new XeqY(girl1,mom)), new IfThen(new XeqY(girl2,dad),new XeqY(girl2,mom)), new IfThen(new XeqY(boy1,mom),new XeqY(boy1,dad)), new IfThen(new XeqY(boy2,mom),new XeqY(boy2,dad))}; return new And(new And(thie),new And(kids)); } public Constraint oneStepTo(River_State next) { Constraint[] driver={new And(new XeqY(mom, raft),new And(new Constraint[]{new XeqY(dad, next.dad),new XeqY(cop, next.cop),new XneqY(mom,next.mom)})), new And(new XeqY(dad, raft),new And(new Constraint[]{new XeqY(mom, next.mom),new XeqY(cop, next.cop),new XneqY(dad,next.dad)})), new And(new XeqY(cop, raft),new And(new Constraint[]{new XeqY(dad, next.dad),new XeqY(mom, next.mom),new XneqY(cop,next.cop)})) }; return new And(new Constraint[] { // At most one of wgc has changed. new Or(new Constraint[] { new And(new Constraint[] { new XeqY(girl1, next.girl1), new XeqY(girl2, next.girl2), new XeqY(boy1, next.boy1), new XeqY(boy2, next.boy2), new XeqY(thief, next.thief), new Or(driver), new XneqY(raft,next.raft) }), new And(new Constraint[] {new XeqY(girl1,raft), new XneqY(girl1, next.girl1), new XeqY(girl2, next.girl2), new XeqY(boy1, next.boy1), new XeqY(boy2, next.boy2), new XeqY(thief, next.thief), new Or(driver), new XneqY(raft,next.raft) }), new And(new Constraint[] {new XeqY(girl1, next.girl1), new XeqY(girl2,raft), new XneqY(girl2, next.girl2), new XeqY(boy1, next.boy1), new XeqY(boy2, next.boy2), new XeqY(thief, next.thief), new Or(driver), new XneqY(raft,next.raft) }), new And(new Constraint[] {new XeqY(girl1, next.girl1), new XeqY(girl2, next.girl2), new XeqY(boy1,raft), new XneqY(boy1, next.boy1), new XeqY(boy2, next.boy2), new XeqY(thief, next.thief), new Or(driver), new XneqY(raft,next.raft) }), new And(new Constraint[] {new XeqY(girl1, next.girl1), new XeqY(girl2, next.girl2), new XeqY(boy1, next.boy1), new XeqY(boy2,raft), new XneqY(boy2, next.boy2), new XeqY(thief, next.thief), new Or(driver), new XneqY(raft,next.raft) }), new And(new Constraint[] {new XeqY(girl1, next.girl1), new XeqY(girl2, next.girl2), new XeqY(boy1, next.boy1), new XeqY(boy2, next.boy2), new XeqY(thief,raft), new XneqY(thief, next.thief), new Or(driver), new XneqY(raft,next.raft) }), new And(new Constraint[] {new XeqY(girl1, next.girl1), new XeqY(girl2, next.girl2), new XeqY(boy1, next.boy1), new XeqY(boy2, next.boy2), new XeqY(thief, next.thief), new XeqY(mom,raft), new XneqY(mom,next.mom), new Or(new And(new XneqY(dad, next.dad),new And(new XeqY(dad,raft),new XeqY(cop, next.cop))),new And(new XneqY(cop, next.cop),new And(new XeqY(cop,raft),new XeqY(dad, next.dad)))), new XneqY(raft,next.raft) }), new And(new Constraint[] {new XeqY(girl1, next.girl1), new XeqY(girl2, next.girl2), new XeqY(boy1, next.boy1), new XeqY(boy2, next.boy2), new XeqY(thief, next.thief), new XneqY(dad,next.dad), new XeqY(dad,raft), new Or(new And(new XneqY(mom, next.mom),new And(new XeqY(mom,raft),new XeqY(cop, next.cop))),new And(new XneqY(cop, next.cop),new And(new XeqY(cop,raft),new XeqY(mom, next.mom)))), new XneqY(raft,next.raft) }), new And(new Constraint[] {new XeqY(girl1, next.girl1), new XeqY(girl2, next.girl2), new XeqY(boy1, next.boy1), new XeqY(boy2, next.boy2), new XeqY(thief, next.thief), new XneqY(cop,next.cop), new XeqY(cop,raft), new Or(new And(new XneqY(mom, next.mom),new And(new XeqY(mom,raft),new XeqY(dad, next.dad))),new And(new XneqY(dad, next.dad),new And(new XeqY(dad,raft),new XeqY(mom, next.mom)))), new XneqY(raft,next.raft) }), }), // The next state is valid. next.isValid()}); } public boolean singleton() { return girl1.singleton() && girl2.singleton() && boy1.singleton() && boy2.singleton()&& thief.singleton() && mom.singleton() && dad.singleton() && cop.singleton()&&raft.singleton(); } @Override public String toString() { StringBuffer left = new StringBuffer(); StringBuffer right = new StringBuffer(); if (!(girl1.singleton() && girl2.singleton() && boy1.singleton() && boy2.singleton()&& thief.singleton() && mom.singleton() && dad.singleton() && cop.singleton()&&raft.singleton())) return "?"; addElt(left, right, 'm', mom.value()); addElt(left, right, 'd', dad.value()); addElt(left, right, 'c', cop.value()); addElt(left, right, 'g', girl1.value()); addElt(left, right, 'l', girl2.value()); addElt(left, right, 'b', boy1.value()); addElt(left, right, 'y', boy2.value()); addElt(left, right, 't', thief.value()); // addElt(left, right, 'r', raft.value()); return left + "|" + right; } } } /* The system takes a while to find the answer as shown D:\data\HW4>java -cp JaCoP.jar;. AcrossRiver Not solved in 10 states: mdcglbyt| --> ? --> ? --> ? --> ? --> ? --> ? --> ? --> ? --> |mdcglbyt Not solved in 12 states: mdcglbyt| --> ? --> ? --> ? --> ? --> ? --> ? --> ? --> ? --> ? --> ? --> |mdcglbyt Not solved in 14 states: mdcglbyt| --> ? --> ? --> ? --> ? --> ? --> ? --> ? --> ? --> ? --> ? --> ? --> ? --> |mdcglbyt Not solved in 16 states: mdcglbyt| --> ? --> ? --> ? --> ? --> ? --> ? --> ? --> ? --> ? --> ? --> ? --> ? --> ? --> ? --> |mdcglbyt *** Number of decisions: 14143708 *** Search depth: 210 *** Backtracks: 7071773 Solved in 18 states: mdcglbyt| --> mdglby|ct --> mdcglby|t --> mdglb|cyt --> mdc glbt|y --> mcglt|dby --> mdcglt|by --> cglt|mdby --> mcglt|dby --> mgl|dcbyt --> mdgl|cbyt --> gl|mdcbyt --> mgl|dcbyt --> g|mdclbyt --> cgt|mdlby --> t|mdcglby --> ct|mdglby --> |mdcglbyt */
