Como Dominar a Torre de Hanói
TLDR: A Torre de Hanói é resolvida por uma regra recursiva: para mover n discos para o pino de destino, primeiro mova n-1 discos para o pino do meio, depois mova o maior disco para o destino, depois mova n-1 discos por cima. Aplique esta regra em todos os níveis e você sempre atingirá o número mínimo de movimentos. O mínimo é sempre um a menos que uma potência de dois: 3 discos precisa de 7 movimentos, 4 discos precisa de 15, 5 precisa de 31, 6 precisa de 63, 7 precisa de 127.
O Que é o Jogo
A Torre de Hanói começa com uma pilha de discos no pino mais à esquerda, o maior na parte inferior, o menor no topo. Seu objetivo: mover toda a pilha para o pino mais à direita, obedecendo a duas regras. Mova um disco de cada vez. Nunca coloque um disco maior em cima de um menor.
É isso. Sem temporizadores, sem aleatoriedade, sem informação oculta. Apenas lógica e um orçamento de movimentos.
O PlayMemorize vai de 3 a 7 discos. O orçamento de movimentos começa acima do mínimo ótimo para que iniciantes ainda possam vencer enquanto aprendem o padrão; à medida que seu nível sobe, o orçamento se aperta em direção ao mínimo matemático.
As contagens mínimas de movimentos: 3 discos = 7 movimentos, 4 discos = 15 movimentos, 5 discos = 31 movimentos, 6 discos = 63 movimentos, 7 discos = 127 movimentos. Cada nível requer aproximadamente o dobro dos movimentos do nível abaixo, mais um. Se você exceder o orçamento de movimentos, a rodada termina como derrota.
O Algoritmo Recursivo
Tudo na Torre de Hanói segue um padrão, aplicado repetidamente em cada escala:
Para mover n discos do pino A para o pino C, usando o pino B como armazenamento temporário:
- Mova n-1 discos de A para B (usando C como temporário)
- Mova o maior disco de A para C
- Mova n-1 discos de B para C (usando A como temporário)
Esse é o algoritmo completo. Em cada nível do quebra-cabeça, você está executando essa mesma estrutura de três etapas. A beleza é que as etapas 1 e 3 são elas próprias instâncias menores do mesmo problema, resolvidas pela mesma regra.
Vamos rastrear 3 discos para concretizar. Meta: mover os três do pino 1 para o pino 3.
- Etapa 1 (mover 2 discos do pino 1 para o pino 2): mova o disco 1 para o pino 3, mova o disco 2 para o pino 2, mova o disco 1 para o pino 2.
- Etapa 2 (mover o disco 3 do pino 1 para o pino 3): um movimento.
- Etapa 3 (mover 2 discos do pino 2 para o pino 3): mova o disco 1 para o pino 1, mova o disco 2 para o pino 3, mova o disco 1 para o pino 3.
Total: 7 movimentos. Ótimo.
Pensamento em Três Fases. Antes de tocar em qualquer disco, nomeie as três fases em voz alta: “Limpe n-1 discos para o meio; mova o maior para o destino; reconstrua n-1 discos por cima.” Em cada nível de recursão, você está repetindo essa mesma estrutura com um disco a menos. Você não está memorizando uma sequência de movimentos - você está executando um padrão fractal.
Dica: Antes de fazer qualquer movimento, pergunte: “Qual é o maior disco que preciso mover agora?” Tudo que você faz até mover esse disco é preparação. Manter esse enquadramento evita movimentos sem propósito e o mantém no caminho ótimo.
Por Que a Contagem de Movimentos é Fixa
A contagem mínima de movimentos segue diretamente do algoritmo. Resolver n discos requer resolver n-1 discos duas vezes (etapas 1 e 3) mais um movimento do maior disco (etapa 2). Então o total T(n) = 2 vezes T(n-1) mais 1. Com T(1) = 1, isso se expande para: 1, 3, 7, 15, 31, 63, 127 para contagens de discos de 1 a 7.
Cada número é um a menos que uma potência de dois. Três discos: 8 menos 1 = 7. Quatro discos: 16 menos 1 = 15. Cinco discos: 32 menos 1 = 31. Seis discos: 64 menos 1 = 63. Sete discos: 128 menos 1 = 127.
Isso não é coincidência - é a consequência direta de resolver n-1 discos duas vezes cada vez que você resolve n discos. Uma vez que você entende isso, para de ver Hanói como um quebra-cabeça para adivinhar e começa a vê-lo como um algoritmo a executar.
Táticas por Dificuldade
3 a 4 discos (aprendizado): Neste nível, o orçamento de movimentos é confortável. Foque em nomear cada disco mentalmente - “pequeno”, “médio”, “grande” - para nunca confundir qual disco você está mirando. Rastreie as três fases antes de tocar em qualquer coisa. Após cada jogo, explique as fases em voz alta: “Limpei dois discos para o meio, movi o grande, reconstruí por cima.”
Dica: O maior disco deve se mover exatamente uma vez por solução completa. Se você se encontrar querendo movê-lo novamente, a estrutura do algoritmo quebrou. Retorne ao enquadramento de três fases e identifique onde você saiu dos trilhos.
5 a 6 discos (intermediário): O orçamento de movimentos aperta. Cada movimento errante custa. Aplique o algoritmo recursivo estritamente em cada nível. Quando você recursa de n para n-1 discos, seu foco mental deve mudar: você agora está resolvendo um quebra-cabeça de Hanói menor com um conjunto diferente de pinos “origem”, “destino” e “auxiliar”. Rastreie qual papel cada pino desempenha em cada nível de recursão.
A Troca do Pino Auxiliar. Em cada nível de recursão, um pino é a origem, um é o destino e um é auxiliar. Esses papéis giram à medida que você recursa. Ao mover n-1 discos do pino 1 para o pino 2, o pino 3 é auxiliar. Ao então mover n-2 discos do pino 1 para o pino 3, o pino 2 é auxiliar. Rastreie essa troca conscientemente - é a fonte mais comum de confusão em 5 e 6 discos.
7 discos (desafio): Com 127 movimentos mínimos e um orçamento apertado, você não pode pensar movimento por movimento. Pense fase por fase. Antes de começar, mapeie a estrutura de nível superior: mova 6 discos para o meio (63 movimentos), mova o maior disco para a direita (1 movimento), mova 6 discos para a direita (63 movimentos). Depois subdivida cada fase de 6 discos da mesma forma. Esse planejamento de cima para baixo reduz a carga cognitiva e evita o erro de perder o controle de qual fase você está.
Cuidado: Com 7 discos, tentar memorizar a sequência movimento por movimento é não confiável e desnecessário. Confie no algoritmo. Quando você aplica a regra recursiva em cada ponto de ramificação, o movimento correto é sempre determinado. A dúvida e a segunda adivinhação são como você queima movimentos e esgota o orçamento.
Erros Comuns
Tratá-lo como um quebra-cabeça de tentativa e erro. Movimentos aleatórios ocasionalmente parecem produtivos mas se acumulam em becos sem saída. Hanói é um algoritmo, não um quebra-cabeça para resolver por experimentação. Remova a aleatoriedade do seu pensamento completamente.
Perder o controle dos papéis dos pinos. Em três pinos idênticos, “origem”, “destino” e “auxiliar” podem se confundir, especialmente em contagens de discos mais altas. Antes de começar, rotule os pinos explicitamente em sua mente: ESQUERDA = início, CENTRO = meio, DIREITA = destino. Use esses rótulos consistentemente em todo nível de recursão.
Mover o maior disco mais de uma vez. No nível superior de recursão, o maior disco se move exatamente uma vez. Se sentir vontade de movê-lo novamente, pare - a estrutura do algoritmo quebrou. Retorne ao enquadramento de três fases e identifique onde você saiu dos trilhos.
O Ponto de Verificação do Maior Disco. Em cada nível de recursão, o n-ésimo disco deve se mover exatamente uma vez. Após completar a primeira subfase (mover n-1 discos para o pino auxiliar), o n-ésimo disco deve estar livre e sem ter sido movido. Após a etapa 2, deve estar no pino de destino. Se não estiver, você desviou do algoritmo.
Ficar sem movimentos. Isso só acontece quando você não está seguindo o algoritmo, ou quando você fez e depois mentalmente “desfez” movimentos (mudou de ideia no meio da execução e tentou um caminho diferente). Comprometa-se com o algoritmo. Ele é ótimo - não há caminho melhor.
Cuidado: Uma vez que você decidiu sobre um movimento usando o algoritmo recursivo, comprometa-se. Questionar isso durante a execução leva a movimentos desperdiçados. O algoritmo garante otimidade - confie nele e execute sem hesitação.
Um Plano de Prática
Semana 1 - Internalização do algoritmo (3 discos). Jogue jogos de 3 discos diariamente. Após cada jogo, descreva as três fases em voz alta. Repita até que o padrão seja tão familiar que você possa narrar toda a solução antes de fazer o primeiro movimento.
Semana 2 - Escalando (4 a 5 discos). Passe para jogos de 4 discos. A recursão agora vai dois níveis de profundidade. Após cada jogo, rastreie a estrutura: “Recursei para 3, movi o disco grande, recursei novamente.” Jogue três a quatro jogos com 4 discos, depois passe para 5.
Semana 3 - Pressão (6 discos). Com 6 discos, o orçamento de movimentos torna-se a restrição vinculante. Jogue com o algoritmo como único guia. Mire em completar dois jogos de 6 discos dentro de cinco movimentos do mínimo (63 movimentos). Rastreie sua contagem de movimentos e veja-a cair em direção a 63 ao longo da semana.
Semana 4 - Domínio (7 discos). Tente quebra-cabeças de 7 discos. Aplique o planejamento de fases de cima para baixo antes de tocar em qualquer disco. Três vitórias consecutivas com 7 discos com uma contagem de movimentos próxima de 127 sinaliza domínio genuíno.
Dica: Mantenha um registro de suas contagens de movimentos por nível de discos. Assistir sua contagem cair em direção ao mínimo ao longo das sessões é o sinal externo mais claro de que o padrão recursivo está internalizando. Contagens acima de 130 para 7 discos significa que movimentos errantes ainda estão aparecendo; abaixo de 135 com consistência significa que a estrutura está sólida.
A Torre de Hanói é um dos poucos jogos onde o domínio é absoluto e mensurável. Ou você conhece o algoritmo recursivo e o executa, ou não. Uma vez que você o faz, cada nível de dificuldade cede à mesma lógica. Desacelere, nomeie suas fases, confie no algoritmo e a solução está sempre lá.
Torres de Hanói
O clássico · move toda a torre de discos para outra haste, um disco de cada vez, nunca um maior sobre um menor
Jogar agora - é grátisSem conta necessária. Funciona em qualquer dispositivo.
