4.10. Torre de Hanoi

O problema da Torre de Hanoi foi inventado pelo matemático francês Edouard Lucas em 1883. Ele foi inspirado por uma lenda que fala de um templo Hindu onde o problema foi apresentado aos jovens sacerdotes. No inicio dos tempos, os sacerdotes receberam três pinos e uma pilha de 64 discos de ouro, sendo cada disco um pouco menor do que aquele abaixo dele. A tarefa era transferir todos os 64 discos colocados em um dos três pinos para outro, com duas restrições importantes. Eles só podiam mover um disco de cada vez, e eles nunca poderiam colocar um disco maior em cima de um disco menor. Os sacerdotes trabalhavam muito eficientemente, dia e noite, movendo um disco todo segundo. Quando eles terminassem seu trabalho, diz a lenda, que o templo se desmoronaria em pó e o mundo desapareceria.

Embora a lenda seja interessante, você não precisa se preocupar com o mundo terminando em breve. O número de movimentos necessários para mover corretamente uma torre de 64 discos é \(2^{64}-1 = 18,446,744,073,709,551,615\). Movimentando um disco por segundo, a tarefa levaria \(584.942.417.355\) anos para terminar! Claramente esse problema é mais complexo do que aparenta.

A Figura 1 mostra um exemplo de configuração de discos no meio de um movimento do pino origem (fromPole) para o pino destino (toPole), usando o segundo pino como intermediário (withPole). Observe que, como as regras especificam, os discos em cada pino são empilhados para que discos menores sempre fiquem em cima de discos maiores. Se você não tentou resolver esse quebra-cabeça antes, procure resolvê-lo agora. Você não precisa de discos e pinos de verdade - basta usar uma pilha de livros ou pedaços de papel.

image

Figura 1: Um Exemplo de Configuração de Discos da Torre de Hanoi

Como podemos resolver este problema recursivamente? Como você resolveria esse problema de qualquer outra forma? Qual é o nosso caso base? Vamos pensar sobre este problema de baixo para cima. Suponha que você tenha uma torre de cinco discos, originalmente no pino um. Se você souber como mover uma torre de quatro discos para o pino dois, então você poderia mover facilmente o disco inferior para o pino três e, em seguida, mover a torre de quatro discos do pino dois para o três. Mas e se você não souber como mover uma torre de altura quatro? Suponha que você saiba como mover uma torre de três discos para o pino três; então seria fácil mover o quarto disco para o pino dois e mover os três discos do pino três em cima dele. Mas e se você não souber como mover uma torre de três? Que tal mover uma torre de dois discos para o pino dois e depois mover o terceiro disco para o pino três e, em seguida, mover a torre de altura dois em cima dele? Mas e se você ainda não souber como fazer isso? Com certeza você concordaria que mover um único disco para o pino três é bastante fácil, trivial você pode até dizer. Isso soa como um caso base se revelando.

Segue um rascunho em alto nível de como mover a torre de um pino origem para um pino destino, usando um pino intermediário:

  1. Mova a torre de \(altura - 1\) para o pino intermediário, usando o pino destino como intermediário.

  2. Mova o disco restante para o pino destino.

  3. Mova a torre de \(altura - 1\) do pino intermediário para o pino destino usando o pino origem como intermediário.

Contanto que sempre obedeçamos a regra de que os discos maiores permanecem na parte inferior da pilha, podemos usar as três etapas acima recursivamente, tratando discos maiores como se eles nem estivessem lá. A única coisa que falta no esquema acima é a identificação de um caso base. O problema mais simples da Torre de Hanoi é uma torre de um disco. Neste caso, precisamos mover apenas um único disco para o seu destino final. A torre de um disco será o nosso caso base. Além disso, as etapas descritas acima nos direciona para o caso base, reduzindo a altura da torre nos passos 1 e 3. A Listagem 1 mostra o código Python para resolver o problema Torre de Hanoi.

Listagem 1

1
2
3
4
5
def moveTower(height,fromPole, toPole, withPole):
    if height >= 1:
        moveTower(height-1,fromPole,withPole,toPole)
        moveDisk(fromPole,toPole)
        moveTower(height-1,withPole,toPole,fromPole)

Observe que o código na Listagem 1 é quase idêntico ao rascunho mas em inglês. A chave para a simplicidade do algoritmo é que fazemos duas chamadas recursivas diferentes, uma na linha 3 e uma segunda na linha 5. Na linha 3 nos movemos todos os discos do pino origem para o pino intermediário, a menos do disco mais baixo. A linha seguinte simplesmente move esse último disco para a sua posição final no pino destino. Então, na linha 5, movemos a torre no pino intermediário para o topo do maior disco. O caso base é detectado quando a altura da torre é 0; neste caso não há nada para fazer, então a função moveTower (mova torre) simplesmente retorna. O importante a lembrar sobre usar o caso base desta forma é que o fim de moveTower é o que permite que a função moveDisk (mova disco) seja chamada.

A função moveDisk, mostrada na Listagem 2, é muito simples. Tudo o que faz é imprimir que está movendo um disco de um pino para outro. Se você digitar e executar o programa moveTower você pode verificar que ela fornece uma solução muito eficiente para o quebra-cabeça.

Listagem 2

def moveDisk(fp,tp):
    print("moving disk from",fp,"to",tp)

O programa no ActiveCode 1 descreve a solução completa para três discos.

Agora que você viu o código para moveTower e moveDisk, você pode estar se perguntando por que não temos uma estrutura de dados que explicitamente mantém o controle de quais discos estão em quais pinos. Aqui vai uma dica: se você fosse explicitamente controlar os discos, você provavelmente usaria três objetos Pilha, um para cada pino. A resposta é que o Python fornece as pilhas que precisamos implicitamente através da pilha de chamadas.

Next Section - 4.11. Exploring a Maze