O Cavalo Xadrez

FACULDADE FAC3 ANHANGUERA EDUCACIONAL

CIÊNCIAS DA COMPUTAÇÃO

LINGUAGENS FORMA E AUTOMÂTOS

O PASSEIO DO CAVALO

ROGER JESUS QUINTINO

R.A. 2565472434

PROFESSORA

REGINA FEDOZZI

CAMPINAS

2014

SUMÁRIO

1 DESAFIO 7

2 OBJETIVO DO DESAFIO 10

3 INTRODUÇÃO 10

3.1 XADREZ 13

3.2 REGRAS 14

3.3 PEÇAS 17

3.4 MOVIMENTO DAS PEÇAS 21

3.5 NOTAÇÃO ENXADRÍSTICA 21

3.6 SISTEMA ALGÉBRICO 21

3.7 SISTEMA DESCRITIVO 21

3.8 SÍMBOLOS ESPECIAIS 23

4 CAPÍTULO 1 25

4.1 DESCRIÇÃO DO PROBLEMA 25

5 CAPÍTULO 2 25

5.1 DESCRIÇÃO TEXTUAL DOS MOVIMENTOS DO XADREZ 25

6 CAPÍTULO 3 25

6.1 RECONHECIMENTO DA ENTRADA 25

DESAFIO

O Xadrez é um jogo estratégico de tabuleiro para dois jogadores. O jogo é disputado em um tabuleiro de 64 casas (8x8) alternadas entre claras e escuras. Cada jogador inicia a partida com 16 peças, sendo: 1 rei, 1 rainha, 2 bispos, 2 cavalos, 2 torres e 8 peões. O objetivo da partida é capturar o rei inimigo. Para isso, um dos jogadores deve posicionar suas peças no tabuleiro de forma que, na próxima jogada, ele consiga mover uma das peças para a casa ocupada pelo rei inimigo, considerando o movimento particular de cada peça.

Além do seu valor estratégico e lúdico, o xadrez também se mostra muito importante no ponto de vista matemático e computacional. Diversos problemas de natureza combinatória e topológica ligado ao xadrez são conhecidos, foram estudados nas últimas centenas de anos e, mais recentemente, suas soluções foram aplicadas para resolução de vários problemas computacionais. Esses problemas são chamados de composições. Em uma composição o problema é apresentado por meio da definição de uma distribuição de peças no tabuleiro e a solução consiste em realizar uma ação determinada. É comum que a ação a ser realizada venha acompanhada de uma ou mais restrições.

Existem diversas composições clássicas no xadrez. Uma delas é conhecida como o passeio do cavalo. Nessa composição o desafio é fazer com que o cavalo passe por todas as casas do tabuleiro. Inicialmente o cavalo está em uma casa qualquer e ele deve ser movimentado obedecendo às regras de movimentação para essa peça.

Este desafio consiste em elaborar uma solução computacional, utilizando os conceitos de Linguagens Formais e Autômatos, para verificar se uma sequência de movimentações é uma solução para a composição do passeio do cavalo. Para tanto o aluno é convidado a elaborar os formalismos geradores (expressões regulares e gramáticas) e reconhecedores (máquinas de estados finitos) necessários para verificar se a sequência corresponde a uma representação textual correta de movimentos da peça; se a sequência de movimentos é válida e, por fim, se todas as casas do tabuleiro foram visitadas.

OBJETIVO DO DESAFIO

Elaborar uma solução computacional, utilizando os conceitos de Linguagens Formais e

Autômatos, para verificar se uma sequência de movimentações é uma solução para a composição do passeio do cavalo.

INTRODUÇÃO

XADREZ

Xadrez é um jogo de tabuleiro de natureza recreativa e competitiva para dois jogadores, sendo também conhecido como Xadrez Ocidental ou Xadrez Internacional para distingui-lo dos seus predecessores e de outras variantes da atualidade. A forma atual do jogo surgiu no Sudoeste da Europa na segunda metade do século XV, durante o Renascimento, depois de ter evoluído de suas antigas origens persas e indianas. O Xadrez pertence à mesma família do Xiangqi e do Shogi e, atualmente segundo os historiadores do enxadrismo. (ou xadrezismo), todos eles se originaram do Chaturanga, que se praticava na Índia no século VI d.C.

O xadrez é um dos jogos mais populares do mundo, sendo praticado por milhões de pessoas em torneios (amadores e profissionais), clubes, escolas, pela internet, por correspondência e informalmente. Há uma estimativa de cerca de 605 milhões de pessoas em todo o mundo que sabem jogar xadrez e destas, 7,5 milhões são filiadas a uma das federações nacionais que existem em 160 países em todo o mundo.

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.

REGRAS

Durante uma partida de xadrez, cada enxadrista controla dezesseis peças que podem ser de cor clara ou escura (normalmente brancas e negras), sendo que as brancas devem sempre fazer o primeiro lance. São necessários um tabuleiro com oito fileiras e oito colunas composto por sessenta R quatro casas (sendo metade claras e metade escuras, alternadamente) e um relógio de xadrez que é opcional para disputas