Mostrar código-fonte de Problema das oito damas

O '''problema das oito damas''' é o problema matemático de dispor oito [[Dama (xadrez)|damas]] em um [[Tabuleiro (xadrez)|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'' &nbsp;≥&nbsp;4).

== História ==
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 [[Carl Friedrich Gauss|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'''.<ref>{{Citar web|ultimo=published|primeiro=Ben Turner|url=https://www.livescience.com/150-year-chess-problem-solved|titulo=Mathematician cracks 150-year-old chess problem|data=2022-02-03|acessodata=2022-02-08|website=livescience.com|lingua=en}}</ref>

== O aumento da Complexidade ==

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?<br />
*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.
::<math>r=N-1</math>

A quantidade de estados Ns é dada por:<br />
::<math>N_s^i=D*N*r</math>

Se em nossa seguinte suposição fizermos N=N+1, temos:<br />
::<math>
\begin{array}{l}
N_s^{i+1}=D*(N+1)*(r+1)\\
N_s^{i+1}=D*(N*r+(N+r)+1)
\end{array}
</math>

Então a distância de estados <math>D_e</math> de i para i+1 é:<br />
::<math>
D_e = D*((N+r)+1)
</math>

de i para um k qualquer:<br />
::<math>
D_e = D*(k-i)*(N+r)+D*(k-i)
</math>

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

{| border=1
|-----
| Tamanho || Estados (max)
|-----
| 4 || 96
|-----
| 5 || 160
|-----
| 6 || 240
|-----
| 8 || 448
|-----
| 10 || 720
|-----
| 100 || 79200
|}

== Heurística Consistente ==

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.

[[Imagem:ExemploConflitos 100.png|Um exemplo de como a heurística é calculada.]]

A definição de Heurística consistente<ref name="Russel">Russell, S. J. and Norvig, P. 1995 Artificial Intelligence: a Modern Approach. Prentice-Hall, Inc.</ref> é a heurística que não superestima o custo de um estado até a origem e respeita a regra:

::<math>
h(x)\leq c(x,y)+h(y)
</math>
*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 ==

Voltando a fórmula introduzida inicialmente:<br />
::<math>N_s^i=D*N*r</math>

Para o obter eficiência em problemas de Melhoria Iterativa<ref name="Russel" /> - 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 (teoria da informação)|entropia]].

=== Rainhas com 0 conflitos===

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 (teoria da informação)|entropia]], outra fonte de informação sobre utilizar a entropia para tomar decisões temos este livro.<ref name="Luger">Luger, G. F. 1997 Artificial Intelligence: Structures and Strategies for Complex Problem Solving. 3rd. Addison-Wesley Longman Publishing Co., Inc.</ref> 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:
<math>P(x,y)=\frac{\sum_{i=0}^NQ_{\rightarrow(x,y)}^i}{N}</math>
*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 <math>K(x,y)</math> é :
<math>K(x,y)=\sum_{i=0}^N-P(x,y)\log_2P(x,y)</math>

== Soluções ==
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:
<table>
<tr>
<td>
{{Diagrama de xadrez pequeno
| tright
|
8  |__|__|__|ql|__|__|__|__
7  |__|__|__|__|__|__|ql|__
6  |__|__|ql|__|__|__|__|__
5  |__|__|__|__|__|__|__|ql
4  |__|ql|__|__|__|__|__|__
3  |__|__|__|__|ql|__|__|__
2  |ql|__|__|__|__|__|__|__
1  |__|__|__|__|__|ql|__|__
|Solução única I
}}
</td>
<td>
{{Diagrama de xadrez pequeno
| tright
|
8  |__|__|__|__|ql|__|__|__
7  |__|ql|__|__|__|__|__|__
6  |__|__|__|ql|__|__|__|__
5  |__|__|__|__|__|__|ql|__
4  |__|__|ql|__|__|__|__|__
3  |__|__|__|__|__|__|__|ql
2  |__|__|__|__|__|ql|__|__
1  |ql|__|__|__|__|__|__|__
|Solução única II
}}
</td>
<td>
{{Diagrama de xadrez pequeno
| tright
|
8  |__|__|__|ql|__|__|__|__
7  |__|ql|__|__|__|__|__|__
6  |__|__|__|__|__|__|ql|__
5  |__|__|ql|__|__|__|__|__
4  |__|__|__|__|__|ql|__|__
3  |__|__|__|__|__|__|__|ql
2  |__|__|__|__|ql|__|__|__
1  |ql|__|__|__|__|__|__|__
|Solução única III
}}
</td>
<td>
{{Diagrama de xadrez pequeno
| tright
|
8  |__|__|__|ql|__|__|__|__
7  |__|__|__|__|__|ql|__|__
6  |__|__|__|__|__|__|__|ql
5  |__|__|ql|__|__|__|__|__
4  |ql|__|__|__|__|__|__|__
3  |__|__|__|__|__|__|ql|__
2  |__|__|__|__|ql|__|__|__
1  |__|ql|__|__|__|__|__|__
|Solução única IV
}}
</td>
</tr>
<tr>
<td>
{{Diagrama de xadrez pequeno
| tright
|
8  |__|__|ql|__|__|__|__|__
7  |__|__|__|__|__|ql|__|__
6  |__|__|__|__|__|__|__|ql
5  |ql|__|__|__|__|__|__|__
4  |__|__|__|ql|__|__|__|__
3  |__|__|__|__|__|__|ql|__
2  |__|__|__|__|ql|__|__|__
1  |__|ql|__|__|__|__|__|__
|Solução única V
}}
</td>
<td>
{{Diagrama de xadrez pequeno
| tright
|
8  |__|__|__|__|ql|__|__|__
7  |__|__|ql|__|__|__|__|__
6  |__|__|__|__|__|__|__|ql
5  |__|__|__|ql|__|__|__|__
4  |__|__|__|__|__|__|ql|__
3  |ql|__|__|__|__|__|__|__
2  |__|__|__|__|__|ql|__|__
1  |__|ql|__|__|__|__|__|__
|Solução única VI
}}
</td>
<td>
{{Diagrama de xadrez pequeno
| tright
|
8  |__|__|__|__|ql|__|__|__
7  |__|__|__|__|__|__|ql|__
6  |__|__|__|ql|__|__|__|__
5  |ql|__|__|__|__|__|__|__
4  |__|__|ql|__|__|__|__|__
3  |__|__|__|__|__|__|__|ql
2  |__|__|__|__|__|ql|__|__
1  |__|ql|__|__|__|__|__|__
|Solução única VII
}}
</td>
<td>
{{Diagrama de xadrez pequeno
| tright
|
8  |__|__|__|ql|__|__|__|__
7  |ql|__|__|__|__|__|__|__
6  |__|__|__|__|ql|__|__|__
5  |__|__|__|__|__|__|__|ql
4  |__|__|__|__|__|ql|__|__
3  |__|__|ql|__|__|__|__|__
2  |__|__|__|__|__|__|ql|__
1  |__|ql|__|__|__|__|__|__
|Solução única VIII
}}
</td>
</tr>
<tr>
<td>
{{Diagrama de xadrez pequeno
| tright
|
8  |__|__|ql|__|__|__|__|__
7  |__|__|__|__|__|ql|__|__
6  |__|__|__|ql|__|__|__|__
5  |ql|__|__|__|__|__|__|__
4  |__|__|__|__|__|__|__|ql
3  |__|__|__|__|ql|__|__|__
2  |__|__|__|__|__|__|ql|__
1  |__|ql|__|__|__|__|__|__
|Solução única IX
}}
</td>
<td>
{{Diagrama de xadrez pequeno
| tright
|
8  |__|__|__|__|__|ql|__|__
7  |__|ql|__|__|__|__|__|__
6  |__|__|__|__|__|__|ql|__
5  |ql|__|__|__|__|__|__|__
4  |__|__|__|ql|__|__|__|__
3  |__|__|__|__|__|__|__|ql
2  |__|__|__|__|ql|__|__|__
1  |__|__|ql|__|__|__|__|__
|Solução única X
}}
</td>
<td>
{{Diagrama de xadrez pequeno
| tright
|
8  |__|__|__|ql|__|__|__|__
7  |__|__|__|__|__|__|ql|__
6  |ql|__|__|__|__|__|__|__
5  |__|__|__|__|__|__|__|ql
4  |__|__|__|__|ql|__|__|__
3  |__|ql|__|__|__|__|__|__
2  |__|__|__|__|__|ql|__|__
1  |__|__|ql|__|__|__|__|__
|Solução única XI
}}
</td>
<td>
{{Diagrama de xadrez pequeno
| tright
|
8  |__|__|__|__|__|ql|__|__
7  |__|__|__|ql|__|__|__|__
6  |__|__|__|__|__|__|ql|__
5  |ql|__|__|__|__|__|__|__
4  |__|__|__|__|__|__|__|ql
3  |__|ql|__|__|__|__|__|__
2  |__|__|__|__|ql|__|__|__
1  |__|__|ql|__|__|__|__|__
|Solução única XII
}}
</td>
</tr>
</table>A solução X possui a propriedade adicional de não possuir três rainhas em uma mesma linha reta.

== Construindo uma solução ==
Encontrar uma solução para este problema não é assim tão fácil. Utilizando [[análise combinatória]] podemos perceber que existem 
:<math>C^{64}_8 = {64\choose 8} =  4426165368</math>
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 é:  
:<math>P\left[A\right]=92/4426165368 </math>

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:
:<math>{8!}=40320</math>
e a probabilidade do evento '''A''' ocorrer seria de:
:<math>P\left[A\right]=92/40320 </math>
que é consideravelmente maior.

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

[[Ficheiro: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.

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.<ref>{{Citar web|ultimo=Nield|primeiro=David|url=https://www.sciencealert.com/a-harvard-mathematician-has-solved-an-epic-150-year-old-chess-problem|titulo=A Harvard Mathematician Has Basically Solved an Epic, 150-Year-Old Chess Problem|acessodata=2022-02-08|website=ScienceAlert|lingua=en-gb}}</ref>

{{Referências}}

{{Portal3|Enxadrismo|Matemática}}

[[Categoria:Problemas matemáticos]]
[[Categoria:Matemática sobre xadrez]]
[[Categoria:Jogos matemáticos]]
[[Categoria:Oito]]