Torre de Hanói
Três hastes e um cone de discos com o maior em baixo. Mova a torre inteira para a haste da direita. Só pode mover um disco de cada vez, e um disco maior nunca pode ficar sobre um menor. A solução mais curta leva 2ⁿ − 1 movimentos: 1, 3, 7, 15, 31, e assim por diante. Mova um disco de cada vez para cima de um disco maior ou de uma haste vazia. A torre inteira deve terminar na haste da direita. A solução mais curta leva 2ⁿ − 1 movimentos. Arraste um disco, ou clique numa haste e depois noutra.
Como funciona
- Abra esta página. Há quatro discos empilhados na haste de partida. Quinze movimentos é o mínimo.
- Arraste o disco de cima para outra haste, ou clique numa haste e depois na que quiser. Um disco maior sobre um menor é recusado.
- Prima Resolver para ver uma solução mais curta, ou avance com Passo. Depois guarde um PNG.
Um disco, e nunca um maior sobre um menor
Um movimento pega no disco de cima de uma haste e coloca-o noutra haste, ou numa haste vazia. É o único tipo de movimento. O disco que coloca tem de ser menor do que aquele onde fica. Com estas regras, os discos de cada haste ficam ordenados, com o maior em baixo.
2ⁿ − 1 movimentos, e nem menos
Para mudar n discos, primeiro afasta os n − 1 discos que estão sobre o maior, move o maior uma vez e depois passa os n − 1 discos para cima dele. Se n − 1 discos levam T movimentos, n discos levam 2T + 1. Isso dá 2ⁿ − 1: 1, 3, 7, 15, 31. Oito discos, a torre mais alta aqui, levam 255 movimentos.
O mesmo quebra-cabeças, com um disco a menos
Mova os n − 1 discos de cima para a haste auxiliar. Mova o disco maior para o destino. Mova os n − 1 discos da haste auxiliar para o destino. Cada uma dessas tarefas menores é de novo o mesmo quebra-cabeças. Passo e Resolver reproduzem um caminho mais curto. A partir de uma torre perfeita, é esta recursão. A partir de um tabuleiro baralhado, continua a ser um caminho mais curto, encontrado procurando entre as posições válidas.
Perguntas frequentes
Quais são as regras da Torre de Hanói?
Mova um disco de cada vez. Pegue no disco de cima de uma haste e coloque-o noutra haste. Nunca ponha um disco maior sobre um menor.
Quantos movimentos leva a solução mais curta?
2ⁿ − 1. Um disco é 1 movimento, dois discos são 3, três são 7, quatro são 15 e cinco são 31.
Quem inventou a Torre de Hanói?
Édouard Lucas apresentou o quebra-cabeças em 1883. A história dos sacerdotes que movem 64 discos de ouro é a lenda que ele contava com o jogo.
Posso ver a solução?
Sim. Passo reproduz um movimento de uma solução mais curta. Resolver reproduz o resto. «Ver 3 discos» executa a estratégia recursiva clássica desde o início.
Ferramentas relacionadas
Torre de Hanói
A Torre de Hanói: três hastes, um disco de cada vez e nunca um maior sobre um menor. A solução mais curta tem 2ⁿ−1 movimentos. Édouard Lucas apresentou o quebra-cabeças em 1883.
Passeio do cavalo
Faça um cavalo de xadrez saltar por todas as casas do tabuleiro exatamente uma vez. Jogue você mesmo com as dicas de Warnsdorff ou veja Resolver terminar um passeio aberto ou fechado. Salve o caminho como PNG.
Oito damas
Coloque oito damas em um tabuleiro de xadrez sem que nenhuma ataque outra. Tente você mesmo, veja a busca com backtracking encontrar uma solução passo a passo e percorra todas as 92 soluções.
Jogo do 15
Jogue o clássico jogo do 15, o quebra-cabeça deslizante, no seu navegador, com peças de madeira em 3×3, 4×4 ou 5×5. Embaralhe, deslize linhas inteiras de uma vez, tente o impossível 14-15 de Sam Loyd ou veja Resolver terminar o jogo.
Agulha de Buffon
Deixe cair agulhas num chão com riscas no seu navegador. Conte os cruzamentos e veja a experiência de Buffon de 1777 estimar π.
Círculos de multiplicação
Ligue cada número de um círculo ao seu múltiplo. Desenhe uma tabuada, uma cardioide ou uma figura de fio em papel, a giz ou em madeira.
A conjetura de Collatz
Explore o problema de Collatz 3n+1 no seu navegador. Percorra sequências de granizo, faça crescer uma árvore de Collatz geométrica e aproxime o fractal de Collatz contínuo.
Formiga de Langton
Execute a formiga de Langton no navegador. Veja a simetria, o caos e a autoestrada de 104 passos e depois experimente regras multicoloridas, várias formigas, uma grelha hexagonal e turmites.
Pronto para experimentar?
Abra o PictorX em seu navegador – sem instalação, sem necessidade de cartão de crédito para iniciar.
Ir para o editor