relatorio

Problema das N-rainhas solucionado por Busca
Informada, Algoritmo Genético e Busca PSR
Alexandre Eiji Harada, Gustavo H. G. Matsushita, Larissa Y. Matsuda
Departamento de Informática – Universidade Estadual de Maringá (UEM)
Maringá – PR – Brasil
Professor Wagner Igarashi

[e-mail], [e-mail], [e-mail]

Resumo: Este trabalho diz respeito a um dos problemas mais discutidos na área de
Inteligência Artificial: o problema das N-rainhas. É implementado três algoritmos na linguagem Java para a resolução deste problema, sendo um algoritmo de Busca
Informada, um Algoritmo Genético e um PSR (Problema de Satisfação de Restrição).
Após a solução do problema é apresentado e analisado os resultados obtidos nas diferentes implementações, tirando as devidas conclusões para tais informações.

1 . Introdução
A Inteligência Artificial (IA) é um ramo da Ciência da Computação que se propõe a elaborar dispositivos que simulam a capacidade humana de raciocinar, perceber, tomar decisões e resolver problemas, enfim, a capacidade de ser inteligente.
Um dos problemas muito discutido na área de IA é o problema das N-Rainhas, inicialmente proposto para apenas 8 rainhas, foi introduzido por um jogador de xadrez de nome Max Bazzel em 1848. Desde então, captou a atenção de muitos matemáticos e, mais recentemente, tem sido discutido no âmbito das ciências computacionais, sendo usado como exemplo de algoritmos de “backtracking”, de geração de permutações, de redes neuronais, de problemas de satisfação de restrições e de paradigmas de “divisão e conquista”, entre outros.
O problema pode parecer um simples jogo: como colocar N rainhas num tabuleiro de xadrez, com N linhas e N colunas, sem que qualquer uma possa atacar outra, dado que, no xadrez, as rainhas têm liberdade de movimentos na horizontal, vertical e diagonal. Na realidade, este problema corresponde à modelação de um problema de cobertura máxima: a solução garante que cada rainha possa ser acedida por qualquer das principais