Passeio Do Cavalo

ATIVIDADES PRÁTICAS SUPERVISIONADAS

Ciência da Computação

7ª Série

O PASSEIO DO CAVALO

Linguagens Formais e Autômatos

Marcos Geronimo da Silva

RA: 1041986619

O PASSEIO DO CAVALO

Introdução

Movimento do cavalo

O movimento do cavalo é em forma de um L. O movimento é composto de um salto de duas casas numa linha ou coluna e em seguida num movimento de uma casa para a coluna ou linha contigua, respectivamente. Note: a casa final de um movimento de cavalo é uma casa de cor diferente da casa de saída. Note também que um cavalo ataca, no máximo, oito casas do tabuleiro. A única restrição que impede um cavalo de ocupar uma casa em seu raio de ação, é o fato de lá estar uma peça da mesma cor do cavalo.

Cap. 1 – Descrição do Problema.

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 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 é 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.

Cap. 2 – Descrição Textual dos Movimentos do Xadrez.

O Cavalo é a única peça do xadrez que pode saltar sobre outras peças. Ele tem um movimento bem peculiar em formato de "L": duas casas no sentido vertical ou horizontal e uma casa no outro sentido. No esquema que se segue estão apresentadas todas as possibilidades de jogada do cavalo (indicado pelos pontos em azul) a partir da posição onde ele está.

Uma sequência de movimentos do cavalo é apresentada na figura acima:

A posição do cavalo é dada por suas coordenadas cartesianas no tabuleiro, onde o eixo x é representado por letras de ‘a’ até ‘h’ e o eixo y representado por números, de 1 até 8.

Dado uma coordenada (x,y), por exemplo (e,5), as oito casas para onde o cavalo pode ir em um movimento são dadas por:

(y+2, x+1)

(y-2, x+1)

(y+2, x-1)

(y-2, x-1)

(x+2, y+1)

(x+2, y-1)

(x-2, y+1)

(x-2, y-1)

Cap. 3 – Reconhecimento da Entrada.

Neste trabalho usaremos um alfabeto de quatro letras “u, d, l, r”, que são respectivamente, “up, down, left, rigth” representando as direções em que a peça pode se movimentar no tabuleiro, sendo assim cada movimento válido terá uma sequencia de três letras, indicando o trajeto do cavalo.

Dado a posição inicial do cavalo,