Problema das N Rainhas em JAVA

Hoje irei mostrar um script que criei na aula de Inteligência Artificial na faculdade, ele se baseia em um problema muito comun quando trabalhamos com recursividade,  o problema das N Rainhas, que é nada mais nada menos, que um tabuleiro de xadres com N rainhas espalhadas de forma que nem uma rainha ataque uma a outra. Na Inteligencia Artificial ele também é bastante esplorado tentando sempre melhorar o seu tempo de desempenho e uso de memória para um número maior de Rainhas. Para a criação do algoritimo foi seguido o artigo : A polynomial Time Algorithm for the N-Queen Problem. Basta digitar no google que você encontra fácilmente este artigo.

Quando trabalhamos com recursividade, não temos um bom desempenho com grande números de rainhas, pois ele irá utilzar muita memória para alcançar o objetivo. Com este algoritmo consegui executar 10.000 rainhas em 98680 milisegundos, ou seja 98.6 segundos.

Qualquer dúvida sobre o código, podem postar nos comentários que se eu puder ajudar irei de boa.

public class Main {

    private static int diagonal_posistiva[];
    private static int diagonal_negativa[];
    private static int rainhas[];
    private static int numeroRainhas;
    private static int numeroDiagonais;

    private static void inicializaTabuleiro() {
        Random aleatorio = new Random();

        rainhas = new int[numeroRainhas];
        diagonal_posistiva = new int[numeroDiagonais];
        diagonal_negativa = new int[numeroDiagonais];

        for (int i = 0; i < numeroRainhas; i++) {
            rainhas[i] = i;
        }

        for (int count = 0; count < numeroDiagonais; count++) {
            double count1 = count;
            if (count % 2 == 0) {
                diagonal_posistiva[count] = 1;
            } else {
                diagonal_posistiva[count] = 0;
            }
            int count2 = count;
            if (count1 == ((numeroDiagonais) / 2)) {
                count1 = Math.ceil(count1);
                count2 = (int) count1;
                diagonal_negativa[count2] = numeroRainhas;
            } else {
                diagonal_negativa[count2] = 0;
            }
        }

        for (int i = 0; i < numeroRainhas; ++i) {
            Swap(aleatorio.nextInt(numeroRainhas), aleatorio.nextInt(numeroRainhas));
        }

    }

    private static void Swap(int Coluna01, int Coluna02) {
        int linha01, linha02;
        linha01 = rainhas[Coluna01];
        linha02 = rainhas[Coluna02];

        int Diagonais_Neg_Aux;
        int Diagonais_Pos_Aux;

        //********************* Primeira Rainha ******************************
        Diagonais_Pos_Aux = linha01 + Coluna01;
        Diagonais_Neg_Aux = (Coluna01 - linha01) + (numeroRainhas - 1);
        diagonal_posistiva[Diagonais_Pos_Aux] = diagonal_posistiva[Diagonais_Pos_Aux] - 1;
        diagonal_negativa[Diagonais_Neg_Aux] = diagonal_negativa[Diagonais_Neg_Aux] - 1;

        Diagonais_Pos_Aux = linha02 + Coluna01;
        Diagonais_Neg_Aux = ((Coluna01 - linha02) + (numeroRainhas - 1));
        diagonal_posistiva[Diagonais_Pos_Aux] = diagonal_posistiva[Diagonais_Pos_Aux] + 1;
        diagonal_negativa[Diagonais_Neg_Aux] = diagonal_negativa[Diagonais_Neg_Aux] + 1;

        //******************** Segunda Rainha ********************************

        Diagonais_Pos_Aux = linha02 + Coluna02;
        Diagonais_Neg_Aux = (Coluna02 - linha02) + (numeroRainhas - 1);
        diagonal_posistiva[Diagonais_Pos_Aux] = diagonal_posistiva[Diagonais_Pos_Aux] - 1;
        diagonal_negativa[Diagonais_Neg_Aux] = diagonal_negativa[Diagonais_Neg_Aux] - 1;

        Diagonais_Pos_Aux = linha01 + Coluna02;
        Diagonais_Neg_Aux = (Coluna02 - linha01) + (numeroRainhas - 1);
        diagonal_posistiva[Diagonais_Pos_Aux] = diagonal_posistiva[Diagonais_Pos_Aux] + 1;
        diagonal_negativa[Diagonais_Neg_Aux] = diagonal_negativa[Diagonais_Neg_Aux] + 1;

        //******************* Substitui rainhas ********************************

        rainhas[Coluna01] = linha02;
        rainhas[Coluna02] = linha01;
    }

    private static Boolean Verifica_Ataques_Rainhas(int Coluna) {
        Boolean Ataques = false;
        if (diagonal_posistiva[procura_diagonal_Pos(Coluna)] > 1) {
            return true;
        }
        if (diagonal_negativa[procura_diagonal_Neg(Coluna)] > 1) {
            return true;
        }
        return Ataques;
    }

    private static int procura_diagonal_Pos(int Coluna) {
        int diagonal = -1;
        diagonal = Coluna + rainhas[Coluna];
        return diagonal;
        //return Coluna + Rainhas[Coluna];
    }

    private static int procura_diagonal_Neg(int Coluna) {
        int diagonal = -1;
        diagonal = (Coluna - rainhas[Coluna]) + (numeroRainhas - 1);
        return diagonal;
        //return (Coluna - Rainhas[Coluna]) + (Nro_rainhas - 1);
    }

    private static int Verifica_ataques() {
        int ataques = 0;

        for (int Diagonal_count = 0; Diagonal_count < numeroDiagonais; Diagonal_count++) {
            if (diagonal_posistiva[Diagonal_count] > 1) //ataques++;
            {
                ataques = ataques + diagonal_posistiva[Diagonal_count] - 1;
            }
            if (diagonal_negativa[Diagonal_count] > 1) //ataques++;
            {
                ataques = ataques + diagonal_negativa[Diagonal_count] - 1;
            }
        }

        return ataques;
    }

    private static Boolean test() {
        for (int Diagonal_count = 0; Diagonal_count < numeroDiagonais; Diagonal_count++) {
            if (diagonal_posistiva[Diagonal_count] > 1) {
                ;
                return false;
            }

            if (diagonal_negativa[Diagonal_count] > 1) {

                return false;
            }
        }
        return true;
    }

    private static void Controlador() {
        int colisoes01 = 0, colisoes02 = 0;
        int[] rainhas_aux = new int[2];
        int swap_perform = 1;
        while (swap_perform != 0) {
            swap_perform = 0;
            for (int coluna01 = 0; (coluna01 < numeroRainhas - 1); coluna01++) {
                int coluna02;
                for (coluna02 = coluna01 + 1; (coluna02 < numeroRainhas); coluna02++) {
                    if ((Verifica_Ataques_Rainhas(coluna01) == true) || (Verifica_Ataques_Rainhas(coluna02) == true)) {
                        colisoes01 = Verifica_ataques();
                        Swap(coluna01, coluna02);
                        colisoes02 = Verifica_ataques();
                        swap_perform = swap_perform + 1;
                        if (colisoes01 == 0) {
                            swap_perform = 0;
                        }
                        if (colisoes01 < colisoes02) {
                            Swap(coluna01, coluna02);
                            swap_perform = swap_perform - 1;
                        }
                    }
                }
            }

        }

        if (test()) {
            return;
        } else {
        }

    }

    private static void imprime() {
        for (int i = 0; i < numeroRainhas; i++) {
            for (int i1 = 0; i1 < numeroRainhas; i1++) {
                if (rainhas[i1] == i) {
                    System.out.print(" " + i + " ");
                } else {
                    System.out.print(" X ");
                }
            }
            System.out.println(" ");
        }
        System.out.println(" ");
        System.out.println(" ");
        System.out.println(" ");
        System.out.println(" ");
    }

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        long tempo, tempoFinal = 0;
        numeroRainhas = 100;
        numeroDiagonais = (numeroRainhas * 2) - 1;
        for (int i = 0; i <= 50; ++i) {

            inicializaTabuleiro();
            tempo = System.currentTimeMillis();
            Controlador();
            tempo = System.currentTimeMillis() - tempo;
            tempoFinal += tempo;
        }
        System.out.println("A Média para " + numeroRainhas + " rainhas  é "
                + tempoFinal / 50 + " milisegundos");

        numeroRainhas = 200;
        numeroDiagonais = (numeroRainhas * 2) - 1;
        for (int i = 0; i <= 50; ++i) {

            inicializaTabuleiro();
            tempo = System.currentTimeMillis();
            Controlador();
            tempo = System.currentTimeMillis() - tempo;
            tempoFinal += tempo;
        }
        System.out.println("A Média para " + numeroRainhas + " rainhas  é "
                + tempoFinal / 50 + " milisegundos");

        numeroRainhas = 500;
        numeroDiagonais = (numeroRainhas * 2) - 1;
        for (int i = 0; i <= 50; ++i) {

            inicializaTabuleiro();
            tempo = System.currentTimeMillis();
            Controlador();
            tempo = System.currentTimeMillis() - tempo;
            tempoFinal += tempo;
        }
        System.out.println("A Média para " + numeroRainhas + " rainhas  é "
                + tempoFinal / 50 + " milisegundos");

        numeroRainhas = 1000;
        numeroDiagonais = (numeroRainhas * 2) - 1;
        for (int i = 0; i <= 50; ++i) {

            inicializaTabuleiro();
            tempo = System.currentTimeMillis();
            Controlador();
            tempo = System.currentTimeMillis() - tempo;
            tempoFinal += tempo;
        }
        System.out.println("A Média para " + numeroRainhas + " rainhas  é "
                + tempoFinal / 50 + " milisegundos");
        numeroRainhas = 10000;
        numeroDiagonais = (numeroRainhas * 2) - 1;
        inicializaTabuleiro();
        tempo = System.currentTimeMillis();
        Controlador();
        tempo = System.currentTimeMillis() - tempo;
        tempoFinal += tempo;
    }
}