jueves, noviembre 25, 2010

Problema de las Reinas

Ocho reinas reina atacarr
El siguiente programa muestra como resolver el problema de las 8 reinas, generalizado para cualquier tamaño de tablero. El problema en sí trata de encontrar una forma de posicionar n reinas en un tablero de ajedrez de tamaño n x n, de tal manera que ninguna de las reinas ataque a ninguna de las otras. Una reina ataca todas las casillas que se encuentren en la misma fila, en la misma columna, o en las diagonales de la casilla en que está ubicada.

Este problema utiliza un esquema igual al utilizado en la solución del problema del salto del caballo, modelando el tablero como una matriz de n x n y utilizando un enfoque de backtracking para marcar una casilla, generar una lista de las siguientes casillas que no están amenazadas y revisar dicha lista en forma recursiva; si no se llega a la respuesta correcta, se devuelve el proceso para continuar con las siguiente casillas de la lista.


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

    public ProblemaReinas(int nf) {
        numFilas    = nf;
        numColumnas = nf;
        tablero     = new int[nf][nf];
    }

    public void mostrarTablero() {
        for(int i=0; i<tablero.length; i++) {
            for(int j=0; j<tablero[i].length; j++) {
                if(tablero[i][j]>0) System.out.printf("  %2d  |", tablero[i][j]);
                else System.out.printf("      |", 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) return true;
            int[][] posibles = buscarPosibles();
            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[][] resp = new int[numFilas*numColumnas][2];
        int[] sumaFilas = new int[numColumnas];
        int[] sumaColumnas = new int[numFilas];
        int     pos  = 0;
        for(int i=0; i<numFilas; i++) {
            for(int j=0; j<numColumnas; j++) {
                if(tablero[i][j]>0) {
                    sumaFilas[i]++;
                    sumaColumnas[j]++;
                }
            }
        }
        for(int i=0; i<numFilas; i++) {
            if(sumaFilas[i]>0) continue;
            for(int j=0; j<numColumnas; j++) {
                if(sumaColumnas[j]>0) continue;
                if(i>0 && j>0             && tablero[i-1][j-1] > 0) continue;
                if(i>0 && j<numColumnas-1 && tablero[i-1][j+1] > 0) continue;
                if(i<numFilas-1 && j>0    && tablero[i+1][j-1] > 0) continue;
                if(i<numFilas-1 && j<numColumnas-1 && tablero[i+1][j+1] > 0) continue;
                resp[pos][0]=i;
                resp[pos][1]=j;
                pos++;
            }
        }
        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) {
        java.util.Random rnd  = new java.util.Random();
        int numFilas      = 8;
        int filaInicial   = rnd.nextInt(numFilas);
        int colInicial    = rnd.nextInt(numFilas);
        ProblemaReinas pr = new ProblemaReinas(8);
        pr.resolverProblema(filaInicial, colInicial,1);
        pr.mostrarTablero();
        System.out.printf("Cantidad de veces que entra al ciclo: %,d %n",  pr.contador);
    }
}
Enhanced by Zemanta

4 comentarios:

  1. Anónimo11:45 p.m.

    no funciona este algoritmo esta mal implementado

    ResponderBorrar
  2. Gracias.... por el codigo lo probé y en ALGUNAS OCACIONES SE MATAN...0K.....

    ResponderBorrar
  3. Anónimo6:20 a.m.

    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 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.

    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...