O passeio do cavalo
Um passeio do cavalo é uma sequência de movimentos de cavalo que visita todas as casas de um tabuleiro de xadrez exatamente uma vez. É um dos quebra-cabeças mais antigos da matemática recreativa: um passeio por meio tabuleiro aparece num poema indiano do século IX, e Leonhard Euler estudou o problema em 1759.
Um quebra-cabeça antigo
No Kavyalankara, escrito pelo poeta indiano Rudrata no século IX, um verso é disposto sobre meio tabuleiro de xadrez de modo que pode ser lido seguindo o caminho de um cavalo. Leonhard Euler escreveu o primeiro estudo matemático do passeio do cavalo em 1759, com maneiras de construir passeios e de transformá-los em passeios fechados.
Um caminho por um grafo
Pense em cada casa como um ponto e em cada movimento de cavalo como uma linha entre dois pontos. Um passeio do cavalo é então um caminho que visita cada ponto exatamente uma vez, o que os matemáticos chamam de caminho hamiltoniano; um passeio fechado é um ciclo hamiltoniano. Na maioria das redes, um caminho assim é muito difícil de encontrar. A rede do cavalo é generosa: tem tantos passeios que uma boa regra encontra um rapidamente.
A regra de Warnsdorff
H. C. von Warnsdorff descreveu sua regra em 1823: salte sempre para a casa que deixa menos movimentos seguintes. As casas ao longo da borda têm poucas vizinhas, então a regra as visita cedo em vez de deixá-las isoladas. Quando duas casas empatam, é preciso escolher, e uma escolha infeliz ainda pode deixar o cavalo preso. No aplicativo, os números dourados marcam as casas que a regra escolheria.
Busca com retrocesso
Resolver segue a ordem de Warnsdorff, mas não confia nela cegamente. Ele faz uma busca em profundidade e, assim que uma casa não visitada não pode mais ser alcançada, abandona esse ramo e tenta o próximo movimento. Em tabuleiros de até 10×10, ele costuma encontrar um passeio na hora. Quando o seu próprio caminho encurralou o cavalo, ele primeiro volta alguns movimentos.
Cores e passeios fechados
Cada movimento de cavalo muda a cor da casa. Num tabuleiro ímpar como o 5×5, há uma casa a mais da cor dos cantos do que da outra cor, então um passeio precisa começar e terminar na cor dos cantos. Ali um passeio fechado é impossível, porque um circuito que alterna as cores tem tantas casas de uma cor quanto da outra. Em tabuleiros pares, existem passeios fechados a partir de 6×6.
Experimente no PictorX
Abra o Passeio do cavalo e clique numa casa para começar. As casas destacadas são os saltos válidos, o número dourado é a escolha de Warnsdorff, e o tabuleiro guarda a ordem dos seus movimentos. Tamanho define o tabuleiro de 5×5 a 10×10, “Passeio fechado” pede a Resolver um circuito, e Desfazer anula qualquer movimento. Salve o caminho pronto como PNG.
Perguntas frequentes
Quem estudou primeiro o passeio do cavalo?
Os passeios já eram conhecidos muito antes de alguém estudá-los matematicamente. Leonhard Euler escreveu o primeiro tratamento matemático em 1759, e Warnsdorff apresentou sua regra em 1823.
Existe um passeio em todo tabuleiro?
Tabuleiros quadrados a partir de 5×5 têm passeios abertos, e os pares a partir de 6×6 também têm passeios fechados. Tabuleiros de 2×2, 3×3 e 4×4 não têm nenhum passeio.
Quantos passeios tem um tabuleiro de xadrez?
Há 26.534.728.821.064 passeios fechados se um passeio e o mesmo passeio percorrido ao contrário contarem separadamente. O número de passeios abertos é de cerca de 19,6 quatrilhões.
O PictorX envia alguma coisa?
Não. O tabuleiro é desenhado numa tela no seu navegador. Salvar baixa um PNG, e Editar abre essa imagem no editor do PictorX.
Ferramentas relacionadas
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.
O problema das oito damas
A história e a matemática do problema das oito damas: Max Bezzel e Gauss, as 92 soluções em 12 famílias, o problema das n damas e o backtracking.
Torre de Hanói
Mova uma torre de discos entre três hastes no seu navegador. Um disco de cada vez, nunca um maior sobre um menor. A solução mais curta tem 2ⁿ − 1 movimentos.
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.
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.
Experimentar o Passeio do cavalo