Resolver
Solucionador da Torre de Hanói
A solução mais curta para qualquer posição válida, não só para uma pilha completa. Monte o tabuleiro como ele está de verdade e veja o caminho ótimo ser jogado.
Solução ótima
31jogadas25 − 1 = 31
O quebra-cabeça clássico: todos os discos começam na torre A e terminam na torre C.
Pronto para reproduzirPasso 0 de 31
←→passoEspaçoreproduzirHomeEndpular
Todas as jogadas, em ordem
O disco 1 é o menor, e A → C significa: tire o disco de cima da torre A e coloque-o na torre C. Selecione qualquer linha para levar o tabuleiro até essa jogada.
A jogada 16 é o disco 5 passando de A para C. As 15 jogadas de cada lado são a mesma solução duas vezes: a solução de 4 discos, jogada primeiro para a torre auxiliar e depois a partir dela.
| # | Disco | De | Para |
|---|---|---|---|
| 1 | 1 | A | C |
| 2 | 2 | A | B |
| 3 | 1 | C | B |
| 4 | 3 | A | C |
| 5 | 1 | B | A |
| 6 | 2 | B | C |
| 7 | 1 | A | C |
| 8 | 4 | A | B |
| 9 | 1 | C | B |
| 10 | 2 | C | A |
| 11 | 1 | B | A |
| 12 | 3 | C | B |
| 13 | 1 | A | C |
| 14 | 2 | A | B |
| 15 | 1 | C | B |
| 16 | 5 | A | C |
| 17 | 1 | B | A |
| 18 | 2 | B | C |
| 19 | 1 | A | C |
| 20 | 3 | B | A |
| 21 | 1 | C | B |
| 22 | 2 | C | A |
| 23 | 1 | B | A |
| 24 | 4 | B | C |
| 25 | 1 | A | C |
| 26 | 2 | A | B |
| 27 | 1 | C | B |
| 28 | 3 | A | C |
| 29 | 1 | B | A |
| 30 | 2 | B | C |
| 31 | 1 | A | C |
Nesta página
Como o solucionador funciona
O método é a própria lógica do quebra-cabeça, executada para a frente. Para assentar o maior disco na torre de destino, todos os discos menores precisam estar em outro lugar — mais precisamente, empilhados na única torre que sobra. Então o solucionador primeiro pede que essa pilha menor vá para lá, passa o disco grande e depois pede que a pilha menor volte por cima dele. Cada um desses pedidos é o mesmo problema com um disco a menos, até chegar a um único disco, que se move em um passo.
O que separa este solucionador dos que só lidam com uma pilha completa é uma linha a mais de raciocínio: se o maior disco já está no destino, não há nada a fazer com ele, e o problema inteiro encolhe para os discos que estão acima. Esse único caso é o que permite resolver a partir de um tabuleiro pela metade em vez de obrigar você a recomeçar — e é por isso que as contagens a partir de uma posição personalizada são menores que 2ⁿ − 1, muitas vezes bem menores numa partida já começada.
Mova os n−1 discos de cima para a torre auxiliar. Nada mais pode acontecer enquanto eles estiverem no caminho.
O maior disco agora está livre, e o destino dele está vazio. Ele passa em uma única jogada — a única de que esta fase precisa.
Reconstrua 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.
Ler uma solução
Cada linha nomeia uma jogada: qual disco, de que torre ele sai e em qual ele pousa. O disco 1 é o menor. Você nunca precisa conferir se a jogada é válida — por construção, toda jogada da lista já é.
A partir de uma pilha completa, dois padrões aparecem de imediato:
- O menor disco se move a cada duas jogadas — as jogadas 1, 3, 5 e assim por diante — e sempre percorre as três torres no mesmo sentido.
- Cada jogada intermediária é a única jogada válida que não toca no menor disco.
Esse é o método iterativo inteiro, e dá para lê-lo direto em qualquer solução que parta de uma pilha completa. A partir de uma posição personalizada a lista continua sendo a mais curta, mas é costurada com transferências menores, então o menor disco pode mudar de sentido no meio do caminho. A solução iterativa mostra por que o método funciona, e o guia de estratégias transforma isso em algo para jogar. Para a recursão em si, seguida linha a linha em seis linguagens, veja o algoritmo da Torre de Hanói.
Os tamanhos mais comuns também têm uma página cada, com todas as jogadas e o que é particular daquele tamanho: soluções de 3 a 10 discos e os 64 discos da lenda.
Levar uma solução com você
A barra de endereços sempre descreve o tabuleiro na tela. Uma transferência completa aparece como ?disks=5&from=A&to=C; uma posição personalizada acrescenta um código como pos=CBBAA, uma letra por disco começando pelo menor. Copie esse link e ele reabre exatamente neste quebra-cabeça — que é também como se envia a alguém a posição em que você travou, em vez de uma descrição dela.
A própria lista de jogadas vai para a área de transferência, ou é baixada como arquivo de texto para ler ao lado de um quebra-cabeça físico e como CSV para abrir numa planilha. O download não tem o limite da tabela impressa: com quinze discos, o arquivo ainda guarda as 32.767 jogadas.
Por que a lista para em 12 discos
As soluções dobram a cada disco. Doze discos são 4.095 jogadas, uma tabela longa mas utilizável. Treze são 8.191, vinte são 1.048.575, e nenhum navegador transforma uma tabela de um milhão de linhas em algo que uma pessoa consiga usar. Acima de doze discos esta página dá a contagem exata e mantém o tabuleiro animado — e os downloads acima continuam contendo todas as jogadas, então a solução continua sendo sua; ela só não é impressa. Se o que você quer são apenas os números, a calculadora vai até sessenta e quatro discos e além.
Perguntas frequentes
O que o solucionador da Torre de Hanói faz?
Ele imprime a menor sequência de jogadas possível que reúne todos os discos em uma torre. Dê a ele um número de discos e ele resolve a transferência completa clássica; dê uma posição pela metade e ele resolve a partir dali, que é justamente o que a maioria dos solucionadores não faz.
A solução é a mais curta?
Sim. O solucionador é comprovadamente ótimo, não apenas correto: a partir de uma pilha inicial completa ele produz exatamente 2ⁿ − 1 jogadas, e de qualquer outra posição válida produz o verdadeiro caminho mais curto até o objetivo. Não existe sequência com menos jogadas.
Ele resolve a partir de uma posição que já comecei?
Sim — é para isso que serve a posição inicial personalizada. Coloque cada disco na torre em que ele está agora e o solucionador termina o serviço no menor número de jogadas possível a partir dali, em geral muito menos do que recomeçar.
Posso compartilhar ou salvar uma solução?
Sim. A barra de endereços sempre guarda o tabuleiro que você está vendo: /pt/solver/?disks=5&from=A&to=C é uma transferência completa de cinco discos, e uma posição personalizada acrescenta um código como pos=CBBAA, uma letra por disco começando pelo menor. Copie o link e ele reabre exatamente nesse quebra-cabeça.
Posso baixar a lista de jogadas?
Sim, como arquivo .txt simples ou como .csv com uma linha por jogada, ao lado do botão de copiar. O download funciona até para as soluções muito longas que a página não imprime como tabela, então uma resposta de 15 discos também é sua.
Como leio a lista de jogadas?
Cada linha nomeia uma jogada: o número do disco, a torre de onde ele sai e a torre onde ele pousa. O disco 1 é o menor. Jogue na ordem e o quebra-cabeça se resolve sozinho; você nunca precisa pensar em qual disco é válido, porque toda jogada listada já é.
Por que a lista de jogadas para em 12 discos?
Uma solução de 12 discos tem 4.095 jogadas. Com 20 discos seriam 1.048.575 linhas, que nenhum navegador exibe de forma útil — então, acima de 12 discos, a página dá a contagem exata e a fórmula no lugar da lista, e o tabuleiro animado continua reproduzindo a solução.