Guião para a Décima Segunda Aula Prática de IPL

Delfim F. Marado Torres

25 de Maio de 1999

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.

Objectivos da aula

Resolução do problema TORRES DE HANOI.

Enunciado do Problema

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 ...

Abordagem Recursiva

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.

Uma solução

         %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
         % 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.

Comentário Final

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?