Introdução à Inteligência Artificial - SCE-5774 |
Trabalho 01 |
Instituto de Ciências Matemáticas e de Computação - ICMC Programa de Doutorado em Ciência da Computação |
|
Apresentação Objetivos Problema Código-Fonte Resolução Caso de Teste Ambiente Prolog Conclusões Referências |
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.
|
||
Objetivos
Permitir o aprendizado da linguagem de programação Prolog 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. 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. Caso de Teste
Considerando-se a implementação feita, o seguinte caso de teste foi realizado: Figura 03 - Interface que ilustra o resultado do caso de teste do programa Como resultado do caso de teste, o programa gera uma lista de pares de coordenadas, lista esta que pode ser decomposta pelos predicados acionados pelo predicado tabuleiro para gerar a representação gráfica. Voltar ao Início Ambiente Prolog
Para o desenvolvimento do trabalho foi utilizado o LPA Prolog - Ambiente Integrado de Desenvolvimento, de duas formas básicas: Figura 04 - Ambiente Prolog utilizado para o desenvolvimento do trabalho 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. Referências
BRATKO, I.: PROLOG: Programming for Articial Intelligence. Addison-Wesley Publishing, 1986. |