Problema das oito damas

 Por: Rogerio Santos    19:32     Sem Comentarios

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).


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

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:

8! = 40320

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.

Todas as Soluções

FONTE: Wikipédia