Torre de Hanói

Como jogar a Torre de Hanói

O quebra-cabeça tem três pinos e uma pilha de discos de tamanhos diferentes, empilhados no primeiro pino do maior embaixo ao menor em cima. Seu objetivo é levar a pilha inteira para o terceiro pino. Só existem duas regras:

1. Você pode mover um disco por vez, sempre o de cima de uma pilha.
2. Um disco nunca pode ficar sobre um menor.

Toque num pino para levantar o disco de cima e depois toque no pino onde quer colocá-lo. Toque de novo no mesmo pino para devolvê-lo. O contador mostra quantos movimentos você fez e o mínimo possível para a sua torre. Se terminar exatamente nesse número, você encontrou a solução perfeita.

A solução mais curta: 2ⁿ − 1 movimentos

O quebra-cabeça tem uma bela solução recursiva. Para levar uma torre de n discos do pino 1 ao pino 3:

1. Tire do caminho os n − 1 discos de cima, levando-os para o pino 2.
2. Leve o disco maior para o pino 3.
3. Leve os n − 1 discos do pino 2 para o pino 3, em cima do maior.

Os passos 1 e 3 são o mesmo quebra-cabeça com um disco a menos, então o número de movimentos dobra, mais um, a cada disco que você acrescenta: 1, 3, 7, 15, 31, 63, 127, 255. Em geral, uma torre de n discos precisa de 2ⁿ − 1 movimentos, e nenhuma solução pode ser mais curta. Toque em Ver solução para assistir.

Uma regra que dá para seguir sem pensar

Também existe um método passo a passo bem simples. Alterne entre dois tipos de movimento:

• Movimentos ímpares: mova o disco menor um pino adiante, sempre na mesma direção. Com um número par de discos ele viaja 1 → 2 → 3 → 1; com um número ímpar, 1 → 3 → 2 → 1.
• Movimentos pares: faça o único movimento permitido que não envolve o disco menor. Sempre existe exatamente um.

Seguindo essas duas regras, você termina sempre no número mínimo de movimentos. Há até uma ligação com a contagem em binário: no movimento número m, o disco que se move depende de quantas vezes o 2 divide m. O disco menor se move em todo movimento ímpar; o segundo, nos movimentos 2, 6, 10 e assim por diante.

A história e a lenda

A Torre de Hanói foi inventada pelo matemático francês Édouard Lucas e vendida como brinquedo em 1883 com o nome brincalhão de “N. Claus de Siam”, um anagrama de “Lucas d'Amiens”. Vinha com uma lenda: num grande templo, sacerdotes movem uma torre de 64 discos de ouro seguindo exatamente essas regras, e quando terminarem, o mundo vai acabar.

A lenda nos deixa tranquilos por um bom tempo. Uma torre de 64 discos precisa de 2⁶⁴ − 1 movimentos, pouco mais de 18 quintilhões. A um movimento por segundo, sem um único erro, isso levaria cerca de 585 bilhões de anos, muitas vezes a idade atual do universo. Hoje o quebra-cabeça é um exemplo querido para ensinar recursão em matemática e programação, e é usado na psicologia para estudar o planejamento.

Perguntas frequentes

Qual é o número mínimo de movimentos?

Para uma torre de n discos, o mínimo é 2ⁿ − 1 movimentos: 7 com 3 discos, 15 com 4, 31 com 5, 63 com 6, 127 com 7 e 255 com 8.

Preciso levar a torre para o terceiro pino?

Sim, aqui o objetivo é o pino 3, o da direita. O pino do meio é o seu auxiliar. A solução mais curta tem o mesmo tamanho em qualquer direção.

Desfazer conta como movimento?

Não. Desfazer volta o seu último movimento e tira um do contador, então você pode explorar sem penalidade.

O que significa o recorde?

Seu recorde é a maior torre que você já resolveu. Comece com 3 ou 4 discos e vá subindo. Resolver 8 discos, em 255 movimentos ou mais, é um verdadeiro teste de paciência e planejamento.

É grátis?

Sim, totalmente grátis e sem cadastro. Seu progresso fica salvo no seu navegador, no seu próprio aparelho.