Estratégia da Torre de Hanói: resolva em 2^n − 1 movimentos (2026)

Última atualização: 17 de outubro de 2026 · Testado no build Tower of Hanoi da Playnesta (quebra-cabeça matemático de domínio público de Édouard Lucas, 1883; o módulo de regras, a casca, a folha de estilo, a ponte e o shim de toque são originais Playnesta, MIT; o layout da interface inspira-se em AJLoveChina/Hanoi @ 917b8d6, MIT, apenas como referência de mecanismo) · 3 pinos · 3 a 8 discos, padrão 4 · ótimo 2^n − 1 movimentos (3 discos → 7, 4 → 15, 5 → 31, 6 → 63, 7 → 127, 8 → 255)

Método: cada número abaixo é uma constante do módulo de regras entregue js/hanoi.js (original Playnesta, MIT), lida e verificada nesta sessão, não citada de terceiros. O quebra-cabeça é totalmente determinístico, então ?disks=5 reproduz a mesma posição inicial para todos, e não há build upstream para observar. Constantes verificadas: 3 pinos (o pino 0 começa com todos os discos, o maior embaixo e o menor em cima; os pinos 1 e 2 começam vazios); número de discos 3 a 8, padrão 4; o ótimo é 2^n − 1 movimentos; um movimento é legal apenas quando o pino de destino está vazio ou seu disco do topo é maior que o que se move, e um movimento ilegal (disco maior sobre um menor) é rejeitado na hora e não muda nada; a vitória só dispara quando uma torre completa aterrissa em um pino diferente do inicial; Desfazer recua um movimento e apaga o estado de vitória; o contador de movimentos se mede contra o ótimo e sobe para Perfeito! quando você resolve no mínimo. Controles: arraste um disco para outro pino, ou toque um pino para levantar seu disco do topo e toque outro para soltar; o menu de número de discos (3 a 8), os botões Desfazer, Regras e Novo jogo; um banner "Resolvido!" com "Jogar de novo" ao fim. Não há cronômetro, então jogue no seu ritmo. O que segue é estratégia — a página do jogo já explica como operar o tabuleiro; aqui vai como resolvê-lo no mínimo de movimentos.

1. O jogo inteiro é um número: 2^n − 1

Para n discos o mínimo de movimentos possível é 2^n − 1, e este build mostra e pontua contra ele. Três discos exigem 7, quatro 15, cinco 31, seis 63, sete 127, oito 255. Isso não é uma meta arbitrária — é o piso matemático, e nenhum humano pode fazer melhor.

A maioria dos que "resolvem" a Torre de Hanói faz em duas ou três vezes o ótimo, porque movem discos de forma oportunista e só notam os movimentos desperdiçados no fim. O contador e o banner Perfeito! deste build tornam essa perda visível: ele só sobe para Perfeito quando seu número de movimentos é igual a 2^n − 1 na vitória. Até você ver esse banner, você não resolveu o quebra-cabeça — apenas terminou. Então o primeiro objetivo não é "mover a torre", mas "mover a torre em 2^n − 1 movimentos", e tudo abaixo é o caminho.

2. A receita recursiva que toca o piso

A solução ótima tem forma recursiva, e uma vez que você a vê o quebra-cabeça deixa de ser busca e vira lista de verificação. Para mover uma torre de n discos do pino A para o pino C, usando o pino B como reserva:

Mova os n − 1 discos do topo de A para B (usando C como reserva).
Mova o maior disco de A para C.
Mova a torre de n − 1 de B para C (usando A como reserva).

Esse é todo o algoritmo. O passo 2 é o único movimento do maior disco; os passos 1 e 3 são o mesmo problema um tamanho menor. Como o maior disco só pode se mover quando não há nada sobre ele e o destino está vazio, você é forçado a liberá-lo primeiro — e liberá-lo significa resolver a torre menor, que por sua vez deve liberar seu maior disco, e assim por diante até um único disco.

A consequência prática: o maior disco se move exatamente uma vez, e só no ponto médio da solução. Se seu maior disco se moveu mais de uma vez, você não está no caminho ótimo — o reenterrou e terá de liberá-lo de novo. Fique atento: uma sessão em que o disco de baixo segue sendo levantado é uma sessão que terminará bem acima de 2^n − 1.

3. Os três erros que custam movimentos

Mover o maior disco cedo demais. Você não pode movê-lo até que seu pino só o contenha, então cada movimento feito antes de a torre de n − 1 estar totalmente estacionada no pino de reserva é um movimento que atrasa o único movimento que importa. Iniciantes costumam embaralhar os discos de cima "para começar" e só então percebem que o disco de baixo ainda está preso.

Tratar o pino vazio como decoração. O pino vazio não é uma reserva que você usa de vez em quando — é o terreno de montagem que torna a recursão possível. Num jogo de três pinos, a qualquer momento um pino sustenta a torre que você constrói, outro a torre que você desmonta e o terceiro está livre. Se você não usa conscientemente os três papéis, faz trabalho extra para contornar o que ignorou.

Jogar com ganância. O movimento legal que parece melhor agora raramente é o que a recursão quer em seguida. "Mover o menor disco" parece produtivo porque sempre é legal, mas a sequência ótima alterna discos pequenos e grandes num padrão fixo (para número ímpar de discos o menor disco cicla A → C → B → A; para par, A → B → C → A). Se você para de pensar e segue movendo o menor disco legal, termina — mas não em 2^n − 1.

4. Suba a escada de discos e saiba quando parar

A dificuldade não é linear, é exponencial, e os números de movimentos dizem isso honestamente:

3 discos / 7 movimentos — aprenda a recursão aqui. Você pode ter toda a solução na cabeça.
4 discos / 15 movimentos — o primeiro tamanho em que deve confiar na receita em vez de improvisar.
5 discos / 31 movimentos — um quebra-cabeça real; um erro e você passa 10.
6 discos / 63 movimentos — uma sessão; planeje terminar de uma vez ou perderá o fio.
7 discos / 127 movimentos — um projeto; use Desfazer com intenção.
8 discos / 255 movimentos — uma maratona; o jogo permite, mas a maioria das sessões deve viver entre 4 e 6.

O caminho de treino honesto é 3 → 4 → 5, e só então 6. Pular para 8 "para ver o grande" não ensina nada, porque 255 movimentos de improvisação são fadiga, não prática. O menu de número de discos (3 a 8) e o parâmetro ?disks=n da URL deixam você fixar um tamanho, então fixe um tamanho por uma semana e persiga o banner Perfeito! nele antes de subir.

5. Use Desfazer como professor, não como muleta

Desfazer recua um movimento e apaga o estado de vitória, então é a forma mais limpa de aprender a recursão: jogue até duvidar, volte à última posição que entendeu e derive o próximo movimento da receita em vez de chutar. Como o jogo não tem cronômetro, não há penalidade por parar para pensar — a única coisa medida é o número de movimentos.

Dois hábitos que ajudam: repita o mesmo seed com ?disks=4 (ou outro) até acertar Perfeito! duas vezes seguidas, e diga em voz alta qual disco você vai mover e por quê antes de movê-lo. Se não puder dizer qual disco e por quê, está chutando, e chutar é o que empurra o contador acima de 2^n − 1. O jogo também redistribui a mesma torre para um mesmo valor de ?disks=, então você pode treinar uma posição em vez de reiniciar de uma nova posição aleatória a cada vez.

FAQ

Como isso difere das regras da página do jogo?

A página do jogo explica como o tabuleiro funciona — três pinos, só o disco do topo, o maior nunca cobre o menor, arrastar ou tocar, o contador contra o ótimo, Desfazer, 3 a 8 discos, sem cronômetro. Este guia dá isso por sabido e joga a camada de cima: o piso 2^n − 1, a receita recursiva, os três erros, a escada de discos e como treinar. Leia as regras primeiro, depois persiga o banner Perfeito!.

2^n − 1 é de fato o mínimo possível?

Sim. O maior disco deve se mover ao menos uma vez, e para movê-lo os n − 1 discos acima devem estar fora de seu pino e do caminho; por indução isso exige ao menos 2^(n−1) − 1 movimentos antes e 2^(n−1) − 1 depois, mais o único movimento do maior disco. Três pinos é o mínimo que torna o problema não trivial, e com três pinos o piso é exatamente 2^n − 1. Variantes de quatro pinos (o quebra-cabeça de Reve) têm piso mais baixo, mas este jogo usa três pinos.

Por que o banner diz "Perfeito!" só às vezes?

Porque "Perfeito!" é reservado para resolver em exatamente 2^n − 1 movimentos. Resolver em mais movimentos ainda ganha — o banner "Resolvido!" dispara e o número de movimentos é mostrado contra o ótimo — mas Perfeito só ativa quando seu número iguala o piso. Se você nunca viu, seu número de movimentos está acima do piso; o contador diz por quanto.

Toda posição pode ser resolvida?

Sim. A posição inicial é sempre uma torre completa num pino, e a receita a resolve para qualquer n de 3 a 8. Não há embaralhamento nem beco sem saída — um movimento ilegal é simplesmente rejeitado e não muda nada, então você não pode se pintar num canto. Você sempre pode desfazer até um estado bom conhecido.

Em qual número de discos devo treinar?

Comece em 3 até acertar Perfeito! duas vezes seguidas, depois 4, depois 5. A maioria dos jogadores estagna em 5 discos (31 movimentos), e é um bom lugar para ficar — 6 e acima são para quando você quer uma sessão mais longa, não para aprender. Evite o 8 para treino; 255 movimentos de improvisação são fadiga, não prática.

Onde posso jogar?

Bem na página tower-of-hanoi deste site. O quebra-cabeça é um problema matemático de domínio público publicado por Édouard Lucas em 1883, então não há arquivos upstream reutilizados byte a byte; o módulo de regras, a casca da página, a folha de estilo, a ponte de analítica e o shim de toque são todos originais Playnesta e MIT. O layout da interface inspira-se em AJLoveChina/Hanoi @ 917b8d6 (MIT), que foi lido apenas como referência de mecanismo e não é redistribuído aqui. Playnesta Games é o desenvolvedor e editor desta implementação web concreta.