Problema do cavalo

Problema matemático

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.[1] 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.

Uma solução aberta do problema em um tabuleiro 8 x 8.

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.[1] 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.[2] 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.

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.[3]

Ver também

editar

Referências

  1. a b Sunnucks (1976), p.263-264
  2. Hooper (1992), p.204
  3. 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

editar
  • 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