viernes, noviembre 26, 2010

Problema de las Reinas - Version 2

Problem of eight queensImage via Wikipedia
Teniendo en cuenta que en cada fila del tablero de ajedrez solo puede ir una reina, entonces es posible modelar el problema utilizando un solo vector, en el que hay tantas posiciones como filas, y el valor para cada posición es la columna en la cual se encuentra ubicada la reina de dicha fila.

La sugerencia (sin código)  para realizar esta solución está en el blog de prothotype.  La estrategia a utilizar está basada en backtracking y recursividad al igual que la solución presentada anteriormente.

public class ProblemaReinas2 {
    final int numFilas;
    int[]   tablero;
    int     contador;
    int     correctas=0;

    public ProblemaReinas2(int nf) {
        numFilas    = nf;
        tablero     = new int[nf];
        for(int i=0; i<tablero.length; i++) tablero[i]=-1;
    }

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

    public boolean resolverProblema(int fila, int columna) {
        //mostrarTablero();
        contador++;
        tablero[fila]=columna;
        correctas++;
        if(correctas==numFilas) return true;
        int[] posibles = buscarPosibles(fila+1);
        for(int c: posibles) {
            if(resolverProblema(siguienteFila(), c)) return true;
        }
        tablero[fila]=-1;
        correctas--;
        return false;
    }

    public int siguienteFila() {
        for(int i=0; i<tablero.length; i++) if(tablero[i]==-1) return i;
        return -1;
    }

    int[] buscarPosibles(int num) {
        int[] resp = new int[numFilas];
        int pos=numFilas;
        for(int i=0; i<resp.length; i++) resp[i]=i;
        for(int i=0; i<numFilas; i++) {
            if(tablero[i]!=-1) {
                resp[tablero[i]]=-1;
                pos--;
            }
        }
        for(int i=0; i<resp.length; i++) {
            if(resp[i]==-1) continue;
            for(int j=0; j<num; j++) {
                double fabs = Math.abs((num-j)*1.0/(resp[i]-tablero[j]));
                if(fabs==1.0 && resp[i]!=-1) {
                    resp[i]=-1;
                    pos--;
                    break;
                }
            }
        }
        int[] tmp = new int[pos];
        int i=0;
        for(int x: resp) if(x!=-1) tmp[i++] = x;
        return tmp;
    }

    public static void main(String[] args) {
        java.util.Random rnd  = new java.util.Random();
        int numFilas      = 8;
        int filaInicial   = rnd.nextInt(numFilas);
        int colInicial    = rnd.nextInt(numFilas);
        ProblemaReinas2 pr = new ProblemaReinas2(numFilas);
        pr.resolverProblema(filaInicial, colInicial);
        pr.mostrarTablero();
        System.out.printf("Cantidad de veces que entra al ciclo: %,d %n",  pr.contador);
    }
}
Enhanced by Zemanta

2 comentarios:

Anónimo dijo...

tampoco funciona. no mira si te pueden matar en diagonal

Anónimo dijo...

Buenos días

El blog esta desactualizado y en mi opinión abandonado pero escrito 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 un mejor ejemplo en http://jmonda.com/blog_post.php?n=algoritmo-backtracking-nreinas y mas ejemplos sobre BackTracking en http://jmonda.com/tags.php?tags=backtracking

Saludos.

Publicar un comentario

LinkWithin

Related Posts Plugin for WordPress, Blogger...

Calificar