Problema das oito damas

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

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

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.

r=N-1

A quantidade de estados Ns é dada por:

N_{s}^{i}=D*N*r

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

{\begin{array}{l}N_{s}^{i+1}=D*(N+1)*(r+1)\\N_{s}^{i+1}=D*(N*r+(N+r)+1)\end{array}}

Então a distância de estados $D_{e}$ de i para i+1 é:

D_{e}=D*((N+r)+1)

de i para um k qualquer:

D_{e}=D*(k-i)*(N+r)+D*(k-i)

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

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.

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)\leq c(x,y)+h(y)

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:

N_{s}^{i}=D*N*r

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

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:

$P(x,y)={\frac {\sum _{i=0}^{N}Q_{\rightarrow (x,y)}^{i}}{N}}$

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 $K(x,y)$ é :

$K(x,y)=\sum _{i=0}^{N}-P(x,y)\log _{2}P(x,y)$

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:

8

	a	b	c	d	e	f	g	h
8									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									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									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									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									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									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									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									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									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									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									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									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

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

C_{8}^{64}={64 \choose 8}=4426165368

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 é:

P\left[A\right]=92/4426165368

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:

{8!}=40320

e a probabilidade do evento A ocorrer seria de:

P\left[A\right]=92/40320

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

↑ 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
↑ ^a ^b Russell, S. J. and Norvig, P. 1995 Artificial Intelligence: a Modern Approach. Prentice-Hall, Inc.
↑ Luger, G. F. 1997 Artificial Intelligence: Structures and Strategies for Complex Problem Solving. 3rd. Addison-Wesley Longman Publishing Co., Inc.
↑ 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

[1] ublished, 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

[Russel-2] Russell, S. J. and Norvig, P. 1995 Artificial Intelligence: a Modern Approach. Prentice-Hall, Inc.

[Luger-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

[1]

[2]

[3]

[4]