N-Queen Problem

Algoritmos implementados:

• Backtracking
• Minimum Conflicts
• Propagation
• Genetic

Algoritmos

Backtracking

Também conhecido como uma forma refinada do algoritmo de Força Bruta, Busca Completa ou Enumeração Exaustiva, o Backtracking consiste em métodos para vasculhar o espaço de busca por completo ou em partes em busca da solução desejada.

No caso do problema das N-Rainhas, há a imposição de restrições e condições no *Backtracking*, tratando-se assim de uma classe de problemas que é conhecida como *Constraint Satisfaction Problem* (CSP), traduzida para Problemas de Satisfação de Restrições (PSR).

Minimum Conflicts

O *Minimum Conflicts (min-conflicts)* funciona a partir de uma atribuição inicial de valores às variáveis do problema. A cada iteração, o algoritmo seleciona aleatoriamente uma variável com conflitos e atribui a ela o valor que minimiza o número desses conflitos. Se houver mais de um valor com o mesmo número mínimo de conflitos, um deles é escolhido aleatoriamente.

Propagation

A propagação de restrição foi interligada com essas buscas, ela consistiu de realizar mudanças nas estruturas de dados que representam os tabuleiros, agora existe uma matriz que registra quantos conflitos cada célula possui e um vetor que contém as posições das rainhas.

Genetic

Os algoritmos genéticos buscam resolver problemas computacionais de otimização simulando o comportamento da seleção natural de candidatas à soluções, encontrado na natureza e descrito primeiramente por Charles Darwin.

Nessa teoria, dentro de uma população de indivíduos há uma disputa de recursos e uma necessidade de sobrevivência em um determinado ambiente, onde existe uma tendência para que indivíduos mais aptos conseguem reproduzir-se deixando suas características genéticas para as gerações futuras. Com o tempo as gerações de indivíduos começam a se especializar e se tornarem mais aptas em seu ambiente, seja através do recebimento do material genético de gerações pais quanto por mutações geradas de forma natural.

Essa solução pode ser aplicada ao problema de N-rainhas consistindo de uma forma interessante de busca local a fim de encontrar uma solução que atenda todas as restrições do problema.

Como executar

Java

É necessário possuir a versão 17 do JAVA ou superior.

Entre nas pastas dos projetos e execute o seguinte comando no terminal:

./gradlew run --console=plain

gradlew.bat run --console=plain

Insira o valor n contendo o número para o problema do n rainhas:

Analisar soluções encontradas

Na pasta board-htm ao acessar o arquivo index.html é possível submeter uma solução do problema, no formato de json, e dessa maneira gerar uma melhor visualização das posições das rainhas:

Resultados

Essa seção traz um resumo dos casos de testes que foram utilizados para cada um dos algoritmos, a fim de estabelecer um comparativo gráfico das soluções encontradas. Lembrando que algoritmos que abordagens aleatórias são mais difíceis de realizar um comparativo, devido a isso os valores presentes são apenas dos testes feitos em um notebook com sistema operacional Linux e cpu AMD Ryzen™ 7 5800H with Radeon™ Graphics × 16.

Input(N)	Tempo em milissegundos
	backtracking	Heurística Minimum Conflicts	backtracking (propagation)	Heurística Minimum Conflicts (propagation)	genético
8	1	4	0	4	15
16	19	6	6	5	41
24	204	8	158	7	44
32	62101	8	17661	6	77
40	7200000	8	7200000	6	49
64	-	18	-	6	90
100	-	38	-	7	310

Após os experimentos feitos, conseguimos avaliar o desempenho e analisar os resultados retornados. Com base nas informações expostas, notamos as limitações de cada algoritmo utilizado. Algoritmos como Backtracking por ter que percorrer de forma sistemática muitas soluções acabou por ter um tempo de execução muito maior do que se comparado com heurísticas e o algoritmo genético. Já o algoritmo genético se mostrou interessante resolvendo casos menores com rapidez e podendo resolver casos maiores dadas as condições. O uso da heurística de conflitos mínimos se mostrou eficiente na resolução de problemas de N-rainhas, com o uso de técnicas de propagação é possível melhorar seu desempenho, porém o algoritmo apresenta problemas com valores de N muito grande, devido ao processo de sorteio de números aleatórios.