Apresentação

Este trabalho faz parte do programa da disciplina de Introdução à Inteligência Artificial, do Programa de Mestrado e Doutorado em Ciência da Computação, do Instituto de Ciências Matemáticas e de Computação, da Universidade São Paulo, como parte dos requisitos de avaliação da disciplina, que está sendo ministrada neste primeiro semestre de 1999 pela Profa. Dra. Sandra Maria Aluísio.

Voltar ao Início

Objetivos

Permitir o aprendizado da linguagem de programação Prolog
Aplicar os conceitos de programação baseada em lógica
Aplicar os conceitos sobre listas, operadores, funções de E/S
Aplicar técnicas de "busca cega" para manipulação de listas
Resolver um problema didático relatado na literatura de Inteligência Artifical

Voltar ao Início

Problema

Este trabalho objetiva apresentar uma solução para o Problema das Oito Rainhas em um Tabuleiro de Xadrez. Tal problema é um exemplo didático clássico da literatura de Inteligência Artificial, e consiste em posicionar oito rainhas em um tabuleiro de xadrez de modo que não haja possibilidade de ataque entra elas. De modo geral, pode-se observar que o posicionamento das rainhas no tabuleiro passa pela definição das posições de ataque. Neste ponto, uma rainha, uma vez posicionada, pode sofrer ataques verticais, horizontais e diagonais, conforme ilustra a Figura 01.

Figura 01 - Restrições para posicionamento de uma rainha no tabuleiro

Figura 02 - Uma possível solução para o posicionamento de oito rainhas no tabuleiro

Voltar ao Início

Código-Fonte

O programa para resolver o problema de posicionamento das oito rainhas no tabuleiro de xadrez foi implementado na linguagem de programação PROLOG, e alguns trechos de código-fonte encontram-se descritos a seguir.

solucaonrainhas([]).

solucaonrainhas([X/Y | OUTRASCOORDENADAS]) :-
solucaonrainhas(OUTRASCOORDENADAS),
membro(Y,[1,2,3,4,5,6,7,8]),
naopodeatacar(X/Y,OUTRASCOORDENADAS).

naopodeatacar(_,[]).

naopodeatacar(X/Y,[X1/Y1|OUTRASCOORDENADAS]) :-
Y=\=Y1,
Y1-Y=\=X1-X,
Y1-Y=\=X-X1,
naopodeatacar(X/Y,OUTRASCOORDENADAS).

membro(X,[X|LISTA]).
membro(X,[Y|LISTA]) :- membro(X,LISTA).

linhadivisoria :- write(' +---+---+---+---+---+---+---+---+'),nl.

tabelainferior :-
write(' +---+---+---+---+---+---+---+---+'),nl,
write(' 1 2 3 4 5 6 7 8 '),nl.

rainha8(X,[X|LISTA]) :- X == 1/8,write('8| R | | | | | | | |'),nl.
rainha8(X,[X|LISTA]) :- X == 2/8,write('8| | R | | | | | | |'),nl.
rainha8(X,[X|LISTA]) :- X == 3/8,write('8| | | R | | | | | |'),nl.
rainha8(X,[X|LISTA]) :- X == 4/8,write('8| | | | R | | | | |'),nl.
rainha8(X,[X|LISTA]) :- X == 5/8,write('8| | | | | R | | | |'),nl.
rainha8(X,[X|LISTA]) :- X == 6/8,write('8| | | | | | R | | |'),nl.
rainha8(X,[X|LISTA]) :- X == 7/8,write('8| | | | | | | R | |'),nl.
rainha8(X,[X|LISTA]) :- X == 8/8,write('8| | | | | | | | R |'),nl.
rainha8(X,[Y|LISTA]) :- rainha8(X,LISTA).

...

tabuleiro(S) :-
nl,
write('Representacao Grafica para o Problema das Oito Rainhas'),
nl,
write('------------------------------------------------------'),
nl,
linhadivisoria,
rainha8(Y8,S),
linhadivisoria,

...

linhadivisoria,
rainha1(Y1,S),
tabelainferior,
nl,nl,write('Lista contendo a solucao: '),nl.

imprimeresposta([1/Y1,2/Y2,3/Y3,4/Y4,5/Y5,6/Y6,7/Y7,8/Y8]).

resolveproblema(S) :-
imprimeresposta(S),
solucaonrainhas(S),
tabuleiro(S),!.

Clique aqui para obter o código-fonte

Voltar ao Início

Resolução

Conforme mostra o código-fonte, um conjunto de recursos da linguagem Prolog foi utilizado para prover a solução do problema. Inicialmente, observa-se a manipulação de listas para armazenar os pares de coordenadas XY do tabuleiro de xadrez. Operadores aritméticos foram utilizados para a composição de expressões envolvendo as coordenadas XY, para obtenção das posições válidas para o posicionamento de cada uma das oito rainhas. Recursos de formatação de saída foram utilizados para desenhar um tabuleiro de xadrez na interface, permitindo a visualização gráfica das posições geradas como solução do problema. Predicados recursivos foram implementados para permitir a "busca cega" na lista de coordenadas e montar a lista que apresenta a solução para o problema. Observa-se, ainda, a presença do operador / que permite a combinação dos valores X e Y para a formação de um par de coordenadas.

Em termos da estratégia para resolução do problema, pode-se observar o seguinte:
- inicialmente, uma lista é construída para armazenar os valores válidos para as coordenadas Y;
- o predicado recursivo membro tem a função de verificar se uma determinada coordenada faz parte da lista de coordenadas Y;
- o predicado recursivo naopodeatacar gera, a partir de um par de coordenadas XY, uma lista de coordenadas que contem posicões em que uma determinada rainha não pode ser atacada;
- os predicados rainha8...rainha1 são utilizados para gerar a representação gráfica do posicionamento de cada rainha no tabuleiro;
- os predicados tabelainferior e linhadivisoria são utilizados para formatar a interface do tabuleiro de xadrez;
- o predicado tabuleiro apresenta a solução gráfica para o problema;
- o predicado resolveproblema aciona a chamada do predicadosolucaonrainhas que, recursivamente, gera uma lista de coordenadas que define a solução para o problema.

Vale a pena observar que, na chamada do predicado resolveproblema, optou-se por evitar o backtracking, através do uso do operador !, o que proporciona a apresentação somente da primeira solução para o problema. Se tal operador for retirado, pode-se obter outras N soluções.

Voltar ao Início

Caso de Teste

Considerando-se a implementação feita, o seguinte caso de teste foi realizado:
resolveproblema(S).

Como resultado do acionamento do motor de inferência da linguagem Prolog, obteve-se o resultado apresentado pela Figura 03.

Figura 03 - Interface que ilustra o resultado do caso de teste do programa

Ambiente Prolog

Para o desenvolvimento do trabalho foi utilizado o LPA Prolog - Ambiente Integrado de Desenvolvimento, de duas formas básicas:
- uma versão demo obtida via download;
- uma versão completa instalada nos laboratórios do ICMC-USP.

Figura 04 - Ambiente Prolog utilizado para o desenvolvimento do trabalho

Voltar ao Início

Conclusões

O trabalho aqui reportado contribuiu, inicialmente, para que o autor pudesse "ter um novo contacto" com a linguagem de programação Prolog, visto que o contacto inicial havia sido feito em tempos de graduação, mais precisamente em 1992.

Em adição, ao revisitar o problema das oito rainhas, um problema bastante conhecido e resolvido pela literatura, o autor pode revalidar conhecimentos em construção de predicados e regras de produção de soluções, além de apresentar uma versão, ainda que rústica, para a representação gráfica da solução ("coisas de quem ainda está se readaptando à linguagem Prolog").

Por fim, a estratégia implementada apresenta boa eficiência por conseguir evitar situações de busca que conduzam a posições em que uma determinada rainha possa ser atacada.

Referências

BRATKO, I.: PROLOG: Programming for Articial Intelligence. Addison-Wesley Publishing, 1986.
MONARD, M.C. et al.: Introdução à Programação Prolog. Disponível on-line em http://www.labic.icmc.sc.usp.br, 1998.
ALUÍSIO, S.M.: Introdução ao Prolog.Notas de Aula da disciplina de Introdução à Inteligência Artificial. ICMC-USP, 1999.

Voltar ao Início