ATPS - Passeio Do Cavalo

FAI – Faculdade Anhanguera de Indaiatuba

ATPS – Linguagens Formais e Autômatos

Nome: Erick Anderson M Gonçalves R.A.: 3730719895

Felipe Pujós 1040795765

Hudson Guedes Ramos 1001762163

Marcela Bisin 1001801155

Indaiatuba, de Abril de 2013.

Etapa 1

1 - Descrição do problema

Esse problema baseia-se em colocar a peça cavalo em um tabuleiro vazio e com movimentos consecutivos seguindo as regras de movimentação da peça tentar percorrer todas as casas do tabuleiro apenas uma vez. Existem milhares de soluções para esse problema matemático muito famoso.

2 - Descrição textual dos Movimentos do Xadrez

O cavalo é a única peça capaz de “saltar” outras peças. Com um movimento diferenciado no formato de um “L” sendo duas casas no vertical ou horizontal e mais uma no sentido oposto.

O tabuleiro é representado por letras e números que vão de “A” até “H” e de 1 até 8, dando a posição de uma peça com a combinação dos símbolos, como por exemplo: D6, A8, C2, etc.

A gramática regular para o passeio do cavalo:

G = (V, T, P, S)

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