ATPS Linguagens Formais e Autômatos: O Passeio do Cavalo

[pic 1]

ATPS Linguagens Formais e Autômatos

O Passeio do Cavalo

Etapas 1 e 2

Eduardo Augusto Silva de Sousa ----------------------- 6814008489                                Eduardo Alves Carvalho ---------------------------------- 6814008488                                                                   Filippe Gonçalves Marchezoni -------------------------- 6814008494                                              Marcelo Pereira de Oliveira ----------------------------- 6659396024

Ciência da Computação – 7° semestre

Faculdade Anhanguera SJC Campus II

São José dos Campos, 05 de março de 2016

O PASSEIO DO CAVALO

1. Descrição do Problema.

O 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 precisa passar por todas as casas exatamente uma vez em movimentos consecutivos.

Existem várias soluções para esse problema. Uma delas consiste em dividir o tabuleiro em quatro partes iguais e andar com o cavalo quatro casas em cada quadrado por vez, até completar o desafio, formando um padrão simétrico com seu desenho.

[pic 2]

Outra solução consiste em numerar cada jogada do cavalo com números de 1 a 64, consecutivamente, e ordená-los no tabuleiro de modo que a soma de qualquer linha ou coluna resulte em 260. Note que, se dividirmos o tabuleiro em quatro partes. A soma de qualquer linha ou coluna de cada parte resulta em 130.

[pic 3]

1. Descrição Textual dos Movimentos do Xadrez.

A posição do cavalo, assim como de qualquer outra peça é dada por suas coordenadas no tabuleiro como num plano cartesiano, onde o eixo x é representado por letras minúsculas de ‘a’ até ‘h’ e o eixo y é representado por números, de 1 a 8.

Cada uma das peças é indicada pela inicial maiúscula (para não confundir com as letras minúsculas indicativas de colunas) de seu próprio nome: Cavalo, Bispo, Torre, Dama e Rei. Os peões não são indicados. Assim indica-se uma jogada: primeiro escreve-se a letra que representa a peça jogada, depois a coordenada da casa na qual ela foi colocada, coluna e linha, nesta ordem.

A notação descritiva dá a cada casa um nome e as peças recebem o nome de suas iniciais, incluindo o peão. As fileiras são numeradas a partir de cada jogador. Difere da notação algébrica porque nesta existia uma única ordem numérica (a partir das brancas). O nome da coluna e o número da fila indicam a casa para a qual a peça se moveu, sendo o lance das brancas designado numericamente do lado das brancas e o das pretas, da mesma forma, como já foi explicado anteriormente. A grande diferença entre a notação algébrica e a descritiva é que algébrica, cada casa tem seu nome, e isso nunca muda, entretanto, na descritiva, para as brancas a casa tem um nome e para as negras ela tem outro. Na notação descritiva também só se escreve com letra maiúscula, ao contrário da notação algébrica.

Há vários símbolos especiais utilizados para a notação das partidas são os seguintes, conforme tabela abaixo:

[pic 4]

O Cavalo é a única peça do xadrez que pode saltar sobre outras peças. Ele se movimenta em formato de um "L": duas casas em uma direção (vertical ou horizontal) e uma na outra.

Formalmente, para que uma jogada do cavalo seja válida ele deve se deslocar duas casas no eixo horizontal x e uma no eixo vertical y, ou uma no eixo x e duas no eixo y. Ou seja:

(∆x = |2| && ∆y = |1|) || (∆x = |1| && ∆y = |2|), onde ∆x é a variação no eixo x em relação à posição anterior, que pode ser positiva ou negativa, e por isso está entre dois símbolos ‘|’, porque não importa para que sentido.