Algoritmos - Backtracking

Luego de mucho intentar entender este tipo de algoritmos, a dos semanas de mi examen logre entenderlos :D.


funcion buscar(parametros){

if(esFactible(..)){

if(no pase(..)){

pongo la ficha tentativamente
if(termine(..)){
exito
}else{
inicializo alternativas y busco entre las exitosas la mas útil
}
}//fin de "no pasé"

}//fin es factible

}

Hasta aquí parece sencillo, pero igual me llevo varios meses entenderlo :S. Por eso aquí les dejo el último ejercicio de examen que pude resolver.

Desarrolle una funcion que recibiendo un tablero de ajedres vacío,y una posicion inicial perteneciente al tablero imprima una secuencia de movimientos del caballo que no repite ninguna casilla y visita todas las casillas del tablero.

public class Camino {

public int[][] tablero;
public int nroPasos =0;
public int ocupadas = 0;

public boolean exito = false;

public Object clone(){
Camino camino = new Camino();
camino.tablero = new int[this.tablero.length][this.tablero[0].length];
camino.nroPasos = this.nroPasos;
camino.ocupadas = this.ocupadas;


for(int x=0;x < camino.tablero.length;x++){
for(int y=0;y < camino.tablero[x].length;y++){
camino.tablero[x][y] = this.tablero[x][y];
}
}


return camino;
}
}
package domain;

public class Tablero{

private int libre = 0;

private Camino mejorCamino = null;

private int[][] alternativas = {
{1,-2},
{2,-1},

{-1,2},
{-2,1},

{-1,-2},
{-2,-1},

{1,2},
{2,1}
};

private boolean exito = false;

private int[][] tablero;

private void inicializarTablero(int n){
this.tablero = new int[n][n];
for(int x=0;x < n;x++){
for(int y=0;y < n;y++){
this.tablero[x][y] =0;
}
}
}


private void buscarCamino(Camino camino, int xOrig,int yOrig){
camino.exito = false;
if(factible(camino.tablero,xOrig,yOrig)){
if(!pase(camino.tablero,xOrig,yOrig)){
//pongo tentativamente el paso en el tablero

camino.nroPasos++;
camino.ocupadas++;
camino.tablero[xOrig][yOrig] = camino.nroPasos;
if(termine(camino)){
camino.exito = true;
}else{

for(int i = 0;i < this.alternativas.length;i++){
Camino caminoAlt = (Camino)camino.clone();
this.buscarCamino(caminoAlt, xOrig+this.alternativas[i][0], yOrig+this.alternativas[i][1]);
//me quedo con las mejores opciones
if(this.mejorCamino == null){
if(caminoAlt.exito){
mejorCamino = caminoAlt;
}
}
}
}
}
}
}

private boolean termine(Camino camino) {

return camino.ocupadas == camino.tablero.length * camino.tablero[0].length;
}

/**
* decide si puede pasar
* @param laberinto
* @param x
* @param y
* @return boolean
*/
private boolean factible(int[][] tablero, int x, int y) {
return this.perteneceAlTablero(tablero, x, y);
}

private boolean pase(int[][] tablero, int x, int y) {
return tablero[x][y] !=this.libre;
}

private boolean perteneceAlTablero(int[][] tablero, int x, int y) {
if(x>=0 && y>=0){
return x < tablero.length && y < tablero[x].length;
}else{
return false;
}

}

/**
* imprime el laberinto
* @param laberinto
*/
public void imprimirCamino(Camino camino){
if(camino == null){
System.out.println("No se encontro un camino");
}else{
System.out.println("********** El caballo*********");
for(int x=0;x < camino.tablero.length;x++){
System.out.println("");
for(int y=0;y < camino.tablero[x].length;y++){
System.out.print(" " + camino.tablero[x][y] + " ");
}
}
System.out.println("");
System.out.println("*******************");
}

}

public Tablero(){
this.inicializarTablero(5);
Camino camino = new Camino();
camino.tablero = this.tablero;

this.buscarCamino(camino, 3,3);
this.imprimirCamino(mejorCamino);


}


}

Nota: perdon por la indentacion, pero me costo pila meter el codigo aca :(
si quieren el codigo bien hecho se los mando por mail