Torre de Hanói: perguntas frequentes

Existe um, e ele é mecânico mais do que esperto: em toda jogada ímpar, mova o disco menor uma torre na mesma direção — para a esquerda se o número de discos for ímpar, para a direita se for par, dando a volta nas pontas, de modo que com três discos a primeiríssima jogada dele vai de A para C. Em toda jogada par existe sempre uma única jogada válida que não toca no disco menor, então você a faz sem pensar. Alterne as duas e joga uma partida perfeita sem planejar um passo sequer. A página de estratégias desenvolve isso.

Comece com a pilha inteira na torre da esquerda, o disco menor em cima. O objetivo é a mesma pilha na torre da direita. Três regras: um disco de cada vez, sempre o disco do topo de uma torre, e nunca um disco maior sobre um menor. Com três discos o jogo mais curto são sete jogadas em três grupos: A→C, A→B, C→B monta os dois discos menores na torre do meio; A→C deixa o disco maior atravessar; e B→A, B→C, A→C remonta aqueles dois por cima dele. Como jogar, com um tabuleiro de treino.

Fácil de aprender, e difícil de um jeito só: fica duas vezes mais longa a cada disco que você acrescenta. Três discos são sete jogadas, e a maioria das pessoas — crianças a partir de uns seis anos — termina na primeira tentativa. Lá pelos cinco ou seis discos a tentativa e erro para de funcionar e é preciso um método, e o difícil do método é confiar em jogadas que parecem andar para trás, como empilhar tudo na torre do meio quando o objetivo está à direita. Quando cai a ficha da ideia recursiva, todo tamanho é o mesmo quebra-cabeça. Por que a ideia recursiva é o quebra-cabeça inteiro.

Não existe entidade que homologue recordes de velocidade da Torre de Hanói como existe para o cubo mágico, então os tempos anunciados não são comparáveis e em geral nem dizem quantos discos foram usados — que é o único número que importa. Faça a conta: um jogo perfeito de n discos são 2ⁿ − 1 jogadas, e quem tem prática sustenta cerca de duas jogadas por segundo. Isso dá uns quatro segundos para três discos, uns nove minutos para dez discos e suas 1.023 jogadas, e cerca de quatro horas e meia para 15 discos e suas 32.767. O tabuleiro deste site guarda o seu menor número de jogadas para cada quantidade de discos no seu navegador, e mostra o seu tempo na tela de resultado. A calculadora dá o tempo para qualquer tamanho.

2ⁿ − 1, e isso é um piso provado, não o melhor resultado conhecido. Três discos precisam de 7 jogadas, quatro precisam de 15, cinco precisam de 31, dez precisam de 1.023 e 15 precisam de 32.767. A prova tem duas metades: o método recursivo alcança esse número, e nenhuma solução consegue superá-lo, porque o disco maior precisa se mover pelo menos uma vez e todos os discos menores acima dele precisam ser tirados antes para a torre auxiliar e trazidos de volta depois. As duas metades da prova, por inteiro.

T(n) = 2·T(n − 1) + 1, com T(0) = 0. Ela se lê direto do método: para mover n discos você tira n − 1 discos do caminho, leva um disco para o outro lado e traz aqueles n − 1 discos de volta — duas soluções menores mais uma única jogada. Desdobrando, chega-se a T(n) = 2ⁿ − 1, o que você pode conferir por indução: se T(n − 1) = 2ⁿ⁻¹ − 1, então T(n) = 2(2ⁿ⁻¹ − 1) + 1 = 2ⁿ − 1. Resolvendo a recorrência, passo a passo.

Não no sentido computacional, apesar do número exponencial de jogadas. O algoritmo tem poucas linhas, decidir a próxima jogada leva tempo constante, e a solução só é exponencialmente longa porque a resposta é: imprimir 2ⁿ − 1 jogadas não dá para fazer em menos de 2ⁿ − 1 passos. Não é NP-difícil, e achar a rota mais curta entre duas posições válidas quaisquer com três hastes também se resolve de forma eficiente. A versão genuinamente difícil é a de quatro hastes, cuja solução ótima foi conjecturada em 1941 e só foi provada quando Thierry Bousch resolveu a questão em 2014. O algoritmo e quanto ele custa.

Use o método de Frame–Stewart. Com quatro hastes você não move mais n − 1 discos de uma vez: escolhe um corte k, leva os k discos de cima para uma haste livre usando as quatro hastes, leva os n − k discos restantes ao destino usando só três — a livre está ocupada, então essa parte é o quebra-cabeça clássico — e depois põe os k discos por cima. Testando todo k e ficando com o melhor, obtém-se a contagem ótima, que despenca de forma espetacular: 15 discos caem de 32.767 jogadas em três hastes para 129 em quatro. Jogue o quebra-cabeça de quatro hastes.

Divisão e conquista, expressa como recursão. A solução padrão é uma única função — mover n − 1 discos da origem para a haste auxiliar, mover o disco n da origem para o destino, mover aqueles n − 1 discos da auxiliar para o destino — com o caso base não fazendo nada quando n chega a zero. Existe um algoritmo iterativo equivalente que não usa recursão nenhuma: mover repetidamente o disco menor uma torre numa direção fixa e depois fazer a única outra jogada válida. Os dois produzem exatamente a mesma sequência de jogadas, porque a solução ótima é única. O algoritmo, linha a linha.

Uma função recursiva e três parâmetros: void hanoi(int n, char from, char to, char via) — se n for zero, return; senão chame hanoi(n − 1, from, via, to), imprima a jogada from → to e depois chame hanoi(n − 1, via, to, from). Chame como hanoi(3, 'A', 'C', 'B'). Junte as jogadas num std::vector<std::pair<char, char>> em vez de imprimir, se quem chamou precisar delas, e mantenha n como um int comum: com um parâmetro sem sinal, uma contagem negativa passada por engano vira uns quatro bilhões sem aviso, e a recursão roda até estourar a pilha em vez de falhar numa checagem simples de n &lt; 0. O programa completo em C++, explicado linha a linha.

São dois usos diferentes de pilha, e vale a pena não misturá-los. As hastes são pilhas: cada torre é último a entrar, primeiro a sair, você só toca no disco do topo, e uma jogada é um pop de uma torre e um push em outra — por isso a checagem da regra é uma única comparação com o topo do destino. Separadamente, uma pilha explícita pode substituir a recursão: empilhe o trabalho inteiro (n, from, to, via) e então repita: desempilhe um trabalho e, se ele ainda tiver discos, empilhe suas três partes na ordem inversa: a segunda transferência, a jogada única do disco n e a primeira transferência. A ordem inversa importa porque uma pilha devolve primeiro o último que entrou. É exatamente isso que o runtime da linguagem faz por você na versão recursiva. A solução sem recursão nenhuma.

Em IA o quebra-cabeça é um problema de busca, não uma fórmula. Cada estado é uma atribuição de cada disco a uma haste, então existem 3ⁿ deles, e as jogadas válidas são as arestas entre eles; uma busca — em largura, A* ou IDA* com uma heurística como o número de discos ainda fora da haste de destino — encontra o caminho mais curto do estado inicial ao objetivo. É um problema de teste padrão desde o General Problem Solver de Newell, Shaw e Simon, porque é um exemplo limpo de análise meios-fins e de decomposição de objetivos: o subobjetivo “mover o disco maior” só é alcançado satisfazendo antes um subobjetivo que parece desfazer o progresso. Repare: o algoritmo recursivo não é busca — ele é a solução conhecida, e nunca explora um estado que não vá usar. O mesmo quebra-cabeça como tarefa psicológica.