Resolver Torre de Hanói: Solução Passo a Passo

Veja a solução da Torre de Hanói de 3 a 20 discos, a partir de qualquer posição, com o mínimo de movimentos exato, a lista completa e a animação passo a passo.

preguicoso.com.br/resolvedores/resolver-torre-de-hanoi

Prefere jogar? Torre de Hanói Online: Jogue e Veja a Solução

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.

Destino
Posição de partida

Toque no pino de cada disco. Em cada pino, os discos ficam sempre em ordem de tamanho.

1
2
3
4
5
54321
A
B
C destino

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

  1. Escolha o número de discos e o pino de destino.
  2. 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.
  3. O mínimo de movimentos e a lista aparecem na hora.
  4. 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:

DiscosMínimo de movimentos
37
415
531
663
7127
8255
101.023
201.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:

  1. 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).
  2. 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.

Ferramentas relacionadas

Incorporar esta ferramenta no seu site

Copie o código e cole no HTML do seu site ou blog. É grátis; só pedimos que mantenha o link para o Preguiçoso abaixo da ferramenta.

Esta ferramenta foi útil? Obrigado pela resposta!