Torre de Hanoi

A Torre de Hanói é um dos quebra-cabeças matemáticos mais populares, também conhecida por torre do bramanismo ou quebra-cabeças do fim do mundo, foi publicada em 1883 pelo matemático frances Edouard Lucas, com o pseudônimo Prof. N. Claus (de Siam), um anagrama de seu nome. A publicação dizia que o jogo vinha do Vietnã, sendo popular também na China e no Japão, e acompanhava a caixa do quebra-cabeças. 

A publicação também oferecia mais de um milhão de Francos para quem resolvesse o problema da Torre de Hanoi com 64 níveis, seguindo as regras do jogo, indicando que o número de movimentos seria 2 elevado a 64 menos 1 que é igual 18.446.744.073.709.551.615 o que daria cerca de 585 bilhões de anos, se cada movimento fosse feito em 1 segundo.

Edouard Lucas foi inspirado por uma lenda Hindu que falava de um templo em Bernares, cidade santa da Índia, onde existia uma torre sagrada do bramanismo, cuja função era melhorar a disciplina mental dos monges jovens. A lenda dizia que, no início dos tempos, foi dado aos monges de um templo uma pilha de 64 discos de ouro, dispostos em uma haste, de forma que cada disco de cima fosse menor que o de baixo. A atribuição que os monges receberam foi transferir a torre, formada pelos discos, de uma haste para outra, usando a terceira como auxiliar com as restrições de movimentar um disco por vez e de nunca colocar um disco maior sobre um menor. Os monges deveriam trabalhar com eficiência noite e dia e, quando terminassem o trabalho, o templo seria transformado em pó e o mundo acabaria.

O Problema

O problema da Torre de Hanoi envolve um ambiente formado por uma base, contendo 3 pinos, onde, em um deles, há uma pilha de discos furados no meio e de diâmetros diferentes ordenados de forma que o disco maior esteja em baixo e o menor esteja em cima, formando assim uma torre.

O problema consiste na tranferência da torre de um pino a outro, obedecendo as seguintes restrições:

a) Só é possível movimentar-se um disco por vez para qualquer pino;

b) Um disco maior nunca poderá ser colocado sobre um menor;

c) A solução deverá ser encontrada com o menor número de passos possível.

O número de discos pode variar sendo que o mais simples contém apenas três.

Veja a solução para o caso com 3 discos:

A Torre de Hanói tem sido tradicionalmente considerada como um procedimento para avaliação da capacidade de memória de trabalho, e principalmente de planejamento e solução de problemas.