Torre de Hanói

Jogue Torre de Hanói online

O tabuleiro no topo desta página é um jogo gratuito da Torre de Hanói que roda no seu navegador — nada para baixar, nenhuma conta para criar. Escolha de 3 a 15 discos e leve a pilha inteira da torre da esquerda para a da direita.

• Celular ou tablet: toque numa torre para levantar o disco do topo e toque em outra para soltá-lo.
• Mouse: arraste um disco, ou clique numa torre e depois em outra.
• Teclado: ← e → escolhem a torre, ↑ levanta e ↓ solta; 1, 2 e 3 vão direto às torres A, B e C, e Esc devolve o disco.

Errar não custa nada. Desfazer volta a sua última jogada, Reiniciar começa o mesmo tamanho de novo e Dica levanta o disco que a solução mais curta moveria em seguida e diz para onde ele vai. Uma jogada faz isso por você. E se preferir só assistir, Resolução automática termina o quebra-cabeça de onde o tabuleiro estiver, e não apenas do começo.

Nada é contado até você jogar. Depois da primeira jogada o painel mostra:

• suas jogadas, um cronômetro e uma pontuação de eficiência — sua partida como porcentagem de uma partida perfeita;
• se você ainda está no caminho ótimo, ou a quantas jogadas está dele.

A linha do tempo abaixo do tabuleiro guarda a partida inteira. Volte a qualquer posição anterior, ou reproduza a partida a 0,5×, 1×, 2× ou 4×; a mesma velocidade marca o ritmo da Resolução automática. O modo foco tira tudo da tela menos as torres, e a página lembra com quantos discos você jogou por último. Ao terminar, a tela de resultado compara suas jogadas com o mínimo e oferece mais um disco.

O problema da Torre de Hanói

O problema começa com três torres e uma pilha de discos de tamanhos diferentes em uma delas, o maior embaixo. O objetivo é levar a pilha inteira para outra torre, sob três regras:

1. Mova um disco de cada vez.
2. Só o disco do topo de uma torre pode se mover.
3. Um disco maior nunca pode ficar sobre um menor.

Esse é o quebra-cabeça inteiro, e leva cerca de um minuto para aprender. A terceira regra é o que o torna difícil: cada disco precisa esperar em algum lugar permitido enquanto os discos de baixo se movem, e com só três torres nunca sobra espaço. Como jogar Torre de Hanói mostra as regras em imagens, com um tabuleiro de treino e um exemplo resolvido.

O matemático francês Édouard Lucas publicou o quebra-cabeça em 1883. Um ano depois, um artigo de revista que o apresentava acrescentou a lenda que o tornou famoso: sacerdotes brâmanes movendo sessenta e quatro discos de ouro, e o fim do mundo quando terminassem. A uma jogada por segundo, isso levaria cerca de 585 bilhões de anos.

Jogadas mínimas e a fórmula 2ⁿ − 1

O número mínimo de jogadas de uma Torre de Hanói com n discos é 2ⁿ − 1, também escrito 2^n − 1. Três discos precisam de 7 jogadas, quatro precisam de 15, e a Torre de Hanói com 5 discos precisa de no mínimo 31 jogadas. É um piso provado, não um recorde: não existe solução mais curta para tamanho nenhum, e é o número contra o qual a pontuação de eficiência do tabuleiro mede você.

A equação por trás da fórmula

A equação sai direto das regras. Antes que o disco maior possa se mover, os n − 1 discos acima dele precisam estar empilhados na torre auxiliar; então ele atravessa; então aqueles discos voltam por cima dele. Escrevendo T(n) para o menor número de jogadas que faz tudo isso:

T(n) = 2·T(n − 1) + 1, partindo de T(0) = 0 — sem discos, sem jogadas.

Cada tamanho custa o dobro do tamanho de baixo, mais um: 1, 3, 7, 15, 31, 63. Todos eles são uma potência de dois menos um, e é daí que vem a forma fechada T(n) = 2ⁿ − 1. A demonstração de que 2ⁿ − 1 é o mínimo trabalha as duas metades dessa afirmação — por que essa quantidade de jogadas sempre basta e por que menos é impossível — e a calculadora de jogadas mínimas dá o número exato para qualquer quantidade de discos até sessenta e quatro.

Jogadas mínimas por número de discos

Cada tamanho leva à sua solução completa, com todas as jogadas listadas e jogadas num tabuleiro. A maior partida aqui é de 15 discos, ou 32.767 jogadas: cada disco que você acrescenta dobra a duração da partida, mais uma jogada.

O algoritmo da Torre de Hanói e a recursão

A equação acima também é o algoritmo, lida como instruções. Para levar n discos de uma torre de origem a uma de destino:

1. Leve n − 1 discos da origem para a torre auxiliar.
2. Leve o disco maior da origem para o destino.
3. Leve os n − 1 discos da torre auxiliar para o destino.

Os passos 1 e 3 são o mesmo problema com um disco a menos, então o algoritmo os resolve chamando a si mesmo, e uma chamada sem discos para mover simplesmente retorna. Essa é a recursão da Torre de Hanói por inteiro, e é por isso que quase todo curso de computação usa este quebra-cabeça para ensinar recursão. O truque é não tentar enxergar todas as jogadas de uma vez: confie que a chamada menor vai fazer o serviço dela, e os três passos são a solução inteira.

Como o algoritmo faz exatamente 2ⁿ − 1 jogadas, seu tempo de execução é O(2ⁿ), e nada consegue superar isso: cada uma dessas jogadas precisa ser feita. Já o uso de memória é apenas O(n). A página do algoritmo da Torre de Hanói executa o código linha a linha ao lado de um tabuleiro vivo e desenha a árvore de chamadas enquanto anda, e a solução iterativa produz as mesmas jogadas com duas regras e um laço.

Torre de Hanói em Python, Java e outras linguagens

Os três passos se traduzem quase palavra por palavra em código. Torre de Hanói em Python é uma função de sete linhas: um caso base para zero discos, duas chamadas recursivas e a única linha entre elas que imprime uma jogada. Torre de Hanói em Java é o mesmo método dentro de uma classe, e o lugar para descobrir por que a conta de sessenta e quatro discos não cabe num long. Há programas completos também em C, C++, C# e JavaScript.

Todos os códigos foram executados e a saída conferida contra o solucionador deste site, e cada um vem com uma explicação que diz por que cada linha está ali, e não o que a sintaxe faz.

Outras formas de jogar e de aprender

Quando três torres e uma pilha completa ficarem fáceis, há mais para experimentar:

• O desafio do dia — uma posição embaralhada, a mesma para todo mundo, nova à meia-noite UTC. Resolva sem o solucionador para manter a sequência.
• O solucionador — todas as jogadas da solução mais curta a partir de qualquer posição válida, inclusive aquela em que você travou neste tabuleiro.
• Estratégias — a única ideia que se repete por trás de qualquer tamanho, e uma regra que diz sua próxima jogada sem planejar.
• Variantes — quatro torres em vez de três, um anel onde os discos andam num sentido só, duas cores para separar e uma posição inicial aleatória.
• Para professores — um plano de aula de 45 minutos, uma folha para imprimir com gabarito e um tabuleiro para incorporar numa página de curso.

Perguntas frequentes

O que é a Torre de Hanói?

A Torre de Hanói é um quebra-cabeça com três torres e uma pilha de discos de tamanhos diferentes. Você leva a pilha inteira de uma torre para outra, um disco de cada vez, e um disco maior nunca pode ficar sobre um menor. Foi publicado pelo matemático francês Édouard Lucas em 1883.

Dá para jogar Torre de Hanói online de graça?

Sim. O tabuleiro desta página é gratuito, roda em qualquer navegador moderno no celular, tablet ou computador, e não exige download nem conta. A quantidade de discos que você jogou por último e seus melhores resultados ficam salvos no seu próprio navegador, não num servidor.

Qual é o número mínimo de jogadas na Torre de Hanói?

Um jogo perfeito de n discos são 2ⁿ − 1 jogadas. Três discos precisam de 7, cinco precisam de 31 e 15 discos precisam de 32.767. Não existe solução mais curta, então esse número é um piso firme, e não só uma meta.

Como se resolve a Torre de Hanói?

Toda solução é a mesma ideia repetida: para levar uma pilha de n discos ao destino, primeiro tire os n − 1 discos de cima do caminho, para a torre auxiliar; leve o disco maior para o outro lado; e então traga aqueles n − 1 discos por cima dele. A pilha menor obedece exatamente à mesma regra, e é por isso que um único método resolve todos os tamanhos.

Existe um atalho para saber a próxima jogada?

Sim. Em toda jogada ímpar, mova o disco menor uma torre numa direção fixa: para a esquerda se o número de discos for ímpar, para a direita se for par, dando a volta nas pontas — com três discos, a primeiríssima jogada dele vai de A para C. Em toda jogada par, faça a única jogada válida que não toca no disco menor. Alternando as duas você joga uma partida perfeita sem planejar nada.

Com quantos discos posso jogar aqui?

De 3 a 15 discos. Comece com 3 para pegar o formato da solução e depois acrescente um de cada vez — cada disco a mais dobra o trabalho, mais ou menos.

Dá para desfazer uma jogada ou rever minha partida?

Sim. Há um botão de desfazer, e cada partida guarda também uma linha do tempo completa: volte a qualquer posição anterior e o tabuleiro mostra exatamente aquele estado, ou reproduza a partida em quatro velocidades para ver onde você saiu do caminho ótimo.