Solução da Torre de Hanói a partir de qualquer posição
Escolha o número de discos, marque onde cada um está e veja a solução ótima: a sequência com o menor número possível de movimentos até juntar tudo no pino de destino. É o que em inglês se procura como tower of hanoi solver, com um diferencial: além da posição inicial, ele resolve qualquer posição no meio do jogo, de 3 a 20 discos.
Posição de partida
Toque no pino de cada disco. Em cada pino, os discos ficam sempre em ordem de tamanho.
Mínimo: 31 movimentos
Com a pilha completa em outro pino, o mínimo é 25 − 1 = 31.
Movimento 1 de 31: Disco 1: A → C
Como usar
- Escolha o número de discos e o pino de destino.
- Em Posição de partida, toque no pino em que cada disco está. Toda escolha é uma posição válida, porque em cada pino os discos ficam em ordem de tamanho.
- O mínimo de movimentos e a lista aparecem na hora.
- Acompanhe com Anterior e Próximo, ou use Reproduzir na velocidade que preferir. A barra salta para qualquer movimento, e a lista aceita toques.
Para jogar por conta própria, abra a Torre de Hanói.
Como o método funciona
O raciocínio é recursivo e vai do maior disco para o menor:
- Se o maior disco já está no pino de destino, ele não precisa se mover: basta resolver os menores.
- Se não está, ele se move exatamente uma vez. Para isso, todos os menores têm de estar no terceiro pino, o único que resta. Depois do movimento dele, os menores são levados, como pilha, até o destino.
Aplicando a regra a cada disco, sai a sequência completa, que é a menor possível: a demonstração mostra que qualquer outro caminho precisa de mais movimentos. Conferimos isso em todas as posições de até 7 discos, comparando com uma busca exaustiva: o número de movimentos bate, e a sequência mais curta é sempre uma só. Para a página não travar, a lista é montada em poucos milissegundos e só as linhas à vista são desenhadas, mesmo com mais de 1 milhão de movimentos.
A fórmula do mínimo de movimentos
De uma pilha completa até outro pino, o mínimo é 2ⁿ − 1, com n discos:
| Discos | Mínimo de movimentos |
|---|---|
| 3 | 7 |
| 4 | 15 |
| 5 | 31 |
| 6 | 63 |
| 7 | 127 |
| 8 | 255 |
| 10 | 1.023 |
| 20 | 1.048.575 |
A cada disco a mais, o trabalho dobra e soma um: mover a pilha menor, mover o disco maior, mover a pilha menor de novo. De uma posição no meio do jogo, o mínimo pode ser menor, e o resolvedor calcula o valor exato.
Como resolver sozinho
Existe um método simples, que funciona na posição inicial:
- Nos movimentos ímpares, mova o menor disco, sempre no mesmo sentido, em círculo (A → B → C → A, se o número de discos for par; A → C → B → A, se for ímpar).
- Nos movimentos pares, faça o único movimento possível que não envolve o menor disco.
Com isso, a pilha chega ao pino C no número mínimo de movimentos, sem precisar decorar nada.
Perguntas frequentes
Quantos movimentos precisa a Torre de Hanói com 3 discos?
Sete. Com 4 discos são 15; com 5, são 31.
E a lenda dos 64 discos?
A história, divulgada junto com o jogo criado pelo matemático francês Édouard Lucas em 1883, fala de monges movendo 64 discos de ouro. Seriam 2⁶⁴ − 1 movimentos, ou cerca de 585 bilhões de anos a um movimento por segundo.
A solução é realmente a menor?
Sim, em qualquer posição de partida. A cada disco fora do lugar, a regra só faz o movimento que é inevitável.
Dá para levar os discos para qualquer pino?
Sim. Escolha A, B ou C como destino, e a solução é recalculada.
Respeita quem prefere menos animação?
Sim. Com a opção de reduzir movimento ativada no sistema, os discos trocam de lugar sem animação e a reprodução começa na velocidade lenta. Veja também os outros resolvedores.