Jogue Torre de Hanói online
A Torre de Hanói é um quebra-cabeça com três pinos e uma pilha de discos de tamanhos diferentes. O objetivo é levar a pilha inteira do pino A para o pino C, movendo um disco por vez e sem nunca colocar um disco maior sobre um menor. Escolha de 3 a 10 discos e jogue abaixo; se travar, a solução é mostrada a partir da posição em que você estiver.
Toque no pino de origem e depois no de destino, ou arraste o disco de cima. No teclado: teclas 1, 2 e 3, ou setas + Enter.
Como jogar
- Toque ou clique no pino de origem e depois no pino de destino: o disco de cima muda de lugar. Também dá para arrastar o disco.
- No teclado: as teclas 1, 2 e 3 escolhem os pinos A, B e C. As setas levam o foco de um pino a outro e Enter confirma. Esc cancela a seleção.
- Desfazer volta um movimento por vez; Reiniciar recomeça com o mesmo número de discos.
- O placar mostra os seus movimentos, o mínimo possível, o tempo e o seu recorde para aquele número de discos (guardado neste navegador).
Regras da Torre de Hanói
- Só se move um disco por vez.
- Só o disco do topo de um pino pode ser movido.
- Um disco nunca pode ficar sobre outro menor. Se você tentar, o jogo avisa e o movimento não é contado.
- Vence quem empilha todos os discos no pino C.
Mínimo de movimentos: a fórmula 2ⁿ − 1
Com n discos, o menor número de movimentos é 2ⁿ − 1. O motivo é simples: para mover o disco maior, todos os outros precisam estar empilhados no pino que sobra. Então você move n − 1 discos, depois o maior, depois os n − 1 de novo — o dobro do caso anterior, mais um. Cada disco a mais dobra o trabalho.
| Discos | Mínimo de movimentos | A 1 movimento por segundo |
|---|---|---|
| 3 | 7 | 7 segundos |
| 4 | 15 | 15 segundos |
| 5 | 31 | 31 segundos |
| 6 | 63 | 1 min 3 s |
| 7 | 127 | 2 min 7 s |
| 8 | 255 | 4 min 15 s |
| 9 | 511 | 8 min 31 s |
| 10 | 1.023 | 17 min 3 s |
Solução para 3 discos, passo a passo
A solução é recursiva: para levar 3 discos de A para C, leve os 2 menores para B, mova o disco 3 para C e traga os 2 menores de B para C. Mover “os 2 menores” é o mesmo problema, só que menor. Na prática, são 7 movimentos:
- Disco 1: A → C
- Disco 2: A → B
- Disco 1: C → B (os dois menores estão em B)
- Disco 3: A → C (o maior chega ao destino)
- Disco 1: B → A
- Disco 2: B → C
- Disco 1: A → C
Dois atalhos ajudam a não se perder com mais discos:
- O disco 1 se move a cada duas jogadas, sempre no mesmo sentido. Com número ímpar de discos, ele faz A → C → B → A; com número par, A → B → C → A.
- Nas jogadas intermediárias, só existe um movimento válido que não mexe no disco 1. Faça-o.
O botão Mostrar solução aplica a mesma ideia a qualquer posição, não só à inicial: encontra o maior disco fora do lugar, abre caminho para ele e repete o raciocínio com os menores. Dá para reproduzir, pausar, mudar a velocidade ou avançar passo a passo.
História: Édouard Lucas e a lenda dos 64 discos
O quebra-cabeça foi inventado pelo matemático francês Édouard Lucas e lançado em 1883. Ele o apresentou como obra de um certo “N. Claus (de Siam)” — um anagrama de “Lucas d’Amiens”, a cidade onde nasceu.
O jogo vinha acompanhado de uma lenda: num templo em Benares, na Índia, sacerdotes moveriam 64 discos de ouro entre três agulhas de diamante, seguindo as mesmas regras. Quando terminassem, o mundo acabaria. Não há motivo para pressa: 64 discos exigem 2⁶⁴ − 1 = 18.446.744.073.709.551.615 movimentos. A um movimento por segundo, sem errar nenhum, são cerca de 585 bilhões de anos — mais de 40 vezes a idade estimada do universo, de 13,8 bilhões de anos.
A Torre de Hanói no ensino
A torre é um exemplo clássico em aulas de programação e de matemática. Em programação, ela mostra a recursão: a função que move n discos chama a si mesma para mover n − 1. Em matemática, a fórmula 2ⁿ − 1 é um exercício comum de indução: vale para 1 disco (1 movimento) e, se vale para n − 1 discos, vale para n, porque 2 × (2ⁿ⁻¹ − 1) + 1 = 2ⁿ − 1.
Gosta de quebra-cabeças de lógica? Experimente também o Sudoku, o 2048, o Campo Minado e a Paciência, ou veja os desafios de hoje em Jogos do Dia.
Perguntas frequentes
Quantos movimentos são necessários com 3 discos? E com 4?
Com 3 discos, o mínimo é 7 movimentos; com 4, são 15. A regra geral é 2ⁿ − 1: 31 para 5 discos, 63 para 6, 127 para 7 e assim por diante.
A solução funciona se eu já tiver mexido nos discos?
Sim. Ela é calculada a partir da posição atual, com o menor número de movimentos dali até o pino C, e é recalculada se você fizer uma jogada por conta própria.
Usar a solução conta para o recorde?
Não. Os movimentos automáticos entram no contador, mas a partida deixa de valer para o recorde. O recorde guarda o menor número de movimentos e, no empate, o menor tempo.
Dá para resolver com menos de 2ⁿ − 1 movimentos?
Não, com três pinos e as regras tradicionais esse é o mínimo comprovado. Se o seu contador terminar exatamente nesse número, a solução foi perfeita.