Atps

CENTRO UNIVERSITÁRIO ANHANGUERA
CIÊNCIA DA COMPUTAÇÃO
LINGUAGENS FORMAIS E AUTÔMATOS

ATIVIDADES PRÁTICAS SUPERVISIONADAS
ESTUDO SOBRE O PASSEIO DO CAVALO

Paulo William Alves Ferreira
Leme, 11 de Abril de 2013.
O Passeio do Cavalo
Capítulo 1: Descrição do problema
Conhecido desde séculos antes de Cristo, o xadrez é um jogo de tabuleiros muito conhecido e difundido. Disputado sobre um tabuleiro de 64 casas sobre o qual se dispõem 16 peças para cada um dos dois jogadores, o xadrez apresenta um grande leque de possibilidades graças à variedade de peças e opções de movimentação que cada uma delas apresenta. Tais combinações (de posição, possibilidades de jogadas, disposição das peças, entre outros) tem sido objeto de estudos desde o século XV, quando o jogo já estava amplamente difundido pela Europa.
Com o advento da computação a partir da década de 1950, houve um crescimento no interesse de se implementar soluções computacionais para os diversos problemas matemáticos propostos a partir do xadrez. Programas que simulassem partidas, programas que fossem capazes de jogar contra humanos, servidores para permitir partidas remotas entre duas pessoas, e verificação da eficiência da inteligência artificial aplicada.
Um famoso problema apresentado é conhecido como “passeio do cavalo”: dada uma casa qualquer do xadrez, seguindo as regras tradicionais de movimentação da peça cavalo, busca-se visitar todas as casas do tabuleiro, de forma que, concluído o passeio, todas tenham sido passadas, e que o cavalo nunca passe mais de uma única vez pela mesma casa. Sua solução consiste da busca por uma solução computacional idealizada (independente de máquina ou software, que se atenha tão-somente a conceitos teóricos computacionais e de linguagem algorítmica) que permita analisar determinada entrada de dados e concluir se tal entrada pode ser uma solução válida para o problema do passeio do cavalo.
Introduzido o problema, no decorrer deste trabalho iremos expor o