Problema das oito damas

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

O problema das oito damas é o problema matemático de dispor oito damas em um tabuleiro de xadrez de dimensão 8x8, de forma que nenhuma delas seja atacada por outra. Para tanto, é necessário que duas damas quaisquer não estejam numa mesma linha, coluna, ou diagonal. Este é um caso específico do Problema das n damas, no qual temos n damas e um tabuleiro com n×n casas(para qualquer n  ≥ 4).

História[editar | editar código-fonte]

O problema foi inicialmente proposto na revista Schachzeitung pelo enxadrista Max Bezzel em 1848, e ao longo dos anos foi avaliado por diversos matemáticos incluindo Gauss e Georg Cantor. A primeira solução foi proposta em 1850 por Franz Nauck, que também o generalizou para o Problema das n damas.

O aumento da Complexidade[editar | editar código-fonte]

Para dizermos que um problema é exponêncial, temos que prová-lo. Vamos para esse problema praticar a seguinte suposição - note que, mais adiante adotaremos tabuleiros iniciais específicos para podermos impor regras mais restritas - as rainhas, Q, movem-se da forma original e na distância original, a pergunta é, quantos são os estados em um tabuleiro de tamanho N?

  • seja r a distância máxima que a rainha percorre;
  • N o tamanho do tabuleiro e consequentemente o número de rainhas.
  • D o número de direções.

A quantidade de estados Ns é dada por:

Se em nossa seguinte suposição fizermos N=N+1, temos:

Então a distância de estados de i para i+1 é:

de i para um k qualquer:

Ao acrescentar uma unidade ao tamanho do tabuleiro acrescentamos um número absurdos de possíveis estados:

Tamanho Estados (max)
4 96
5 160
6 240
8 448
10 720
100 79200

Heurística Consistente[editar | editar código-fonte]

O custo de mover de um estado X até o outro Y é o número de movimentos feitos com as rainhas para chegar de X até Y.

Nossa heurística é a contagem de conflitos global existente no tabuleiro, ou a contagem de arcos que definem caminhos de tamanho 1 entre as rainhas.

Um exemplo de como a heurística é calculada.

A definição de Heurística consistente[1] é a heurística que não superestima o custo de um estado até a origem e respeita a regra:

  • h(x) Estimativa do custo de x até o objetivo;
  • c(x,y) Custo real do caminho x até y;
  • h(y) Estimativa do custo de y até o objetivo.

Deduções[editar | editar código-fonte]

Voltando a fórmula introduzida inicialmente:

Para o obter eficiência em problemas de Melhoria Iterativa[1] - Hill Climbing e Gradiente Descendente, para N's muito grandes, a redução dos multiplicadores D e r na fórmula acima foi analisada e agora será apresentada.

Nesta seção estamos apresentando algumas conclusões obtidas pelos experimentos realizados sobre o problema. Tais conclusões foram feitas com o intuito de aproveitar informações sobre o tabuleiro, principalmente entropia.

Rainhas com 0 conflitos[editar | editar código-fonte]

Este fator reduz progressivamente o número de estados gerados, pois considera que rainhas que já tem conflitos=0, ou seja, não possuem arcos que as conectem com outras rainhas, não precisam ter os estados referentes à sua movimentação calculados.

Esse princípio vem de uma dedução lógica. Se de N rainhas somente duas estão em conflito e todas as outras sem conflitos, estas podem fazer com um movimento uma terceira rainha que não faz parte do conflito anterior, poder ter seus vizinhos calculados criando uma nova direção no espaço de soluções. Sem a necessidade de calcular vizinhos para todas as N-2 rainhas existentes no tabuleiro.

Por que manter as Rainhas com conflitos = 0, a resposta é redução da entropia, outra fonte de informação sobre utilizar a entropia para tomar decisões temos este livro.[2] Suponha o seguinte:

  • A probabilidade de uma Casa no tabuleiro é o número de rainhas que podem legalmente alcançar esta casa sobre o número de rainhas o que vamos determinar como:

  • Entropia irá medir a quantidade de informação que determinada casa contém. Dizemos que quanto maior a sua entropia maior o número de bits necessários para representar esta quantidade. Então temos que a quantidade de informação de uma casa é :

Soluções[editar | editar código-fonte]

O problema possui 92 soluções distintas, que podem ser obtidas a partir de um conjunto de 12 soluções únicas, aplicando operações de simetria (rotação e reflexão). Essas 12 soluções fundamentais estão listadas abaixo:

8
a b c d e f g h
8
Chessboard480.svg
d8 branco rainha
g7 branco rainha
c6 branco rainha
h5 branco rainha
b4 branco rainha
e3 branco rainha
a2 branco rainha
f1 branco rainha
8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
a b c d e f g h
Solução única I
8
a b c d e f g h
8
Chessboard480.svg
e8 branco rainha
b7 branco rainha
d6 branco rainha
g5 branco rainha
c4 branco rainha
h3 branco rainha
f2 branco rainha
a1 branco rainha
8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
a b c d e f g h
Solução única II
8
a b c d e f g h
8
Chessboard480.svg
d8 branco rainha
b7 branco rainha
g6 branco rainha
c5 branco rainha
f4 branco rainha
h3 branco rainha
e2 branco rainha
a1 branco rainha
8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
a b c d e f g h
Solução única III
8
a b c d e f g h
8
Chessboard480.svg
d8 branco rainha
f7 branco rainha
h6 branco rainha
c5 branco rainha
a4 branco rainha
g3 branco rainha
e2 branco rainha
b1 branco rainha
8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
a b c d e f g h
Solução única IV
8
a b c d e f g h
8
Chessboard480.svg
c8 branco rainha
f7 branco rainha
h6 branco rainha
a5 branco rainha
d4 branco rainha
g3 branco rainha
e2 branco rainha
b1 branco rainha
8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
a b c d e f g h
Solução única V
8
a b c d e f g h
8
Chessboard480.svg
e8 branco rainha
c7 branco rainha
h6 branco rainha
d5 branco rainha
g4 branco rainha
a3 branco rainha
f2 branco rainha
b1 branco rainha
8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
a b c d e f g h
Solução única VI
8
a b c d e f g h
8
Chessboard480.svg
e8 branco rainha
g7 branco rainha
d6 branco rainha
a5 branco rainha
c4 branco rainha
h3 branco rainha
f2 branco rainha
b1 branco rainha
8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
a b c d e f g h
Solução única VII
8
a b c d e f g h
8
Chessboard480.svg
d8 branco rainha
a7 branco rainha
e6 branco rainha
h5 branco rainha
f4 branco rainha
c3 branco rainha
g2 branco rainha
b1 branco rainha
8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
a b c d e f g h
Solução única VIII
8
a b c d e f g h
8
Chessboard480.svg
c8 branco rainha
f7 branco rainha
d6 branco rainha
a5 branco rainha
h4 branco rainha
e3 branco rainha
g2 branco rainha
b1 branco rainha
8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
a b c d e f g h
Solução única IX
8
a b c d e f g h
8
Chessboard480.svg
f8 branco rainha
b7 branco rainha
g6 branco rainha
a5 branco rainha
d4 branco rainha
h3 branco rainha
e2 branco rainha
c1 branco rainha
8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
a b c d e f g h
Solução única X
8
a b c d e f g h
8
Chessboard480.svg
d8 branco rainha
g7 branco rainha
a6 branco rainha
h5 branco rainha
e4 branco rainha
b3 branco rainha
f2 branco rainha
c1 branco rainha
8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
a b c d e f g h
Solução única XI
8
a b c d e f g h
8
Chessboard480.svg
f8 branco rainha
d7 branco rainha
g6 branco rainha
a5 branco rainha
h4 branco rainha
b3 branco rainha
e2 branco rainha
c1 branco rainha
8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
a b c d e f g h
Solução única XII

Construindo uma solução[editar | editar código-fonte]

Encontrar uma solução para este problema não é assim tão fácil. Utilizando análise combinatória podemos perceber que existem

maneiras distintas de dispor 8 damas em um tabuleiro 8x8. Podemos notar, também, pelas operações de simetria que exitem 92 soluções. Logo, seja A um evento relacionado a uma solução, a probabilidade de A ocorrer colocando as damas aleatoriamente no tabuleiro é:

Se adotarmos uma estratégia em que colocássemos somente uma dama para cada linha e coluna, o número de maneiras distintas diminuiria para:

e a probabilidade do evento A ocorrer seria de:

que é consideravelmente maior.

Pode-se assim diminuir o tempo em que um algoritmo que solucione o problema é executado.

Eight-queens-animation.gif

Esta animação usa backtracking para resolver o problema. Uma dama é posicionada em uma coluna em que se sabe que não causará conflito. Se nenhuma coluna é encontrada, o programa retorna à última situação válida e tenta uma coluna diferente.

  1. a b Russell, S. J. and Norvig, P. 1995 Artificial Intelligence: a Modern Approach. Prentice-Hall, Inc.
  2. Luger, G. F. 1997 Artificial Intelligence: Structures and Strategies for Complex Problem Solving. 3rd. Addison-Wesley Longman Publishing Co., Inc.