Resolvendo o Problema do Cavalo no Xadrez Através de
Grafo Hamiltoniano
Grafo Hamiltoniano
Elias Vidal Bezerra Júnior |
O autor do artigo é nascido em Tocantinópolis, Tocantis, Brasil, acadêmico do curso de Ciência da Computação, Unitins, Palmas-TO, vidal@unitins.br. Atual campeão do Jut´s (Jogos Universitários do Tocantins). Um amante da arte de jogar de xadrez. |
"Elaborei esse problema com o objetivo de unir os conhecimentos computacionais que adquiri na disciplina de Teoria dos Grafos e o jogo de xadrez."
Considere o jogo de xadrez. Seguindo as regras de movimento do cavalo, é possível que um cavalo parta de uma casa qualquer, percorra todo o tabuleiro visitando cada casa uma e somente uma única vez e retorne à casa inicial?
No xadrez o movimento do cavalo é sempre em "L" (letra ele), ou seja, duas casas num sentido (vertical ou horizontal) e uma casa no outro sentido (horizontal ou vertical). Na figura ao lado estão postos dois cavalos, sendo que cada uma das setas indica um dos possíveis movimentos dos cavalos. |
Um modelo para este problema é definir o grafo G(V,A) como: V = { c | onde c é uma casa do tabuleiro de xadrez} A = { (c1,c2) | onde a casa c2 pode ser atingida a partir da casa c1 por um único movimento de cavalo} |
A solução deste problema passa por verificar se o grafo G é hamiltoniano.
Um grafo G é dito ser hamiltoniano se existe um ciclo em G que contenha todos os seus vértices, sendo que cada vértice só aparece uma vez no ciclo. Este ciclo é chamado de ciclo hamiltoniano. Sendo assim. um grafo é hamiltoniano se ele contiver um ciclo hamiltoniano.
Teorema: Se G é um grafo de ordem p (>=3) tal que o grau(v) >= p/2 para cada vértice v de G, então G é hamiltoniano.
Este grafo tem 64 vértices e 168 arestas e, em realidade, contém vários ciclos hamiltonianos, um dos quais é apresentado na figura que se segue.
Neste problema, a definição do grafo G(V,A) pode ser bem mais direcionada para uma implementação computacional se introduzirmos um pouco mais de formalismo quando da definição dos vértices e das arestas. Considere que tenhamos enumerado as linhas e colunas do tabuleiro de 1 a 8.O grafo poderia ser, então definido por: V = { (L,C) | onde L e C são a linha e a coluna, respectivamente, que denotam uma casa do tabuleiro de xadrez} A = { (v1,v2) | onde a casa v2 = (L2,C2) pode ser atingida a partir da casa v1 = (L1,C1) por um único movimento de cavalo} ou seja, | L1 - L2 | + | c1 - c2 | = 3, L1 ~= L2, c1 ~= c2}. |
Portanto, prova-se, um critério matemático simples que permite identificar as 64 casas do tabuleiro e todos os possíveis movimentos de um cavalo (168 arestas).
Nenhum comentário:
Postar um comentário