Torre de Hanói online
Torre de Hanói online: jogue grátis com 3 a 10 discos e deixe o solucionador terminar qualquer posição em que você travar.
As regras
- Leve a torre inteira do primeiro pino até o último.
- Mova um disco por vez, e apenas o disco do topo de um pino.
- Nunca coloque um disco sobre outro menor.
Com n discos, o mínimo de movimentos é 2ⁿ − 1: 7 com três discos e 1.023 com dez. Dica: com um número ímpar de discos, comece levando o menor disco ao último pino; com um número par, ao pino do meio.
Como jogar
Toque em um pino para pegar o disco do topo e toque em outro pino para soltá-lo; também dá para arrastar o disco. Com o teclado, aperte 1, 2 ou 3 para escolher um pino e Z para desfazer. Embaixo do tabuleiro você escolhe de 3 a 10 discos ou um quarto pino. Quer um desafio novo todo dia? Experimente o quebra-cabeça diário.
Como resolver
A solução é recursiva. Para levar n discos do pino A ao pino C, usando B como apoio:
- leve os n − 1 discos menores de A para B;
- leve o maior disco de A para C;
- leve os n − 1 discos menores de B para C.
Cada etapa 1 e 3 é o mesmo problema com um disco a menos, e é por isso que o método funciona com qualquer tamanho. Na prática, há um atalho: o menor disco se move a cada dois movimentos, sempre no mesmo sentido (para o último pino se o número de discos for ímpar, para o do meio se for par). Os outros movimentos não têm escolha, porque só um outro disco pode se mover. Se você travar, o solucionador continua a partir da posição em que você está.
Quantos movimentos são necessários
O mínimo com n discos é 2ⁿ − 1: cada disco a mais dobra o trabalho e ainda soma um movimento. Pela lenda, com 64 discos seriam necessários mais de 18 quintilhões de movimentos, o que levaria cerca de 585 bilhões de anos a um movimento por segundo.
| Discos | Movimentos |
|---|---|
| 3 | 7 |
| 4 | 15 |
| 5 | 31 |
A tabela completa, de 3 a 10 discos, e a demonstração da fórmula estão na página Fórmula e matemática.
Torre de Hanói na sala de aula
A Torre de Hanói é um bom exercício para ensinar recursão, padrões e demonstração por indução. Uma sequência que funciona: os alunos jogam com 3 discos e anotam os 7 movimentos; depois tentam com 4 e 5 e preenchem a tabela acima; por fim, descobrem sozinhos que o número de movimentos dobra e soma um a cada disco, o que leva à fórmula 2ⁿ − 1. O jogo não tem anúncios nem exige cadastro, então funciona direto em computadores e celulares da turma. Há um plano de aula de 50 minutos, ligado à BNCC, na página para professores.
Perguntas frequentes
Qual é o número mínimo de movimentos da Torre de Hanói?
Com n discos, o mínimo é 2ⁿ − 1 movimentos: 7 com três discos, 15 com quatro, 31 com cinco e 1.023 com dez.
Quantos discos tem a Torre de Hanói?
Os brinquedos mais comuns têm de 7 a 9 discos, e o original vendido por Lucas tinha 8. O quebra-cabeça funciona com qualquer quantidade; aqui você pode começar com 3 e ir até 10 discos.
Qual é o primeiro movimento?
Com um número ímpar de discos, leve o menor disco ao último pino; com um número par, ao pino do meio. Daí em diante, o menor disco se move a cada dois movimentos, sempre no mesmo sentido.
A Torre de Hanói sempre tem solução?
Sim. Para qualquer número de discos e qualquer posição válida existe uma solução, e o solucionador do site mostra a mais curta.
Existe uma versão com 4 pinos?
Sim. Com um quarto pino, dez discos precisam de apenas 49 movimentos em vez de 1.023. Escolha 4 pinos embaixo do tabuleiro.
De onde vem a Torre de Hanói?
O quebra-cabeça foi apresentado em 1883 pelo matemático francês Édouard Lucas, que o acompanhou de uma lenda: num templo de Benares, na Índia, monges movem 64 discos de ouro e, quando terminarem, o mundo acaba. O nome Hanói foi só uma escolha de Lucas, sem relação com o lugar da lenda.