Sign in
Log inSign up

Torre de Hanoi - Algoritmo que resolve automáticamente

Max Roberto Machado Ribeiro's photo
Max Roberto Machado Ribeiro
·Mar 28, 2018

Este é um algoritmo em Java criado por mim que resolve a Torre de Hanoi independente do número de discos usado.

Primeiro eu criei a classe que monta a Torre de Hanoi.

TorreHanoi.java

abstract class TorreHanoi {
    protected int[][] Torre;
    protected int NumDiscos, MovMinimos, Impar, Par;

    TorreHanoi(int tamanho){
        this.NumDiscos = tamanho;

        if((tamanho % 2) != 0) {
            this.Impar = 2;
            this.Par = 1;
        }else {
            this.Impar = 1;
            this.Par = 2;
        }

        this.Torre = new int[tamanho][3];        
        //Preencher Primeira Torre
        int j = 0;
        for(int i = tamanho; i > 0; i--) {
            this.Torre[j][0] = i;
            j++;
        }    

        //Preencher Restante com zeros
        for(int i =0; i < tamanho; i++) {
            for(int k = 1; k <= 2; k++) {
                this.Torre[i][k] = 0;
            }
        }    

        this.MovMinimos = (int)Math.pow(2, tamanho) - 1;
    }

    public abstract void IniciarJogo();
}

A classe seguinte é a classe que será responsável por movimentar os discos e imprimir cada movimento.

Movimentos.java

public class Movimentos extends TorreHanoi {

    int PosicaoAtual01, PosicaoAtual02 = 0, PosicaoAtual03 = 0, LivreTorre1, LivreTorre2 = 0, LivreTorre3 = 0;
    int Contador = 1, ColunaDisco1 = 0, LinhaDisco1, ColunaDisco2 = 0, LinhaDisco2, NovaLinha, NovaColuna;


    Movimentos(int tamanho) {
        super(tamanho);
        this.PosicaoAtual01 = tamanho - 1;
        this.LinhaDisco1 = tamanho - 1;        
        this.LinhaDisco2 = tamanho - 2;
    }

    @Override
    public void IniciarJogo() {

        System.out.println("Movimento - 0");
        this.Imprime();
        System.out.println(" ");

        for(int i =0; i < this.MovMinimos; i++) {
            this.Movimentar();        

            System.out.println("Movimento - " + (i+1));
            this.Imprime();
            System.out.println(" ");
        }                
    }

    private void Movimentar() {
        if(this.Contador == 1 || this.Contador == 3) {                        
            if(this.Contador == 1) {
                this.Contador = 2;
            }else {
                this.Contador = 4;
            }

            this.MoveDiscos(this.ColunaDisco1, this.LinhaDisco1, this.Impar);    
            this.ColunaDisco1 = this.NovaColuna;
            this.LinhaDisco1 = this.NovaLinha;

        }else if(this.Contador == 2) {
            this.Contador = 3;
            this.MoveDiscos(this.ColunaDisco2, this.LinhaDisco2, this.Par);                

            this.ColunaDisco2 = this.NovaColuna;
            this.LinhaDisco2 = this.NovaLinha;

        }else if(this.Contador == 4) {
            this.Contador = 1;
            //Disco 1 na Torre 1
            this.OutrosDiscos();
        }
    }

    private void OutrosDiscos() {
        switch (this.ColunaDisco1) {
        case 0:
            this.CheckTorresLivres(1, this.PosicaoAtual02, 2, this.PosicaoAtual03);
            break;
        case 1:
            this.CheckTorresLivres(0, this.PosicaoAtual01, 2, this.PosicaoAtual03);
            break;
        case 2:
            this.CheckTorresLivres(0, this.PosicaoAtual01, 1, this.PosicaoAtual02);
            break;
        }            
    }

    private void CheckTorresLivres(int ColunaOrigem, int LinhaOrigem, int ColunaDestino, int LinhaDestino) {


        if(this.Torre[LinhaOrigem][ColunaOrigem] !=0 && this.Torre[LinhaDestino][ColunaDestino] != 0) {

            if(this.Torre[LinhaOrigem][ColunaOrigem] < this.Torre[LinhaDestino][ColunaDestino]) {

                if(this.Torre[LinhaOrigem][ColunaOrigem] % 2 == 0) {
                    this.MoveDiscos(ColunaOrigem, LinhaOrigem, Par);
                }else {
                    this.MoveDiscos(ColunaOrigem, LinhaOrigem, Impar);
                }
            }else if(this.Torre[LinhaOrigem][ColunaOrigem] > this.Torre[LinhaDestino][ColunaDestino]) {

                if(this.Torre[LinhaDestino][ColunaDestino] % 2 == 0) {
                    this.MoveDiscos(ColunaDestino, LinhaDestino, Par);
                }else {
                    this.MoveDiscos(ColunaDestino, LinhaDestino, Impar);
                }
            }
        }else {    
            if(this.Torre[LinhaOrigem][ColunaOrigem] == 0) {
                if(this.Torre[LinhaDestino][ColunaDestino] % 2 == 0) {
                    this.MoveDiscos(ColunaDestino, LinhaDestino, Par);
                }else {
                    this.MoveDiscos(ColunaDestino, LinhaDestino, Impar);
                }
            }else {
                if(this.Torre[LinhaOrigem][ColunaOrigem] % 2 == 0) {
                    this.MoveDiscos(ColunaOrigem, LinhaOrigem, Par);
                }else {
                    this.MoveDiscos(ColunaOrigem, LinhaOrigem, Impar);
                }
            }            
        }        
    }
    //Movimenta os Discos pelas Colunas
    private void MoveDiscos(int ColunaAtual,int LinhaAtual, int Movimentos) {
        if(Movimentos == 1) {
            switch (ColunaAtual) {
            case 0:
                this.NovaColuna = 1;
                break;
            case 1:
                this.NovaColuna = 2;
                break;
            case 2:
                this.NovaColuna = 0;
                break;
            }
        }else if(Movimentos == 2){
            switch (ColunaAtual) {
            case 0:
                this.NovaColuna = 2;
                break;
            case 1:
                this.NovaColuna = 0;
                break;
            case 2:
                this.NovaColuna = 1;
                break;
            }
        }    

        this.AtualizaLinhaNovaColuna();        
        this.Torre[this.NovaLinha][this.NovaColuna] = this.Torre[LinhaAtual][ColunaAtual];
        this.AtualizaLinhaColunaAntiga(ColunaAtual);
    }

    //Atualiza Linha
    private void AtualizaLinhaNovaColuna() {
        switch(this.NovaColuna) {
        case 0:
            this.NovaLinha = this.LivreTorre1;
            this.PosicaoAtual01 = this.LivreTorre1;
            this.LivreTorre1++;
            break;
        case 1:
            this.NovaLinha = this.LivreTorre2;
            this.PosicaoAtual02 = this.LivreTorre2;
            this.LivreTorre2++;
            break;
        case 2:
            this.NovaLinha = this.LivreTorre3;
            this.PosicaoAtual03 = this.LivreTorre3;
            this.LivreTorre3++;
            break;
        }
    }

    private void AtualizaLinhaColunaAntiga(int ColunaAntiga) {
        switch (ColunaAntiga) {
        case 0:
            this.Torre[this.PosicaoAtual01][ColunaAntiga] = 0;
            this.LivreTorre1 = this.PosicaoAtual01;
            this.PosicaoAtual01 = AtualizaPosicaoAtual(PosicaoAtual01);
            break;
        case 1:
            this.Torre[this.PosicaoAtual02][ColunaAntiga] = 0;
            this.LivreTorre2 = this.PosicaoAtual02;
            this.PosicaoAtual02 = AtualizaPosicaoAtual(PosicaoAtual02);
            break;
        case 2:
            this.Torre[this.PosicaoAtual03][ColunaAntiga] = 0;
            this.LivreTorre3 = this.PosicaoAtual03;
            this.PosicaoAtual03 = AtualizaPosicaoAtual(PosicaoAtual03);
            break;
        }
    }    

    private int AtualizaPosicaoAtual(int Linha) {
        if(Linha > 0) {
            Linha--;
        }else {
            Linha = 0;
        }
        return Linha;
    }

    private void Imprime() {
        System.out.println("A B C");
        for(int j = 0; j < this.NumDiscos; j++) {
            System.out.print(this.Torre[j][0] + " " + this.Torre[j][1] + " " + this.Torre[j][2] + "\n");                
        }
    }
}

E pra finalizar a classe que instância e defini o número de discos que serão utilizados.

ProgramaTorreHanoi.java

public class ProgramaTorreHanoi {

    public static void main(String[] args) {
        TorreHanoi torre = new Movimentos(10);
        torre.IniciarJogo();
    }
}