A torre de Hanoi, também conhecida por torre do bramanismo ou qu1ebra-cabeças do fim do mundo, foi publicada em 1883 pelo matemático francês 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ça.

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 ^ 64) –1 2 elevado a 64 menos 1 = 18.446.744.073.709.551.615 o que daria mais do que 5 bilhões de séculos, 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 dada 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.

Definição do Problema

O problema da Torre de Hanói 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 conforme a figura a seguir:

O problema consiste em transferir-se à 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

Algoritmo

A solução para o problema da Torre de Hanoi com recursividade é compacta e baseia-se no seguinte:

a) A única operação possível de ser executada é "move disco de um pino para outro";

b) Uma torre com (N) discos, em um pino, pode ser reduzido ao disco de baixo e a torre de cima com (N-1) discos;

c) A solução consiste em transferir a torre com (N-1) discos do pino origem para o pino auxiliar, mover o disco de baixo do pino origem para o pino destino e transferir a torre com (N-1) discos de o pino auxiliar para o pino destino. Como a transferência da torre de cima não é uma operação possível de ser executada, ela deverá ser reduzida sucessivamente até transformar-se em um movimento de disco.