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
- Movimentos de número ímpar (1º, 3º, 5º…): mova o menor disco (1) para a haste vizinha, em um sentido fixo.
- 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 discos | Ordem 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.
- Início
- Mov. 1 1 para a direita
- Mov. 2 2 para o centro
- Mov. 3 1 para o centro
- Mov. 4 3 para a direita
- Mov. 5 1 para a esquerda
- Mov. 6 2 para a direita
- 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:
- Tirar os n−1 discos de cima do caminho, para o meio.
- Levar o maior disco para a direita.
- 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.
- 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.
- 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.
- 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.
- Tabela de respostas (3 a 10 discos)
- Como resolver com 4 discos (15 movimentos em diagramas)
- Como resolver com 5 discos (31 movimentos)
- Como resolver com 7 discos (127 movimentos)
- Como resolver com 10 discos (1.023 movimentos)
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.
