Como jogar Torre de Hanói

A Torre de Hanói é um dos quebra-cabeças mais antigos e elegantes da matemática. Você começa com três hastes e uma pilha ordenada de discos na haste esquerda, cada disco menor que o de baixo, formando uma pirâmide. O desafio parece trivial e acaba sendo um verdadeiro teste de planejamento.

Objetivo

Mova a pilha inteira da haste esquerda para a direita, reconstruída na mesma ordem, com o menor no topo. A haste central é sua para usar como descanso temporário pelo caminho.

Regras

• Mova apenas um disco por vez, sempre o disco do topo de uma haste.
• Um disco maior nunca pode descansar sobre um menor. Essa única regra é o que torna o quebra-cabeça interessante.

Controles

Toque ou clique em uma haste para pegar o disco do topo dela; o disco se eleva e espera. Toque em uma segunda haste para soltá-lo lá, ou toque na mesma haste de novo para cancelar e devolvê-lo. No teclado, pressione 1, 2 ou 3 para as hastes esquerda, central e direita. Você pode escolher com quantos discos jogar, de uns rápidos 3 até uns exigentes 8: use o botão de número de discos para mudar a dificuldade.

Estratégia

Há um lindo truque recursivo por trás da solução perfeita. Para mover uma pilha de N discos para uma haste alvo, primeiro mova os N−1 discos superiores para a haste livre, depois passe o disco maior para o alvo e por fim mova aquela pilha de N−1 por cima. Também funciona um ritmo mais simples: mova sempre o disco menor em turnos alternados, em uma mesma direção constante, e nos turnos intermediários faça o único outro movimento legal disponível.

A matemática

O menor número de movimentos para N discos é exatamente 2ᴺ − 1. Assim, 3 discos se resolvem em 7 movimentos, 5 discos em 31, 7 em 127, e uma pilha completa de 8 leva 255 movimentos perfeitos. Tente igualar o número ótimo quando tiver aprendido o padrão.