Torre de Hanói

O quebra-cabeça da Torre de Hanói: mova a pilha inteira de discos do pino A para outro pino seguindo as regras. Resolva você mesmo ou acompanhe a solução automática e a lista de movimentos, por exemplo em uma aula sobre recursão.

Como usar

1. Escolha o número de “Discos”, de 3 a 10.
2. Arraste o disco de cima para outro pino ou toque em um pino para pegar o disco de cima e toque em outro pino para soltá-lo. As teclas 1, 2 e 3 também funcionam.
3. Pressione “Desfazer” para voltar um movimento ou “Começar de novo” para recomeçar.
4. Se travar, pressione “Mostrar a solução” para vê-la a partir da posição atual. Você pode mudar a “Velocidade” ou pressionar “Pausar” e usar “Um passo”.

Como funciona

• As regras: mova um disco de cada vez, mova só o disco de cima de um pino e nunca coloque um disco maior sobre um menor.
• O menor número possível de movimentos é 2ⁿ − 1 para n discos. Para mover n discos, você move n − 1 discos para o lado, move o maior disco uma vez e depois move os n − 1 discos de volta por cima dele.
• O melhor recorde para cada número de discos fica salvo neste navegador. As partidas em que a solução automática foi usada não são registradas.

Perguntas frequentes

Qual é o número mínimo de movimentos da Torre de Hanói?

Para n discos, é 2ⁿ − 1: 7 movimentos para 3 discos, 15 para 4, 31 para 5 e 1.023 para 10.

Existe um jeito simples de resolver a Torre de Hanói?

Em todo movimento ímpar, mova o menor disco um pino adiante, sempre no mesmo sentido. Em todo movimento par, faça o único movimento permitido que não usa o menor disco.

Por que a Torre de Hanói é usada para ensinar recursão?

A solução para n discos é formada por duas soluções para n − 1 discos mais um movimento do maior disco, então T(n) = 2·T(n − 1) + 1.

Dá para ver todos os movimentos de uma vez?

Abra a “Lista de movimentos da solução” para ver cada movimento no formato “Disco 1: A → C”.