Resolvendo o Problema do Cavalo no Xadrez Através de Grafo Hamiltoniano

Resolvendo o Problema do Cavalo no Xadrez Através de
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).