Problema do cavalo
Neste artigo iremos mergulhar no fascinante mundo de Problema do cavalo, explorando suas origens, evolução e relevância na sociedade atual. Desde as suas primeiras aparições até ao impacto que tem hoje, Problema do cavalo tem desempenhado um papel fundamental em vários aspectos da vida quotidiana das pessoas. Ao longo das próximas linhas analisaremos em profundidade os diferentes ângulos a partir dos quais podemos abordar Problema do cavalo, com o objetivo de esclarecer sua importância e influência na sociedade. Junte-se a nós nesta jornada para descobrir tudo o que você precisa saber sobre Problema do cavalo.
O problema do cavalo, ou passeio do cavalo, é um problema matemático envolvendo o movimento da peça do cavalo no tabuleiro de xadrez. O cavalo é colocado no tabuleiro vazio e, seguindo as regras do jogo, precisa passar por todas as casas exatamente uma vez em movimentos consecutivos. Existem diversas soluções para o problema, dentre elas 26.534.728.821.064 terminam numa casa onde ele ataca a casa na qual iniciou o seu movimento. Esses caminhos são chamados de fechados, pois com mais um movimento o cavalo volta para a posição inicial, formando assim um ciclo. Quando o cavalo termina em uma posição em que não é possível retornar à casa inicial o caminho é dito aberto. Uma determinada solução fechada pode ser realizada iniciando-se de qualquer casa do tabuleiro, o que não é o caso de uma solução aberta.
O problema aparece no quinto livro de Wilson, Lucas escrito por volta do Séc. XVI que contém uma seção sobre o Xadrez. Em manuscritos árabes antigos, o problema era restringido a metade do tabuleiro. Existem algumas soluções com um refinamento matemático no qual ao somar os algarismos das ordens dos movimentos nas colunas e fileiras o resultado é 260, sendo este tipo de solução proposto inicialmente por Carl Jaenisch em 1862. O exercício tem pouco a ver com o xadrez e existe a possibilidade do problema anteceder o jogo e o movimento do cavalo ter sido retirado do problema. Durante séculos muitas variações desse problema foram estudadas por matemáticos, incluindo Euler que em 1759 foi o primeiro a estudar cientificamente esse problema. As variações do problema são:
- tamanhos diferentes de tabuleiro;
- o número de jogadores;
- a maneira com que o cavalo se move.
-
Uma das soluções abertas, onde a casa inicial é diferente da final. -
A solução fechada do problema do cavalo encontrada por O Turco, um autômato de jogar xadrez. -
Solução com refinamento matématico onde a soma das colunas e fileiras é 260..
.png)
O problema pode ser resolvido com uma implementação de uma árvore genérica que irá reproduzir o maior número de soluções possíveis. Porém, é necessário à implementação de uma heurística, que irá calcular o nó mais propenso para que a busca pelo caminho completo seja realizada. O algoritmo abaixo demonstra milhares de soluções para diferentes coordenadas em um tabuleiro 8 x 8. Árvores genéricas são uma boa solução quando se quer resolver um problema com a força bruta.[carece de fontes]
Outras utilizações incluem a criptografia no qual foi proposta sua utilização como um padrão de preenchimento dos dados em um retângulo de ouro de Fibonacci. A quantidade de caracteres a ser criptografada gera números de uma sequência Fibonacci que é empregado para definir o ponto de partida no retângulo de Fibonacci do qual o padrão de movimentação do cavalo será aplicado. A segurança do método é garantida por um padrão diferente para cada quantidade de caracteres empregada do qual o método de força bruta não é vantajoso para quebrar a chave criptográfica.
Ver também
Referências
- ↑ a b Sunnucks (1976), p.263-264
- ↑ Hooper (1992), p.204
- ↑ VAIDYANATHAN, Prashant (2012). «A new encryption technique for the secured transmission and storage of text information with medical images» 1 ed. Engineering Review. 32: 57-63
Bibliografia
- HOOPER, David & WHYLD, Kenneth (1992). The Oxford Companion to Chess (em inglês) 2ª ed. Inglaterra: Oxford University Press. ISBN 0-19-866164-9
- SUNNUCKS, Anne (1976). The Encyclopaedia of Chess (em inglês) 2ª ed. Inglaterra: St Martin Press. ISBN 0709146973