1 – Introdução 2
2 – Descrição do Problema 2 2.1 – Problema de Satisfação de Restrições (CSP). 2 2.1.1 – Problema das N-Rainhas visto como um CSP 3 2.2 – Backtracking 5
3 – Solução 6
4 – Testes de Eficiência 8 5 – Conclusão 8
6 – Bibliografia 8

1 – Introdução

Este trabalho tem por objetivo apresentar uma solução para o problema da N-Rainhas. Este problema foi proposto em 1850 por Carl Friedrich Gauss e tem o seguinte enunciado:

|Encontrar uma disposição de N rainhas do jogo de xadrez em um tabuleiro N x N, de tal modo que |
|nenhuma rainha ataque as outras de acordo com as regras do jogo. |

O algoritmo construído para resolver este problema baseia-se em dois conceitos que serão abordados no decorrer deste texto, são eles: Satisfação de Restrições e Backtracing.

2 – Descrição do Problema

O problema das N-Rainhas é descrito informalmente a seguir:

Colocar um número N de rainhas em um tabuleiro NxN (tipo xadrez) de forma que elas não se ataquem. Por ataque entendemos que quaisquer duas rainhas não podem compartilhar a mesma linha, coluna ou diagonal.
Isto significa que no máximo pode haver uma rainha em cada linha, coluna ou diagonal, e exatamente N rainhas no tabuleiro. A figura abaixo mostra um tabuleiro 4x4 onde 4 rainhas foram colocadas satisfazendo as restrições do problema.
| |X | | |
| | | |X |
|X |