Calculadora da Torre de Hanói

Quanto tempo isso é de verdade

Os números acima são exatos e, sozinhos, quase não ensinam nada: passados alguns bilhões, um número enorme se parece muito com outro. O que a aritmética está fazendo de verdade é mais fácil de ver do que de dizer. Como cada disco a mais dobra o trabalho, uma régua com discos igualmente espaçados é uma régua com prazos que se multiplicam — e toda a distância entre uma pausa para o café (dez discos, dezessete minutos) e a idade do universo (cinquenta e nove discos) acaba sendo mais ou menos cinquenta passos.

• 1 disco — 1 jogada — 1 segundo: o primeiro tamanho que alcança um segundo.
• 6 discos — 63 jogadas — 1 minuto: o primeiro tamanho que alcança um minuto.
• 12 discos — 4.095 jogadas — 1 hora: o primeiro tamanho que alcança uma hora.
• 17 discos — 131.071 jogadas — 1 dia: o primeiro tamanho que alcança um dia.
• 25 discos — 33.554.431 jogadas — 1 ano: o primeiro tamanho que alcança um ano.
• 32 discos — 4.294.967.295 jogadas — 136 anos: o primeiro tamanho que alcança uma vida humana.
• 38 discos — 274.877.906.943 jogadas — 8,71 mil anos: o primeiro tamanho que alcança toda a história registrada.
• 59 discos — 576.460.752.303.423.487 jogadas — 18,3 bilhões de anos: o primeiro tamanho que alcança a idade do universo.

A faixa sombreada perto da esquerda é tudo o que dá para jogar aqui. Onze discos são uma sessão longa; vinte e cinco são um ano de jogadas sem parar; cinquenta e nove passam da idade do universo. Nada nas regras muda ao longo desse eixo: só a contagem muda.

A fórmula

Uma partida perfeita de n discos leva exatamente 2ⁿ − 1 jogadas — a fórmula da Torre de Hanói, normalmente escrita 2^n − 1 quando não há expoentes à mão. Isso não é o melhor que alguém já conseguiu: é um piso comprovado. Para o maior disco poder se mover, todos os discos menores precisam estar empilhados fora do caminho, na torre auxiliar, e assim que ele atravessa, todos têm de voltar por cima dele. Duas transferências completas de n − 1 discos, mais uma jogada:

T(n) = 2·T(n − 1) + 1, partindo de T(0) = 0: sem discos, nenhuma jogada.

1. 1Mova os n−1 discos de cima para a torre auxiliar. Nada mais pode acontecer enquanto eles estiverem no caminho.

2. 2O maior disco agora está livre, e o destino dele está vazio. Ele passa em uma única jogada — a única de que esta fase precisa.

3. 3Reconstrua a pilha de n−1 discos em cima dele. É o mesmo problema outra vez com um disco a menos, até chegar a um único disco que se move em uma jogada.

Desenrolando, dá 1, 3, 7, 15, 31, 63 — cada um o dobro do anterior mais um, que é a sequência dos números logo abaixo de uma potência de dois. Cada disco que você acrescenta faz um pouco mais do que dobrar o trabalho, e é por isso que o quebra-cabeça vai de uma pausa para o café a mais do que o universo existe em menos de cinquenta passos.

Essa mesma recorrência é a origem da fama do quebra-cabeça nos cursos de computação. Como o trabalho dobra a cada disco, a solução recursiva roda em tempo O(2ⁿ) — e não há nenhum algoritmo mais esperto escondido aí, já que a própria contagem de jogadas é exponencial e cada jogada precisa ser impressa. O que ela não custa é memória: a recursão só desce um disco de cada vez, então mantém O(n) quadros de pilha — um por disco mais um para o caso base: dezesseis no maior tabuleiro daqui, sessenta e cinco na lenda. A dedução completa, e por que esta não é uma recorrência à qual o Teorema Mestre se aplica, está na página do algoritmo da Torre de Hanói.

Jogadas mínimas por número de discos

Estes são os tamanhos que dá para jogar aqui. A faixa de dificuldade é a mesma que o tabuleiro mostra ao lado do seletor de discos, e cada número de discos leva à lista de jogadas que o resolve.

Além do tabuleiro

Acima de 15 discos, o quebra-cabeça deixa de ser algo que se joga e passa a ser algo que se calcula. As contagens continuam exatas — elas só não são mais alcançáveis numa vida humana.

Esses números têm nome

Um número logo abaixo de uma potência de dois é um número de Mersenne, escrito M_n = 2ⁿ − 1 — ou seja, todo valor das tabelas acima é um, e a contagem de jogadas de uma partida da Torre de Hanói nunca é outra coisa. Quando um número de Mersenne por acaso é primo, ele é um primo de Mersenne, e são esses os números sobre os quais a caça a primos recordistas roda há décadas, porque 2ⁿ − 1 é bem mais barato de testar do que um número qualquer daquele tamanho.

M_n só pode ser primo quando o próprio n é primo, mas isso sozinho não basta — e o contraexemplo é uma partida que dá para jogar aqui. Onze é primo; suas 2.047 jogadas não são, já que 2.047 = 23 × 89. Dos tamanhos deste tabuleiro, os discos cuja contagem de jogadas é prima são 3, 5, 7 e 13. OEIS A000225 é a sequência completa.

A lenda dos sessenta e quatro discos

O quebra-cabeça foi posto à venda em 1883 e, em menos de um ano, já tinha uma história: num templo em Benares, sacerdotes movem sessenta e quatro discos de ouro entre três agulhas de diamante, e quando o último disco for colocado o mundo acaba. A aritmética tranquiliza. Sessenta e quatro discos levam 18.446.744.073.709.551.615 jogadas e, a uma jogada por segundo, isso dá 585 bilhões de anos — umas quarenta vezes a idade atual do universo.

Perguntas frequentes

Quantas jogadas a Torre de Hanói leva?

O mínimo é 2ⁿ − 1 jogadas para n discos. Três discos levam 7, cinco levam 31, dez levam 1.023 e vinte levam 1.048.575. Cada disco a mais faz um pouco mais do que dobrar o total, porque resolver n discos significa resolver n − 1 discos duas vezes com uma jogada no meio.

Por que a fórmula é 2ⁿ − 1?

Para mover n discos, primeiro é preciso tirar os n − 1 de cima do caminho, depois mover o maior disco uma vez, depois trazer esses n − 1 de volta por cima dele. Isso dá T(n) = 2·T(n−1) + 1 com T(1) = 1, e desenrolando dá 1, 3, 7, 15, 31 — cada um o dobro do anterior mais um, que é exatamente 2ⁿ − 1.

Qual é a complexidade de tempo da Torre de Hanói?

O(2ⁿ). Cada disco dobra o trabalho, então a solução recursiva faz 2ⁿ − 1 jogadas, e nenhum algoritmo consegue superar isso: as jogadas em si precisam ser produzidas, e são essas. O espaço é só O(n): a recursão desce um disco de cada vez, então guarda no máximo n + 1 quadros de pilha ao mesmo tempo — por isso uma chamada de 64 discos esgotaria sua paciência muito antes de esgotar a pilha.

Quanto tempo levariam 64 discos?

Sessenta e quatro discos precisam de 18.446.744.073.709.551.615 jogadas. A uma jogada por segundo, isso é 585 bilhões de anos — muito mais do que a idade atual do universo, que é justamente o ponto da lenda anexada ao quebra-cabeça em 1884.

Uma solução pode ser mais curta que 2ⁿ − 1?

Não. 2ⁿ − 1 é um limite inferior comprovado, não apenas o melhor resultado conhecido: o maior disco precisa se mover pelo menos uma vez e, antes disso, todos os discos menores têm de estar fora dele e fora do destino dele. Isso força as duas transferências parciais, e o argumento se repete até embaixo.

A calculadora serve para um tabuleiro meio resolvido?

Esta página não — 2ⁿ − 1 pressupõe que todos os discos começam em uma torre. Para a solução mais curta a partir de uma posição que já está no meio do caminho, use o solucionador, que calcula o caminho ótimo a partir de qualquer arranjo válido. Abrir o solucionador →