Problema de las Reinas - Version 2

Image 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);
    }
}

Problema de las Reinas

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);
    }
}

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);
    }
}

Problema de la mochila - Algoritmos Voraces

Si bien la solución por backtracking permite obtener la mejor solución al problema de la mochila, existe el problema de que cuando la cantidad de elementos a evaluar es relativamente grande, los tiempos de respuesta se vuelven prohibitivos. Por otro lado, la solución de agregar primero los elementos más costosos, o lo más livianos, no garantiza una solución óptima, o por lo menos parecida a la óptima.

Estas dos aproximaciones representan el concepto de algoritmos voraces, donde se selecciona una estrategia que permite decidir si un elemento se agrega o no a la solución. En los casos mencionados se utilizaba la estrategia del mayor costo o la del menor peso. Una mejor solución se presenta cuando se utiliza el costo por unidad de peso para ordenar los elementos, de esta manera, un elemento muy caro no se agrega si pesa demasiado en comparación con otro de menor valor, pero de mucho menor peso. La función resolverProblema queda entonces de la siguiente manera:

    public void resolverProblema() {
        // Comparador para ordenar los elementos del almacen por valor
        Comparator cmp = new Comparator<Elemento>() {
            public int compare(Elemento x, Elemento y) {
                return (int) (x.valor/x.peso - y.valor/y.peso);
            }
        };
        Collections.sort(almacen,cmp);  // ordena usando el comparador anterior
        Collections.reverse(almacen);   // reversa el orden de los elementos

        double pesoMochila=0;
        int    posicion=0;
        while(pesoMochila<pesoMaximo && posicion < almacen.size()) {
            Elemento tmp = almacen.get(posicion);
            if(pesoMochila + tmp.peso <= pesoMaximo) {
                mochila.add(tmp);
                pesoMochila+=tmp.peso;
            }
            posicion++;
        }
    }

En cuanto al desempeño de este método, su complejidad es la equivalente al proceso de ordenación de la lista de elementos por su valor por unidad de peso, que es O(N log N), ya que el proceso de llenado de la mochila es lineal.

En el caso de ejemplo, este método da una respuesta con un peso total de 18 Kg y un costo de $945, mientras que la respuesta obtenida por backtracking es de 20 Kg con un costo de $955, lo que muestras que se obtiene un valor muy cercano al óptimo en una fracción del tiempo.

Problema de la mochila - Backtracking

Resolver el problema de la mochila seleccionando los elementos más caros en primer lugar, o los más livianos, no necesariamente garantiza llegar a una solución ideal, pues es posible que otras combinaciones de elementos produzcan mejores resultados.

Para obtener la solución ideal se deben revisar todas las alternativas; y en este caso, se puede utilizar una estrategia de retroceso, o backtracking. En esta implementación, iniciando en el primer elemento del almacén, se evalúan dos posibilidades, agregar o no agregar el elemento a la mochila, y llamando recursivamente el método hasta que la mochila se llena; una vez llena, se compara con el máximo calculado anteriormente y se guarda la lista de elementos que genere el mayor valor en la mochila. Esta solución requiere una mochila temporal (tmpMochila) que se crea en forma similar a la mochila definitiva, y dos métodos que calculen el valor y el peso acumulado de dicha mochila temporal. La implementación queda entonces de la siguiente manera:

// Solución por backtracking
    public void resolverProblemaBT(int posicion) {
        double  pesoMochila=getPeso(tmpMochila);    // peso de la solucion temporal
        double valorMochila=getValor(tmpMochila);   // valor de la solucion temporal

        if( posicion>=almacen.size() ) {            // si ya se tuvieron en cuenta todos los elementos
            if(valorMochila>valorMaximo) {          // si el valor es mayor que el máximo anterior
                valorMaximo=valorMochila;           // se actualiza el valor mayor
                mochila.clear();
                mochila.addAll(tmpMochila);
            }
            return;
        }
        Elemento e = almacen.get(posicion);
        // Si el elemento se puede agregar, se envía a la mochila temporal
        if(pesoMochila + e.peso <= pesoMaximo) {
                tmpMochila.add(e);                  // Se agrega a la mochila temporal
                resolverProblemaBT(posicion+1);     // se revisa para el siguiente elemento
                tmpMochila.remove(e);               // Se retira el elemento
        }
        // Si no se pudo agregar, o ya se agregó y se retiró, se revisa para el siguiente
        resolverProblemaBT(posicion+1);
    }

    double getPeso(List<Elemento> tmp) {
        double respuesta=0;
        for(Elemento e: tmp) respuesta+=e.peso;
        return respuesta;
    }

    double getValor(List<Elemento> tmp) {
        double respuesta=0;
        for(Elemento e: tmp) respuesta+=e.valor;
        return respuesta;
    }

El método de invocación quedaría de la siguiente manera (no olvidar crear el vector tmpMochila como un Vector de objetos de tipo Elemento):

    public static void main(String[] args) {
        ProblemaMochila pm = new ProblemaMochila(20);
        pm.resolverProblemaBT(0);       // Inicia en el primer elemento disponible
        pm.mostrarMochila();
    }

Este método devuelve la solución óptima, puesto que evalúa todas las posibilidades, sin embargo, cuando el número de elementos disponibles es relativamente grande, la cantidad de operaciones a realizar hace prácticamente imposible utilizar el algoritmo, ya que su complejidad es del orden de O(N!), donde N es la cantidad de elementos del almacén.