ATPS Passeio Do Cavalo

Capítulo 1 – Descrição do Problema.

O jogo de Xadrez é um ótimo exercício mental, pois usa muito o raciocínio lógico, com regras universais, entretanto em qualquer lugar do mundo que se jogar esse jogo terão as mesmas regras.

Conforme pesquisa feita as características de arte e ciência são encontradas nas composições enxadrísticas e em sua teoria que abrange aberturas, meio-jogo e finais, as fases em que subdividem o transcorrer do jogo, precisa ter concentração para

analisar em volta da peça que vai movimentar e nas possibilidades que podem acontecer, conforme a decisão tomada e a peça movimentada, por ser um jogo de estratégia e tática, não envolve o elemento sorte. A única exceção, nesse caso, é o sorteio das cores no início do jogo, já que as brancas sempre fazem o primeiro movimento e teriam, em tese, uma pequena vantagem por isso. Teoria essa suportada por um grande número de estatísticas, embora alguns especialistas não aceitem a existência de tal vantagem, depende do movimento que é feito.

A partida de xadrez é disputada em um tabuleiro de casas claras e escuras, sendo que, no início, cada enxadrista controla dezesseis peças com diferentes formatos e características. O objetivo da partida é dar xeque-mate (também chamado de mate) no adversário. Teóricos do enxadrismo desenvolveram uma grande variedade de estratégias e táticas para se atingir este objetivo, muito embora, na prática, ele não seja um fato muito comum, já que os jogadores em grande desvantagem ou iminência de derrota têm a opção de abandonar (desistir) a partida, antes de receberem o mate.

Cada casa do tabuleiro recebe um endereço que é formado pela letra de sua coluna e o numero de sua linha.

As oitos linhas do tabuleiro são numeradas de 1 á 8, das brancas para as pretas.

As oitos colunas recebem letras minúsculas que vão de a á h, da esquerda para a direita em relação à posição das brancas.

As peças recebem letras maiúsculas:

Rei = R;

Dama = D;

Torre = T;

Bispo = B;

Cavalo = C;

Peão = A inicial P não é utilizada. A notação do peão é caracterizada pela ausência da letra P, já que os peões podem avançar apenas para frente.

ER= (C*(l+k+k)* (l+l+k)*)

G=({C}, {k}, {(k) (l)}, {S})

C= é o cavalo;

k= são as colunas que são representadas delas as letras a|b|c|d|e|f|g|h;

l= são as linhas que são representadas por números de 1|2|3|4|5|6|7|8;

S= é a produção inicial.

O Passeio do Cavalo

O Passeio do Cavalo em um tabuleiro de xadrez (ou qualquer outro tabuleiro) consiste de uma seqüência de movimentos feitos pela peça de xadrez correspondente ao cavalo, de tal maneira que cada casa do tabuleiro seja visitada exatamente uma única vez. Cada movimento da peça é descrito como um "L": consiste de dois avanços em relação a um dos eixos (linha ou coluna) e um avanço em relação ao outro eixo.

O Problema do Passeio do Cavalo pode ser definido da seguinte forma:

Dado um tabuleiro l x k qualquer, determine uma seqüência legal de movimentos do cavalo de modo que esta peça passe por todas as casas uma única vez, a partir de qualquer casa do tabuleiro.

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

O movimento é o deslocamento de uma peça localizada em uma casa para outra.

Tem o movimento da captura de uma peça para uma casa já ocupada pelo adversário, neste caso, tira-se a peça adversária, e coloca-se a própria peça em seu lugar. A captura é opcional.

Cada peça do xadrez obedece a uma regra diferente.

No xadrez também tem movimentos especiais como:

Roque é o único lance que envolve o movimento de duas peças ao mesmo tempo: rei e torre. O roque tem como objetivo colocar o rei em maior segurança e uma das torres em posição mais ativa. Há dois tipos de roque: roque pequeno e roque grande.

No roque, pequeno ou grande, o rei sempre se move duas casas na direção de uma das torres; completando o movimento, a torre salta sobre o rei e passa a ocupar a casa ao seu lado.

O roque não é permitido se:

• o rei ou a torre já tiverem sido movimentados;

• o rei estiver em xeque;

• o rei ficar em xeque ao final do movimento;

• o rei passar por uma casa dominada por peça adversária;

• houver