Farmer Wolf Goat Cabbage Problem 问题 In Java

fyhao · 发表于 25-8-2009 02:51 PM

本人之前无聊的时候写了一个Java程序，来解决 Farmer Wolf Goat Cabbage 过桥问题。
大家应该听过这个问题吧？就是怎么样让农夫把所有东西都带到对岸去。
但是呢，一次农夫只能带一样东西过去。
有一些规则：
如果农夫不在的话，狼会吃羊，后者羊会吃白菜。

这个程序的主要用途，就是自动探索所有解决路线，然后最终目标是可以成功显示解题步骤。
就好像这样
Move Farmer, Wolf from here to there
Move Farmer from there to here

而这个程序，本人只花了三天来写，所以程序蛮乱的。
而且有个问题就是，最后一步，就会有错误。就只差最后一步就到终点了。

本人第一次把程序发表在这里，希望有高手可以帮忙看看。。。
感谢了！

程序太长，分两个帖子来

Main.java

/**
* To demonstrate the solution of Farmer Wolf Goat Cabbage Problem in Java
*
* @author (Khor Yong Hao)
* @version (0.1)
*/
import java.util.*;
public class Main
{
public static void main(String args[]) {
new Main().solve();
}
final int FARMER = 1;
final int WOLF = 2;
final int GOAT = 4;
final int CABBAGE = 8;
Side side1 = new Side("left side", new int[]{FARMER, WOLF, GOAT, CABBAGE});
Side side2 = new Side("right side", new int[]{});
LinkedHashSet states = new LinkedHashSet(); // insertion order unique element
public void solve() {
// initialize
states.add(new State(side1, side2));
reach_to(side1, side2);
}
// reach side1 to side2
public void reach_to(Side side1, Side side2) {
printSides();
checkMove(side1, side2);
// for testing purpose
/*
printStates(states);
System.out.println("state: " + checkRepeatState());
move_to(side1.getSlot(), side1, side2);
printStates(states);
System.out.println("state: " + checkRepeatState());
move_to(side2.getSlot(), side2, side1);
printStates(states);
System.out.println("state: " + checkRepeatState());
System.out.println(checkGoal());
printStates(states);
*/
printSides();
}
public void checkMove(Side side1, Side side2) {
if(checkGoal()) {
System.out.println("The Problem Solved");
System.exit(0);
return;
}
if(checkExist(FARMER, side1)) {
//System.out.println("farmer at side " + side1.getName());
try_move(side1, side2);
} else if(checkExist(FARMER, side2)) {
//System.out.println("farmer at side " + side2.getName());
try_move(side2, side1);
}
}
public boolean checkGoal() {
if(side1.getSlot().length == 0 && side2.getSlot().length == 4) {
return true;
}
return false;
}
// check if target exist in that side
public boolean checkExist(int target, Side side) {
for(int i=0; i<side.getSlot().length; i++) {
if(side.getSlot()[i] == target) {
return true;
}
}
return false;
}
public boolean checkTargetExist(int[] targets, Side side) {
boolean result = true;
String notExistTargets = "";
for(int i=0; i<targets.length; i++) {
if(!checkExist(targets[i], side)) {
result = false;
notExistTargets += getName(targets[i]) + " ";
}
}
if(!result) {
//System.out.println("Target: " + notExistTargets + "not existed in " + side.getName());
}
return result;
}
public void try_move(Side side1, Side side2) {
//System.out.println("side1 slot length: " + side1.getSlot().length);
for(int i=0; i<side1.getSlot().length; i++/*, System.out.println("i++")*/) {
//System.out.println("i: " + i);
int successCount = 0;
if(side1.getSlot()[i] != FARMER) {
int[] moveTargets = new int[] {FARMER, side1.getSlot()[i]};
// move side1 to side2 first
try_move_to(moveTargets, side1, side2);
// check eating rule
// if break rule, move back (backtracking)
// if repeat, go back
//System.out.println("11111111111111");
if(checkBreakRule(side1) || checkBreakRule(side2) || checkRepeatState()) {
try_move_to(moveTargets, side2, side1);
//System.out.println("22222222222222");
} else {
// this is success route, so print
successCount++;
addState();
printMove(moveTargets, side1, side2);
checkMove(side1, side2); // recursive continue to search
//System.out.println("33333333333333");
}
//System.out.println("successcount: " + successCount);
// move farmer only if other already try
if(i == side1.getSlot().length - 1 && successCount == 0) {
try_move_to(new int[]{FARMER}, side1, side2);
if(checkBreakRule(side1) || checkBreakRule(side2) || checkRepeatState()) {
try_move_to(new int[]{FARMER}, side2, side1);
} else {
addState();
printMove(new int[]{FARMER}, side1, side2);
checkMove(side1, side2);
//System.out.println("44444444444444");
}
}
if(successCount > 0 && checkRepeatState()) {
try_move_to(moveTargets, side2, side1);
continue;
}
}
}
}
public boolean checkBreakRule(Side side) {
if(sum(side) == 12) {
// GOAT eat CABBAGE
//System.out.println("OOPS, goat eat cabbage");
return true;
} else if(sum(side) == 6) {
// WOLF eat GOAT
//System.out.println("OOPS, wolf eat goat");
return true;
}
return false;
}
public boolean checkRepeatState() {
/*
if(states.contains(new State(side1.getSlot().clone(), side2.getSlot().clone()))) {
return true;
}
*/
Iterator it = states.iterator();
int t = 0;
int count = 0;
while(it.hasNext() && (count++ < states.size() - 1)) {
State state = (State) it.next();
if(state.isSameState(side1, side2)) {
t++;
}
}
return t>0;
}

复制代码

fyhao · 发表于 25-8-2009 02:53 PM

public int sum(Side side) {
int sum = 0;
for(int i=0; i<side.getSlot().length; i++) {
sum += side.getSlot()[i];
}
return sum;
}
// move targets from side1 to side2
public void move_to(int[] targets, Side side1, Side side2) {
if(try_move_to(targets, side1, side2)) {
printMove(targets, side1, side2);
}
}
public boolean try_move_to(int[] targets, Side side1, Side side2) {
// check target exist or not
if(!checkTargetExist(targets, side1)) {
return false;
// out
}
// give temporary storage
int[] temp1 = new int[side1.getSlot().length - targets.length];
int[] temp2 = new int[side2.getSlot().length + targets.length];
int m=0;
// move side1 into temp1 first
// here got bug
for(int n=0; n<side1.getSlot().length; n++) {
// all targets not exists then add temp
int t = 0;
for(int p=0; p<targets.length; p++) {
if(targets[p] == side1.getSlot()[n]) {
t++; // target exist
}
}
if(t == 0) {
temp1[m++] = side1.getSlot()[n];
}
}
// move side2 into temp2 first
for(m=0; m<side2.getSlot().length; m++) {
temp2[m] = side2.getSlot()[m];
}
for(int i=0; i<targets.length; i++) {
temp2[m++] = targets[i];
}
// update new data
side1.setSlot(temp1);
side2.setSlot(temp2);
addState();
//printSides();
return true;
}
public void printMove(int[] targets, Side side1, Side side2) {
System.out.print("Move ");
for(int i=0; i<targets.length; i++) {
System.out.print(getName(targets[i]) + " ");
}
System.out.println("from " + side1.getName() + " to " + side2.getName());
}
public String getName(int obj) {
String output = null;
switch(obj) {
case FARMER:
output = "farmer";
break;
case WOLF:
output = "wolf";
break;
case GOAT:
output = "goat";
break;
case CABBAGE:
output = "cabbage";
break;
}
return output;
}
public void printSide(Side side) {
System.out.print(side.getName() + ": ");
for(int i=0; i<side.getSlot().length; i++) {
System.out.print(getName(side.getSlot()[i]) + " ");
}
System.out.println();
}
public void printSides() {
System.out.println("--------------------------------");
printSide(side1);
printSide(side2);
System.out.println("--------------------------------");
}
public void printArray(Side side) {
int[] array = side.getSlot();
System.out.print("Array: ");
for(int i=0; i<array.length; i++) {
System.out.print(getName(array[i]) + " ");
}
System.out.println();
}
public void printStates(LinkedHashSet states) {
Iterator it = states.iterator();
System.out.println("States: ");
while(it.hasNext()) {
State state = (State) it.next();
System.out.print("side 1 ");
printArray(state.getSide1());
System.out.print("side 2 ");
printArray(state.getSide2());
}
System.out.println();
}
public void addState() {
// insert state
State state = new State(side1, side2);
states.add(state);
}
}
class Side extends Object implements Cloneable {
public static int count = 0;
private int counter = ++count;
private int[] slot = new int[4];
private String name;
public Side(String name, int[] slot) {
this.name = name;
this.slot = slot;
}
public int[] getSlot() {
return slot;
}
public void setSlot(int[] slot) {
java.util.Arrays.sort(slot);
this.slot = slot;
}
public String getName() {
return name;
}
public boolean equals(Object obj) {
int[] sideObj = (int[])(((Side) obj).getSlot());
if(sideObj.length + slot.length == 0) {
return true;
} else if(slot.length == 0 || sideObj.length == 0) {
return false;
}
for(int i=0; i<sideObj.length; i++) {
try {
if(sideObj[i] != slot[i]) {
//System.out.println("side obj: " + sideObj[i] + " :::: slot[i]: " + slot[i]);
return false;
}
} catch (ArrayIndexOutOfBoundsException e) {
System.err.println(e);
return false;
}
}
return true;
}
public Side clone() {
Side side = null;
try {
side = (Side) super.clone();
} catch (CloneNotSupportedException e) {
System.err.println(e);
}
return side;
}
}
class State {
Side side1;
Side side2;
public State(Side side1, Side side2) {
this.side1 = side1.clone();
this.side2 = side2.clone();
}
public boolean isSameState(Side sideA, Side sideB) {
/*
System.out.print("same state side1 ");
printArray(side1);
System.out.print("same state side2 ");
printArray(side2);
System.out.print("same state sideA ");
printArray(sideA);
System.out.print("same state sideB ");
printArray(sideB);
System.out.println("same state end");
System.out.println("side1.equals(sideA) = " + side1.equals(sideA) + " :::: " + "side2.equals(sideB) = " + side2.equals(sideB));
//return true;
*/
if(side1.equals(sideA) && side2.equals(sideB)) {
return true;
}
return false;
}
public Side getSide1() {
return side1;
}
public Side getSide2() {
return side2;
}
public void printArray(Side side) {
int[] array = side.getSlot();
System.out.print("Array: ");
for(int i=0; i<array.length; i++) {
System.out.print(array[i] + " ");
}
System.out.println();
}
}

复制代码

希望各位高手能帮忙看看。

		自动登录	找回密码
密码			注册

Farmer Wolf Goat Cabbage Problem 问题 In Java

所属分类: 电脑手机

浏览过的版块