Problema das n-rainhas

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 | | | |
| | |X | |

O problema é facilmente resolvido para N=1, por definição existirá 1 rainha ocupando a única linha, coluna e diagonal.
Para N=2 e N=3 não existe solução pois é impossível que as rainhas não compartilhem a mesma Diagonal. Para N >3 podem existir mais de uma solução.

2.1 – Problema de Satisfação de Restrições (CSP).

Um problema de satisfação de restrições é um tipo de problema que impõe propriedades