Para resolver a Torre de Hanói, só há 2 passos para decorar. Repetindo-os alternadamente, você move a torre com o menor número de movimentos, com qualquer quantidade de discos. Neste artigo, explicamos o caso de mover a torre da haste esquerda para a direita (as regras estão em O que é a Torre de Hanói?). Os discos são numerados 1, 2, 3… do menor para o maior.

Resolver é repetir 2 passos

  1. Movimentos de número ímpar (1º, 3º, 5º…): mova o menor disco (1) para a haste vizinha, em um sentido fixo.
  2. Movimentos de número par (2º, 4º, 6º…): faça o movimento possível com os discos que não são o 1. O movimento possível é sempre um só.

É só isso. O 1 se move de 2 em 2 movimentos, e nos movimentos entre eles os outros discos se movem uma vez cada.

Como escolher o sentido do disco menor

O sentido do 1 depende da quantidade de discos. Pense nas 3 hastes como um círculo, e ao chegar à ponta volte para a ponta oposta. Ao mover a torre da esquerda para a direita, a ordem é esta.

Quantidade de discosOrdem do disco 1
Ímpar (3, 5, 7…)esquerda→direita→meio→esquerda…
Par (4, 6, 8…)esquerda→meio→direita→esquerda…

Para lembrar: “com uma quantidade ímpar, no 1º movimento você põe o 1 direto na haste de destino”. Com uma quantidade par, no 1º movimento você o põe na haste que não é a de destino (o meio). Depois de escolher o sentido, não o mude até o fim.

Para mover para a haste do meio, pense trocando “direita” e “meio” na tabela.

Confira com 3 discos

São 3 discos (ímpar), então o 1 gira na ordem “esquerda → direita → meio → esquerda”. O disco dourado é o que foi movido naquele movimento.

  1. 321 Início
  2. 321 Mov. 1 1 para a direita
  3. 321 Mov. 2 2 para o centro
  4. 321 Mov. 3 1 para o centro
  5. 213 Mov. 4 3 para a direita
  6. 123 Mov. 5 1 para a esquerda
  7. 132 Mov. 6 2 para a direita
  8. 321 Mov. 7 1 para a direita

Vê-se que nos movimentos 1, 3, 5 e 7 só o 1 está girando, e nos movimentos 2, 4 e 6 é “o único movimento possível sem o 1”.

Por que o movimento de número par fica definido

Nos movimentos de número par, compare os discos do topo das 2 hastes onde o 1 não está. Só dá para mover o menor sobre o maior (ou para uma haste vazia).

  • Sobre o 1 não se pode pôr nenhum disco (porque não há disco menor que o 1).
  • Das 2 hastes restantes, não se pode pôr o disco grande sobre o pequeno.

Por isso, o movimento possível é sempre um só. A única dúvida é o sentido do 1 nos movimentos ímpares, e, uma vez decidido no início, as mãos seguem sem precisar pensar.

A ideia de “tirar os de cima e levar o maior”

Além de decorar os passos, há uma forma de pensar por que isso resolve. Para mover uma torre de n discos da esquerda para a direita, basta dividir em 3 partes:

  1. Tirar os n−1 discos de cima do caminho, para o meio.
  2. Levar o maior disco para a direita.
  3. Mover os n−1 discos do meio para a direita.

Os passos 1 e 3 são o problema “mover uma torre com 1 disco a menos”, então dá para usar a mesma ideia de novo. Com 4 discos, é “tirar 3 → levar o 4 → trazer os 3”. Para tirar os 3, é “tirar 2 → levar o 3 → trazer os 2”… e assim se divide em problemas menores. Por essa ideia, também se entende que o número de movimentos é 2ⁿ−1 (fórmula do mínimo de movimentos).

Como se recuperar quando se perde

Se você esqueceu os passos e os discos ficaram numa disposição bagunçada, não tem problema. Com esta ideia, dá para se recuperar de qualquer ponto.

  1. Entre os discos que ainda não estão empilhados corretamente na haste da direita, procure o maior. Esse é o próximo disco a levar.
  2. Para levá-lo para a direita, todos os discos menores que ele precisam estar juntos na 1 haste restante, que não é a em que ele está nem a da direita.
  3. Juntar os discos menores é repetir a mesma ideia. Pense na haste onde juntá-los como a “haste de destino” e recomece do 1.

A dica é decidir o destino começando pelos discos grandes. O modo “Desafios” do app (arrumar discos espalhados na forma do modelo) também se resolve com essa ideia.

Dicas para vencer

  • Conte os movimentos: nos movimentos ímpares você sempre move o 1, então, se souber qual é o movimento, não terá dúvida sobre qual disco mover.
  • Quanto maior o disco, menos ele se move: o 1 se move na metade dos movimentos, mas o maior disco se move só 1 vez. Se você está movendo um disco grande várias vezes, está dando voltas.
  • No começo, use 3 ou 4 discos: até os 2 passos entrarem no corpo, é bom repetir algumas vezes com poucos discos. Quando se acostumar, aumente para 5 e 7.

Sequências por quantidade de discos

As sequências e as posições-guia no caminho para cada quantidade de discos estão nos artigos abaixo.

Jogue para testar

No tabuleiro abaixo, teste os 2 passos. Ao tocar em uma haste, o disco do topo é levantado, e ao tocar em outra haste ele é colocado lá. Começa com 4 discos (um número par), então no 1º movimento o 1 vai para o meio.

4321
Jogadas: 0 (mínimo 15)

Leve a torre inteira da haste esquerda para a direita. Toque numa haste para levantar o disco de cima.