ATPS Linguagens Formais E Automatos

Etapa 1

O PASSEIO DO CAVALO

1. Descrição do Problema.

O problema do cavalo é um problema matemático conhecido desde meados do Séc. XVI, quando apareceu pela primeira vez no quinto livro de Bhagavantabháskara. Esse problema baseia-se basicamente no movimento do cavalo em um tabuleiro de xadrez. Para isso, a peça é colocada em um tabuleiro vazio e, com movimentos consecutivos e seguindo as regras do xadrez, deve percorrer todas as casas exatamente uma vez cada uma. Existem milhares de soluções para esse problema, das quais 26.534.728.821.064 terminam atacando exatamente a casa de onde partiu o movimento inicial, formando assim um ciclo que é conhecido como caminho fechado. Caso a casa final seja diferente da casa de partida, este caminho é dito como aberto. Dentre ambos os caminhos disponíveis, somente no caminho fechado é possível iniciar a solução em qualquer casa do tabuleiro.

2. Descrição Textual dos Movimentos do Xadrez.

O Cavalo é a única peça do xadrez que pode saltar sobre outras peças. Ele tem um movimento bem peculiar em formato de "L": duas casas no sentido vertical ou horizontal e uma casa no outro sentido.

A posição do cavalo é dada por suas coordenadas cartesianas no tabuleiro, onde o eixo x é representado por letras de ‘a’ até ‘h’ e o eixo y representado por números, de 1 até 8.

Seguindo essa linha de raciocínio é possível gerar a Gramática Regular do passeio do cavalo, como informado abaixo:

G = (V, T, P, S)

Onde,

V = {S, A1, A2, A3, A4, A5, A6, A7, A8, B1, B2, B3, B4, B5, B6, B7, B8, C1, C2, C3, C4, C5, C6, C7, C8, D1, D2, D3, D4, D5, D6, D7, D8, E1, E2, E3, E4, E5, E6, E7, E8, F1, F2, F3, F4, F5, F6, F7, F8, G1, G2, G3, G4, G5, G6, G7, G8, H1, H2, H3, H4, H5, H6, H7, H8};

T = {a1, a2, a3, a4, a5, a6, a7, a8, b1, b2, b3, b4, b5, b6, b7, b8, c1, c2, c3, c4, c5, c6, c7, c8, d1, d2, d3, d4, d5, d6, d7, d8, e1, e2, e3, e4, e5, e6, e7, e8, f1, f2, f3, f4, f5, f6, f7, f8, g1, g2, g3, g4, g5, g6, g7, g8, h1, h2, h3, h4, h5, h6, h7, h8};

S = S;

P = {

S d4C2 | d4B3 | d4B5 | d4C6 | d4E6 | d4F5 | d4F3 | d4E2

A1 a1C2 | a1B3 | ε

A2 a2C1 | a2C3 | a2B4 | ε

A3 a3B1 | a3C2 | a3C4 | a3B5 | ε

A4 a4B2 | a4C3 | a4C5 | a4B6 | ε

A5 a5B3 | a5C4 | a5C6 | a5B7 | ε

A6 a6B4 | a5C5 | a6C7 | a6B8 | ε

A7 a7B5 | a7C6 | a7C8 | ε

A8 a8B6 | a8C7 | ε

B1 b1D2 | b1A3 | b1C3 | ε

B2 b2D1 | b2A4 | b2C4 | b2D3 | ε

B3 b3A1 | b3A5 | b3C5 | b3D4 | b3D2 | b3C1 | ε

B4 b4A2 | b4A6 | b4C6 | b4D5 | b4D3 | b4C2 | ε

B5 b5A3 | b5A7 | b5C7 | b5D6 | b5D4 | b5C3 | ε

B6 b6A4 | b6A8 | b6C8 | b6D7 | b6D5 | b6C4 | ε

B7 b7A5 | b7D8 | b7D6 | b7C5 | ε

B8 b8A6 | b8D7 | b8C6 | ε

C1 c1A2 | c1B3 | c1D3 | c1E2 | ε

C2 c2A1 | c2A3 | c2B4 | c2D4 | c2E3 | c2E1 | ε

C3 c3A2 | c3A4 | c3B5 | c3D5 | c3E4 | c3E2 | c3D1 | c3B1 | ε

C4 c4A3 | c4A5 | c4B6 | c4D6 | c4E5 | c4E3 | c4D2 | c4B2 | ε

C5 c5A4 | c5A6 | c5B7 | c5D7 | c5E6 | c5E4 | c5D3 | c5B3 | ε

C6 c6A5 | c6A7 | c6B8 | c6D8 | c6E7 | c6E5 | c6D4 | c6B4 | ε

C7 c7A6 | c7A8 | c7E8 | c7E6 | c7D5 | c6B5 | ε

C8 c8A7 | c8E7 | c8D6 | c6B6 | ε

D1 d1B2 | d1C3 | d1E3 | d1F2 | ε

D2 d2B1 | d2B3 | d2C4 | d2E4 | d2F3 | d2F1 | ε

D3 d3B2 | d3B4 | d3C5 | d3E5 | d3F4 | d3F2 | d3E1 | d3C1 | ε

D4 d4B3 | d4B5 | d4C6 | d4E6 | d4F5 | d4F3 | d4E2 | d4C2 | ε

D5 d5B4 | d5B6 | d5C7 | d5E7 | d5F6 | d5F4 | d5E3 | d5C3 | ε

D6 d6B5 | d6B7 | d6C8 | d6E8 | d6F7 | d6F5 | d6E4 | d6C4 | ε

D7 d7B6 | d7B8 | d7F8 | d7F6 | d7E5 | d6C5 | ε

D8 d8B7 | e8F7 | e8E6 | d6C6 | ε

E1 e1C2 | e1D3 | e1F3 | e1G2 | ε

E2 e2C1 | e2C3 | e2D4 | e2F4 |

...