miércoles, noviembre 17, 2010

El problema del recorrido del caballo de ajedrez - backtracking

La peregrinación del caballo de ajedrez consiste en su paseo por todas las casillas del tablero sin pasar dos veces por la misma, utilizando sus movimientos: dos casillas horizontales y una vertical o a la inversa. Cuando desde la última casilla podamos pasar a la primera se trata de una "peregrinación cerrada".

Para resolver este problema se puede utilizar la técnica de backtracking con un algoritmo recursivo relativamente simple: marcar la posición solicitada, hacer una lista de las siguientes posiciones vacías a las que se puede saltar desde la posición marcar, y tomar la primera de ellas, marcándola entonces en forma recursiva. Si en alguno de los pasos recursivos no se alcanza una solución, la casilla se desmarca y se pasa a la siguiente que estaba en la lista. Si se termina la lista y no se llega a una solución, entonces se devuelve a la casilla anterior desde la que se hizo el llamado.

La solución en JAVA para esta solución es la siguiente:

public class ProblemaCaballo {
    final int numFilas;
    final int numColumnas;
    int[][] tablero;
    int     contador;

    public ProblemaCaballo(int nf, int nc) {
        numFilas = nf;
        numColumnas = nc;
        tablero     = new int[nf][nc];
    }

    public void mostrarTablero() {
        for(int i=0; i<tablero.length; i++) {
            for(int j=0; j<tablero[i].length; j++) {
                System.out.printf("  %2d  |", tablero[i][j]);
            }
            System.out.println();
            for(int j=0; j<tablero[i].length; j++) System.out.print("------+");
            System.out.println();
        }
    }

    public boolean resolverProblema(int f, int c, int num) {
            contador++;
            tablero[f][c] = num;
            if(num==numFilas*numColumnas) return true;
            int[][] posibles = buscarPosibles(f, c);
            for(int i=0; i<posibles.length; i++) {
                if(resolverProblema(posibles[i][0], posibles[i][1], num+1)) return true;
            }
            tablero[f][c]=0;
            return false;
    }

    int[][] buscarPosibles(int f, int c) {
        int[][] resp = new int[8][2];
        int     pos  = 0;
        if(esValido(f-2,c-1)){ resp[pos][0]=f-2; resp[pos++][1]=c-1; }
        if(esValido(f-2,c+1)){ resp[pos][0]=f-2; resp[pos++][1]=c+1; }
        if(esValido(f-1,c-2)){ resp[pos][0]=f-1; resp[pos++][1]=c-2; }
        if(esValido(f-1,c+2)){ resp[pos][0]=f-1; resp[pos++][1]=c+2; }
        if(esValido(f+2,c-1)){ resp[pos][0]=f+2; resp[pos++][1]=c-1; }
        if(esValido(f+2,c+1)){ resp[pos][0]=f+2; resp[pos++][1]=c+1; }
        if(esValido(f+1,c-2)){ resp[pos][0]=f+1; resp[pos++][1]=c-2; }
        if(esValido(f+1,c+2)){ resp[pos][0]=f+1; resp[pos++][1]=c+2; }
        int[][] tmp = new int[pos][2];
        for(int i=0; i<pos; i++) { tmp[i][0] = resp[i][0]; tmp[i][1]=resp[i][1]; }
        return tmp;
    }

    boolean esValido(int f, int c) {
        if(f<0 || f>numFilas-1 || c<0 || c>numColumnas-1) return false;
        if(tablero[f][c]!=0) return false;
        return true;
    }

    public static void main(String[] args) {
        ProblemaCaballo pc = new ProblemaCaballo(8,8);
        pc.resolverProblema(0,0,1);
        pc.mostrarTablero();
        System.out.printf("Cantidad de veces que entra al ciclo: %,d %n",  pc.contador);
    }
}

6 comentarios:

  1. Anónimo2:41 a.m.

    Tu codigo esta fatal, solo funciona para tableros de 5x5 y en algunos casos de 7x7, en los demas no acaba nunca, se queda iterando siempre.

    ResponderBorrar
  2. Anónimo3:24 a.m.

    por eso hay una segunda parte!

    ResponderBorrar
  3. Hola y gracias. Estos de deitel se pasaron ponen este problema en el los ejercicios del capitulo 7 y segun veo esto de recursividad y backtracking se ve en capitulo 15. Use la heuristica que explican en el mismo y solo pude conseguir 5 soluciones en 64 intentos cambiando en cada uno la casilla inicial. ¿son pocos? o ¿para lo poco que se esta bien?.

    Bueno, me podrias recomendar algun otro libro que no sea tan brusco. Gracias

    ResponderBorrar
  4. buenas amigo porque no imprime nada el codigo?

    ResponderBorrar
  5. Buenos días

    El blog esta desactualizado y en mi opinión abandonado pero escribo esto para las nuevas personas.
    El código mostrado arriba no hace uso de las propiedades BackTracking(https://es.wikipedia.org/wiki/Vuelta_atr%C3%A1s)

    El algoritmo BackTracking lo que hace es ir hacia delante y si no encuentra la solución vuelve hacia atras. Este código publicado nunca vuelve hacia atras.

    Tenéis mejores ejemplos en http://jmonda.com/tags.php?tags=backtracking

    Saludos.

    ResponderBorrar

Multiprocesamiento recursivo en JAVA 7

Una de las estrategias de diseño de algoritmos más comunes es la de "divide y vencerás", en la cual, un problema de tamaño relativ...