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.

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:

Começo de um tabuleiro de xadrez. a b c d e f g h
8 dama branca em d8 8
7 dama branca em g7 7
6 dama branca em c6 6
5 dama branca em h5 5
4 dama branca em b4 4
3 dama branca em e3 3
2 dama branca em a2 2
1 dama branca em f1 1
a b c d e f g h Fim do tabuleiro de xadrez.
Solução única I
Começo de um tabuleiro de xadrez. a b c d e f g h
8 dama branca em e8 8
7 dama branca em b7 7
6 dama branca em d6 6
5 dama branca em g5 5
4 dama branca em c4 4
3 dama branca em h3 3
2 dama branca em f2 2
1 dama branca em a1 1
a b c d e f g h Fim do tabuleiro de xadrez.
Solução única II
Começo de um tabuleiro de xadrez. a b c d e f g h
8 dama branca em d8 8
7 dama branca em b7 7
6 dama branca em g6 6
5 dama branca em c5 5
4 dama branca em f4 4
3 dama branca em h3 3
2 dama branca em e2 2
1 dama branca em a1 1
a b c d e f g h Fim do tabuleiro de xadrez.
Solução única III
Começo de um tabuleiro de xadrez. a b c d e f g h
8 dama branca em d8 8
7 dama branca em f7 7
6 dama branca em h6 6
5 dama branca em c5 5
4 dama branca em a4 4
3 dama branca em g3 3
2 dama branca em e2 2
1 dama branca em b1 1
a b c d e f g h Fim do tabuleiro de xadrez.
Solução única IV
Começo de um tabuleiro de xadrez. a b c d e f g h
8 dama branca em c8 8
7 dama branca em f7 7
6 dama branca em h6 6
5 dama branca em a5 5
4 dama branca em d4 4
3 dama branca em g3 3
2 dama branca em e2 2
1 dama branca em b1 1
a b c d e f g h Fim do tabuleiro de xadrez.
Solução única V
Começo de um tabuleiro de xadrez. a b c d e f g h
8 dama branca em e8 8
7 dama branca em c7 7
6 dama branca em h6 6
5 dama branca em d5 5
4 dama branca em g4 4
3 dama branca em a3 3
2 dama branca em f2 2
1 dama branca em b1 1
a b c d e f g h Fim do tabuleiro de xadrez.
Solução única VI
Começo de um tabuleiro de xadrez. a b c d e f g h
8 dama branca em e8 8
7 dama branca em g7 7
6 dama branca em d6 6
5 dama branca em a5 5
4 dama branca em c4 4
3 dama branca em h3 3
2 dama branca em f2 2
1 dama branca em b1 1
a b c d e f g h Fim do tabuleiro de xadrez.
Solução única VII
Começo de um tabuleiro de xadrez. a b c d e f g h
8 dama branca em d8 8
7 dama branca em a7 7
6 dama branca em e6 6
5 dama branca em h5 5
4 dama branca em f4 4
3 dama branca em c3 3
2 dama branca em g2 2
1 dama branca em b1 1
a b c d e f g h Fim do tabuleiro de xadrez.
Solução única VIII
Começo de um tabuleiro de xadrez. a b c d e f g h
8 dama branca em c8 8
7 dama branca em f7 7
6 dama branca em d6 6
5 dama branca em a5 5
4 dama branca em h4 4
3 dama branca em e3 3
2 dama branca em g2 2
1 dama branca em b1 1
a b c d e f g h Fim do tabuleiro de xadrez.
Solução única IX
Começo de um tabuleiro de xadrez. a b c d e f g h
8 dama branca em f8 8
7 dama branca em b7 7
6 dama branca em g6 6
5 dama branca em a5 5
4 dama branca em d4 4
3 dama branca em h3 3
2 dama branca em e2 2
1 dama branca em c1 1
a b c d e f g h Fim do tabuleiro de xadrez.
Solução única X
Começo de um tabuleiro de xadrez. a b c d e f g h
8 dama branca em d8 8
7 dama branca em g7 7
6 dama branca em a6 6
5 dama branca em h5 5
4 dama branca em e4 4
3 dama branca em b3 3
2 dama branca em f2 2
1 dama branca em c1 1
a b c d e f g h Fim do tabuleiro de xadrez.
Solução única XI
Começo de um tabuleiro de xadrez. a b c d e f g h
8 dama branca em f8 8
7 dama branca em d7 7
6 dama branca em g6 6
5 dama branca em a5 5
4 dama branca em h4 4
3 dama branca em b3 3
2 dama branca em e2 2
1 dama branca em c1 1
a b c d e f g h Fim do tabuleiro de xadrez.
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

C^{64}_8 = {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.

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.