Problema das oito damas

Origem: Wikipédia, a enciclopédia livre.
(Redirecionado de Problema das oito rainhas)

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.[1]

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[2] é 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[2] - 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.[3] 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
abcdefgh
8
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
77
66
55
44
33
22
11
abcdefgh
Solução única I
8
abcdefgh
8
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
77
66
55
44
33
22
11
abcdefgh
Solução única II
8
abcdefgh
8
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
77
66
55
44
33
22
11
abcdefgh
Solução única III
8
abcdefgh
8
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
77
66
55
44
33
22
11
abcdefgh
Solução única IV
8
abcdefgh
8
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
77
66
55
44
33
22
11
abcdefgh
Solução única V
8
abcdefgh
8
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
77
66
55
44
33
22
11
abcdefgh
Solução única VI
8
abcdefgh
8
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
77
66
55
44
33
22
11
abcdefgh
Solução única VII
8
abcdefgh
8
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
77
66
55
44
33
22
11
abcdefgh
Solução única VIII
8
abcdefgh
8
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
77
66
55
44
33
22
11
abcdefgh
Solução única IX
8
abcdefgh
8
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
77
66
55
44
33
22
11
abcdefgh
Solução única X
8
abcdefgh
8
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
77
66
55
44
33
22
11
abcdefgh
Solução única XI
8
abcdefgh
8
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
77
66
55
44
33
22
11
abcdefgh
Solução única XII

A solução X possui a propriedade adicional de não possuir três rainhas em uma mesma linha reta.

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.

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.

Em julho de 2021, foi resolvido pelo menos, até certo ponto. Para oito rainhas em um tabuleiro padrão de 8 x 8, a resposta é 92, embora a maioria delas sejam variantes rotacionadas ou refletidas de apenas 12 soluções fundamentais.

Mas para 1.000 rainhas em um tabuleiro de 1.000 x 1.000 quadrados, a solução aproximada para o problema é (0,143n)n – o número de rainhas multiplicado por 0,143, elevado à potência de n. Com um milhão de rainhas, a figura sai como um número com cinco milhões de dígitos depois.[4]

Referências

  1. published, Ben Turner (3 de fevereiro de 2022). «Mathematician cracks 150-year-old chess problem». livescience.com (em inglês). Consultado em 8 de fevereiro de 2022 
  2. a b Russell, S. J. and Norvig, P. 1995 Artificial Intelligence: a Modern Approach. Prentice-Hall, Inc.
  3. Luger, G. F. 1997 Artificial Intelligence: Structures and Strategies for Complex Problem Solving. 3rd. Addison-Wesley Longman Publishing Co., Inc.
  4. Nield, David. «A Harvard Mathematician Has Basically Solved an Epic, 150-Year-Old Chess Problem». ScienceAlert (em inglês). Consultado em 8 de fevereiro de 2022