Friday, December 24, 2010

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. Existem diversas soluções para o problema, dentre elas 26.534.728.821.064 terminam numa casa da qual 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 é posível retonar à 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.
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.

No comments: