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?