El problema del recorrido del caballo de ajedrez - heuristicas

La solución al problema del recorrido del caballo de ajedrez encontrada con el método de backtracking se tarda un tiempo considerable porque evalúa demasiadas alternativas que no forman parte de la solución. La prueba en un computador con procesador Intel core i5 con Windows 7 tardó cerca de 40 minutos con 67,890,999,999,999 de ensayos.

Una solución utilizando heurísticas para este problema se enfoca en la manera en cómo se evalúan las celdas una vez se ha marcado una de ellas y propone que la asignación del orden en que se evalúan las casillas dependa de la cantidad de casillas a la que cada una de ellas tenga alcance. Es decir, por ejemplo, que si una vez marcada una casilla, ésta tiene 5 posibles celdas a las que el caballo puede saltar, se debe ir primero a aquella casilla que tenga menos saltos posibles.

Para implementar esta solución, sólo debe agregarse a la solución propuesta anteriormente un método que ordene el arreglo de posibles casillas y llamar a dicha función una vez se calcule dicho arreglo así:

    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);
            ordenarPosibles(posibles);              // llamado a la nueva función
            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;
    }

    // nuevo método: ordena el arreglo de posibles casillas a saltar
    void ordenarPosibles(int[][] posibles) {
        for(int i=0; i<posibles.length; i++) {
            for(int j=i+1; j<posibles.length; j++) {
                int cuantosPosiblesI = buscarPosibles(posibles[i][0], posibles[i][1]).length;
                int cuantosPosiblesJ = buscarPosibles(posibles[j][0], posibles[j][1]).length;
                if(cuantosPosiblesJ<cuantosPosiblesI) {
                    int tmp0 = posibles[i][0];
                    posibles[i][0] = posibles[j][0];
                    posibles[j][0] = tmp0;
                    int tmp1 = posibles[i][1];
                    posibles[i][1] = posibles[j][1];
                    posibles[j][1] = tmp1;
                }
            }
        }
    }

Con este cambio el proceso tarda algo menos de un segundo y sólo tiene que entrar 64 veces al proceso de marcado de casillas, es decir, no hace ningún retroceso.