ATPS LinguagENS FORMAIS

• 1. O Xadrez é um jogo estratégico de tabuleiro para dois jogadores. O jogo é disputado em umtabuleiro 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 reiinimigo, considerando o movimento particular de cada peça.“Passeio do Cavalo”Capítulo 1 – Descrição do ProblemaAlém do seu valor estratégico e lúdico, o xadrez também se mostra muito importanteno ponto de vista matemático e computacional. Diversos problemas de natureza combinatóriae topológica ligado ao xadrez são conhecidos, foram estudados nas últimas centenas de anose, mais recentemente, suas soluções foram aplicadas para resolução de vários problemascomputacionais. Esses problemas são chamados decomposições. Em uma composição oproblema é apresentado por meio da definição de uma distribuição de peças no tabuleiro e asolução consiste em realizar uma ação determinada. É comum que a ação a ser realizadavenha acompanhada de uma ou mais restrições. Existem diversas composições clássicas noxadrez. Uma delas é conhecida como o passeio do cavalo. Nessa composição o desafio é fazercom que o cavalo passe por todas as casas do tabuleiro. Inicialmente o cavalo está em umacasa qualquer e ele deve ser movimentado obedecendo às regras de movimentação para essapeça.Capítulo 2 – Descrição Textual dos Movimentos do XadrezSistema de notação algébrica, ver Figura1, é um método usado hoje em todas as organizaçõesde competição de xadrez e a maioria dos livros e periódicos para registrar e descrever lancesde partidas de xadrez. A forma mais comum usada, e primariamente descrita aqui, é tambémchamada de notação algébrica abreviada (ou curta) para distingui-la da notação algébricaexpandida (ou longa). Iniciada nos anos 1970, a notação algébrica abreviada acabou porsubstituir anotação descritiva de xadrez, apesar de que essa notação ainda possa ser achadana literatura mais antiga.Sistema de notação algébricaApós verificar as notações e rever o sistema de expressão regular, consegui terminar a mesma,deixando no modo abaixo sendo possível realizar toda a notação algébrica.^[R,D,B,C,T]*[a-h]*([a-h][0-7]#*){1}$

• 2. Capítulo 1 – Descrição do Problema.O problema do cavalo, ou passeio do cavalo, é um problema matemático envolvendo omovimento da peça do cavalo no tabuleiro de xadrez. O cavalo é colocado no tabuleiro vazio e,seguindo as regras do jogo, precisa passar por todas as casas exatamente uma vez, ou seja,movimentar o cavalo em “L” para que ele passe por todas as 64 casas do tabuleiro sem repetirnenhuma.Capítulo 2 – Descrição Textual dos Movimentos do XadrezAbaixo gramática regular que exemplifica uma sequência de movimento do cavalo em umtabuleiro 8x8.G=({S, C}, {a1,b1,c1,d1,e1,f1,g1,h1, a2,b2,c2,d2,e2,f2,g2,h2, a3,b3,c3,d3,e3,f3,g3,h3,a4,b4,c4,d4,e4,f4,g4,h4, a5,b5,c5,d5,e5,f5,g5,h5, a6,b6,c6,d6,e6,f6,g6,h6,a7,b7,c7,d7,e7,f7,g7,h7, a8,b8,c8,d8,e8,f8,g8,h8}, R, S) onde R:S→CC→e4; C→c3; C→g3; C→d2; C→f2; C→c5; C→g5, C→d6; C→f6Figura 1- Tabuleiro de XadrezFigura 2 - Tabuleiro de xadrez após aplicação da gramática regular descrita acimaAbaixo

...