Problema das n-rainhas

Disponível somente no TrabalhosFeitos
  • Páginas : 7 (1732 palavras )
  • Download(s) : 0
  • Publicado : 9 de março de 2013
Ler documento completo
Amostra do texto
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 foiproposto 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 podehaver 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 é facilmenteresolvido 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 propriedadesestruturais adicionadas a solução. Basicamente consiste em:

• Um conjunto de variáveis que podem assumir valores de um dado domínio
• Um conjunto de restrições que especificam propriedades da solução.


Para encontrar a solução devemos especificar valores para todas as variáveis tal forma que as restrições sejam atendidas.

Cada variável Vi possui um domínio Di .
O domínio é o conjunto detodos os valores possíveis que a variável pode assumir.
As restrições especificam sub conjuntos do domínio de uma variável.


2.1.1 – Problema das N-Rainhas visto como um CSP



|Variáveis |Localidade de cada uma das N rainhas. Vi especifica a coluna ocupada pela rainha já que cada rainha pode ocupar |
| |apenas uma linha.|
|Domínio |Valores possíveis para as variáveis (posições do tabuleiro). |
|Restrições |Conjunto de valores permitidos para as variaveis de forma que as rainhas não se ataquem. |

Vamos acompanhar a solução para 4rainhas.

• Variáveis → V1, V2, V3, V4
• Domínio → {1,2,3,4}
• Restrções → Qi ‡ Qj (não podem estar na mesma coluna)
|Qi – Qj| ‡ |i-j| (não podem estar na mesma diagonal)


Inicialmente todas as variáveis possuem os valores do domínio, já que as restrições ainda não foram aplicadas. As variáveis se apresentam a seguir:


V1 = {1,2,3,4}V2 = {1,2,3,4}
V3 = {1,2,3,4}
V4 = {1,2,3,4}


Vamos selecionar um valor para a variável V1, ou seja, a coluna que a rainha da primeira linha irá ocupar.


Fazemos V1 = 1
Aplicamos as restrições temos que:


V2 = {3,4} V2 ‡ V1 e V2 ‡ V1 + 1
V3 = {2,4} V3 ‡ V1 e V3 ‡ V1 + 2
V4 = {2,3} V4 ‡ V1 e V4 ‡ V1 + 3


Agora que temos um possível...
tracking img