ATPS Liguagem Formais e Automatos

FACULDADE ANHANGUERA DE CASCAVEL

ATPS de Liguagens Formais e Automatos

Relatório desenvolvido pelo acadêmico:
Luiz Henrique Homenhuk, RA: 2400007024,

Na disciplina de Linguagem formais e autômatos, ministrado pelo professor Emerson, Sexta e Sétima fase do Curso de Ciência da Computação.

CASCAVEL – PARANÁ
2015
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 com16 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 deforma 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.

Relatório:
Passeio do Cavalo
Capítulo 1 – Descrição do Problema
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