Torre de Hanoi - Algoritmo que resolve automáticamente
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.
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.
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.
public class ProgramaTorreHanoi {
public static void main(String[] args) {
TorreHanoi torre = new Movimentos(10);
torre.IniciarJogo();
}
}