Sistemas de informação

Avaliação Empírica de Heurísticas para o Problema das Oito Rainhas
RENATO HIDAKA TORRES1, OTÁVIO NOURA TEIXEIRA2

Resumo. Diferentes metodologias são propostas para resolver problemas no âmbito da computação. Neste contexto, este artigo apresenta uma análise comparativa entre dois algoritmos que possuem diferentes metodologias para resolução do problema das oito rainhas. Palavras-chave: Algoritmo Genético (AG), Algoritmo Recursivo, Oito Rainhas.

Heuristics for empirical evaluation of the Problem of the Eight Queens
Abstract. Different methods are proposed to solve problems within the computer. In this context, this article presents a comparative analysis of two algorithms that have different approaches to solving the problem of eight queens. Key-words: Genetic Algorithm (GA), Recursive algorithm, Eight Queens.
.

1

Bacharelando em Ciência da Computação - Centro Universitário do Pará (CESUPA). e-mail: [e-mail]. 2 Mestre em Ciência da Computação, Docente da Área de Ciências Exatas e Tecnológicas - Centro Universitário do Pará (CESUPA). e-mail: [e-mail].

24

1 INTRODUÇÃO
Problemas enxadrísticos perduram na matemática e na computação ao longo da história. Com o passar do tempo novas soluções e metodologias foram criadas com o intuito de solucionar problemas clássicos como o problema das oito rainhas. O problema foi proposto em 1848 por Max Bezzel que lançou o seguinte desafio: “Será possível colocar oito rainhas em um tabuleiro de xadrez vazio de modo que nenhuma rainha esteja atacando qualquer outra, isto é, sem que duas rainhas quaisquer estejam na mesma linha, coluna ou diagonal?” Vários matemáticos como Friedrich Gauss e Georg Cantor tentaram resolver o problema, mas foi Franz Nauck em 1850 o primeiro homem a resolver e estender o desafio para o problema das “n” rainhas. Uma vez que o problema foi solucionado, diversas técnicas e metodologias foram propostas, dentre elas está o depth-first backtracking algorithm [Thomas,