Xadrez

SUMÁRIO

1. Desafio.................................................................................................................................................2

1.1. Objetivo Do Desafio 3

2. Etapa 1 4

2.1. Capitulo 1 - Descrição Do Problema 4

2.2. Capitulo 2 - Descrição Textual Dos Movimentos Do Xadrez 5

2.2. Capitulo 2 - Descrição Textual Dos Movimentos Do Xadrez...................................6

3. Fontes. 7

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

Movimento do Cavalo (fonte UOL) 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 é valida e, por fim, se todas as casas do tabuleiro foram visitadas.

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

2. Etapa 1

Aula-tema: Introdução aos principais critérios de avaliação das linguagens de programação: legibilidade. Critérios de avaliação das linguagens de programação: capacidade de escrita. Critérios de avaliação das linguagens de programação: confiabilidade.

"Passeio Do Cavalo"

2.1 Capitulo 1 - Descrição Do Problema

Este Trabalho tem como objetivo elaborar uma solução computacional utilizando os conceitos de Linguagens Formais e Autômatos, vamos usar um dos jogos mais estratégicos e matemático mundialmente conhecido o Xadrez, a solução basicamente se consiste em realizar uma determinada movimentação baseado nas suas regras para cada uma das situações propostas, mas existem varias composições clássicas.

Como exemplo temos algumas categorias:

• Direitos: Problema tradicional onde as brancas buscam o mate e as pretas tentam se defender a qualquer custo.

• Ajudados: As Pretas ajudam as brancas a darem mate. Sendo assim aparenta ser fácil a resolução, mas não é verdade.

• Retroanálise: São classes especiais de problemas onde a legalidade da posição é fundamental para a solução.

• Inversos: Neste caso as brancas obrigam as pretas a lhes darem mate.

Neste desafio vamos usar o "Passeio Do Cavalo" independente onde esteja e claro obedecendo sua regras de movimentação passe

...