Trabalho Analise De Algoritimos

Problema das N-Rainhas
Luiz Marcelo Ferreira
Rua Caspio nº 48, Bairro Betânia, CEP 30590-450, Belo Horizonte, MG - Brazil [e-mail] Abstract. This paper aims at the problem of N-Queens, a possible solution and its classification as P, NP, or NP-Complete. This problem was proposed in
1850 by Carl Friedrich Gauss and has the following statement:
Find an array of N queens of the chess board in an N x N, so that no queen attacks the other in accordance with the rules of the game.
Resumo. Este trabalho tem por objetivo o problema das N-Rainhas,uma possível solução e sua classificação, como P, NP, ou NP-Completo . 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.

1. Introdução
Este trabalho apresenta o problema da computação das N-Rainhas, o contextualizando e dentro de uma das classes P, NP ou NP-Completo, exemplificando e sugerindo uma possível solução para o problema.

2. Descrição do Problema
O problema das N-Rainhas é descrito 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.
Assim apenas podemos ter 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, pois apenas 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.
Você pode acessar e estudar o problema visualmente através de um jogo em tabuleiro 8x8, disponível em: