TORRES DE HANOI
Agradeço comentários, sugestões ou correccões. O meu endereço de correio electrónico é < delfim@mat.ua.pt > . Desde já obrigado.
Resolução do problema TORRES DE HANOI.
Algures perto de Hanoi, existe um mosteiro cujos monges devotam as suas vidas a uma
tarefa muito importante. No pátio desse mosteiro existem três postes enormes. Nestes
postes existe um conjunto de sessenta e quatro discos, cada um deles com um orifício no
centro e com um raio diferente. Quando o mosteiro foi construído, todos os discos estavam
num dos postes: cada disco descansando sobre o disco de raio imediatamente a seguir. A
tarefa dos monges consiste em mover todos os discos para um dos outros postes. Apenas um
disco pode ser movido de cada vez e todos os restantes discos devem estar num dos postes.
Para além disso, em nenhum instante durante o processo, pode um disco estar colocado em
cima de um disco menor. O terceiro poste pode, claro, ser usado como local temporário de
descanso para os discos. Qual é a maneira mais rápida de os monges cumprirem a sua
missão?
Mesmo a melhor solução para este problema, precisará de muito tempo para que os monges a consigam terminar. Ainda bem que assim é, pois a lenda conta que o mundo acabará quando os monges tiverem terminado a sua tarefa ...
O problema é muito fácil de resolver se pensarmos de modo generalista e recursivo.
Começamos por generalizar o problema da seguinte maneira.
Em vez de considerarmos um número fixo de discos, 64, consideramos o problema mais
geral em que o número de discos é arbitrário: digamos N. A generalização de problemas
é algo de muito importante e constitui um dos paradoxos da programação: muitas vezes a
maneira mais fácil de resolver um problema consiste em resolver uma sua generalização!
Vamos agora resolver o problema generalizado de modo recursivo. O caso trivial acontece para N = 0: não há nenhum disco, não é preciso fazer nada. Para N > 0, temos no início os discos num dos postes, digamos no posteA, e no final pretendemos que eles estejam todos em outro, digamos, no posteB. A utilidade da recursividade está em percebermos que se soubermos resolver o problema para N-1 discos, facilmente o resolvemos também para N discos:
E pronto. Já temos todos os ingredientes para implementar uma solução em Prolog.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Torres de Hanoi % Delfim F. Marado Torres, 24/Maio/1999 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Predicado Principal: torresHanoi(N) % % N representa o numero de discos % Os tres postes sao denotados por posteA, posteB e posteC % No inicio todos os discos estao no posteA % No fim pretendemos ter todos os discos no posteB %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% torresHanoi(N) :- move(N,posteA,posteB,posteC). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % move(NumDiscosAMover,Origem,Destino,Auxiliar) %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% move(0,_,_,_). move(N,A,B,C) :- N1 is N-1, move(N1,A,C,B), informa(A,B), move(N1,C,B,A). informa(A,B) :- write('Move disco do '), write(A), write(' para o '), write(B), nl.
Resolver o problema das Torres de Hanoi com um número de discos muito pequeno, por exemplo 3, pode ser facilmente feito ``à mão'' (com papel e lápis e esboçando a configuração dos postes no pátio dos monges). A solução é:
?- torresHanoi(3). Move disco do posteA para o posteB Move disco do posteA para o posteC Move disco do posteB para o posteC Move disco do posteA para o posteB Move disco do posteC para o posteA Move disco do posteC para o posteB Move disco do posteA para o posteB
Tentar fazer, no entanto, o mesmo para 10 discos... A folha termina num emaranhado de riscos... com grande probabilidade de nos 'perdermos'... Se executarmos o comando
?- tell('hanoi10.txt'), torresHanoi(10), told, tell(user). Yes
e dermos uma vista de olhos ao ficheiro hanoi10.txt, concluímos que
precisamos de 1023 operações Move para alcançarmos o desejado! O programa, no
meu computador, apenas é capaz de ir até N = 13: para 13 discos a solucão envolve 8191
operações Move!
Quantas operações serão necessárias antes 'do final dos tempos'? De um modo mais geral: é capaz de encontrar uma fórmula, em função do número N de discos, que nos dê o número de operações necessárias para o fim do jogo?