Apurada
09 de Marzo del 2005

he de resolver por backtracking recursivo Una solucion el acertijo del cruce del rio de la oveja,el barquero y la lechuga llegando a la otra orilla sin que se coman mutuamente y estoy to¡talmente atascada
el codigo que he desarrollado es el siguiente:
/* * ACERTIJO.java */

public class Acertijo {
int cdto;
boolean acertado=false;
boolean[] orilla = new boolean[4];
boolean[] norilla = new boolean[4];
boolean[][] solucion = new boolean[20][4];
int contar;
boolean[] completa = new boolean[4];
public void inicializar(){
contar =0;
for (int i=0;i<4;i++){
completa[i]=false;
orilla[i]=true;
}
}



public void UnaSolucion( boolean[] orilla){
IniciarCdto();
do{
SeleccionarCdto();
if(Aceptable()){
AnotarCdto();
if(!SolucionCompleta()){
UnaSolucion(norilla);
if (!acertado)DesanotarCdto();
}else{
acertado=true;
}
}
}while((acertado)||(QuedanCdto()));
}

public void IniciarCdto(){
cdto=-1;
}

public void SeleccionarCdto(){
cdto++;
}

public boolean Aceptable(){
boolean seComen = false;
if(orilla[cdto]==orilla[3]) {//si un elemento esta en la misma orilla que barquero
norilla=orilla;
if(cdto!=3) norilla[cdto]=!norilla[cdto];
norilla[3]=!norilla[3];
if(existe(norilla)){return false; //si esa posicion ya existia
}else{
seComen = (((norilla[1]==norilla[0])&&(norilla[3]==norilla[0])) || ((norilla[0]==norilla[2])&&(norilla[3]==norilla[0])));
return !seComen;
}
}else return false;
}

public boolean existe(boolean[] norilla){
int i=0;
while (i<contar){
if(solucion[i]==norilla) return true;
i++;
}
return false;
}
public void AnotarCdto(){
solucion[contar]=norilla;
contar++;
}

public boolean SolucionCompleta(){
return norilla==completa;
}

public void TratarSolucion(){
for(int i =0;i<contar;i++){
for(int j =0;j<4;j++){
System.out.println(solucion[i][j]);
}
}
}

public void DesanotarCdto(){
contar--;
}

public boolean QuedanCdto(){
return cdto<3;
}

public Acertijo() {
inicializar();
UnaSolucion(orilla);
if(acertado){
TratarSolucion();
}else{
System.out.println("No tiene solucion");
System.out.println (contar);
}
}
public static void main(String args[]) {
Acertijo rio = new Acertijo();
}
}