Machine Learning - Atividade 3

Prévia do material em texto

Discente: Heloísa Helena Lopes Alvarenga
O problema das oito rainhas é um problema matemático, onde de acordo com as
regras do xadrez, devemos posicionar oito rainhas num tabuleiro de xadrez, de maneira a
que nenhuma das rainhas seja atacada por outra. Para que tal aconteça, as rainhas não
devem ocupar as mesmas colunas, linhas e diagonais em simultâneo.
Este problema terá sido proposto por Max Bezzel em 1848, e acabou por ser
analisado por diversos matemáticos. Não demorou muito até que a primeira solução fosse
proposta, o qual tomou data em 1850 por Franz Nauck, este acabou por criar soluções
para outras quantidades de rainhas, generalizando-o como problema das n rainhas. 
A solução para o problema das 8 rainhas conta com 92 soluções, estando uma
delas demonstrada na figura abaixo:
Nesse contexto, a heurística é a contabilidade 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 é a heurística que não superestima o custo
de um estado até a origem e respeita a regra:
• onde h(x) é uma 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.
De modo a simplificar o problema ao máximo iremos optar pelo caminho da força
bruta viável. Sendo assim, teremos as seguinte opções:
1) Averiguar todas possíveis posições para as 8 rainhas. Um tabuleiro 8x8 tem 64
posições, logo para a primeira rainha temos 64 possibilidades, para a segunda 63,
e por ai fora. Assim, o número de combinações de 64 elementos tomados de 8 a 8
será:
C64,8= 64 !
8 !∗(64−8)!
= 64 !
8 !∗56 !
=4426165368
2) Se introduzirmos uma nova variável e dissermos que cada rainha tem de ocupar
uma coluna diferente, teremos o seguinte:
• A rainha 1 tem 8 linhas para ocupar na coluna 1,
• A rainha 2 tem 8 linhas para ocupar na coluna 2,
• …
• A rainha 8 tem 8 linhas para ocupar na coluna 8.
No total obtemos 8⁸ = 16777216.
3) Vamos reduzir o espaço de busca ainda mais sabendo que as rainhas não podem
ocupar a mesma linha.
• A rainha 1 tem 8 linhas para ocupar na coluna A,
• A rainha 2 tem 7 linhas para ocupar na coluna B,
• ...
• A rainha 8 tem 1 linha para ocupar na coluna H.
No total obtemos 8! = 40320, ou seja, o número de trocas entre 8 elementos.
Uma vez que o terceiro método se revelou o mais eficiente, iremos eligi-lo como
base para solucionar o nosso problema, agregando-o assim ao código que gera as trocas
dos elementos de um vetor. Cada troca deve ser verificada pelo programa uma vez que
pode gerar uma das 92 soluções para o nosso problema. Uma vez que o nosso terceiro
método já concretiza a exclusão de outras rainhas na mesma coluna ou linha, apenas nos
resta verificar as diagonais.
Considerando uma matriz do tabuleiro 8x8, com índices de um a oito nas linhas e
de A a H nas colunas. Cada combinação das rainhas no tabuleiro é representada por um
vetor int linhas[8], onde a enésima rainha n ocupa a posição (x,y)=(n-1, linhas[n-1]) do
tabuleiro.
• A rainha 1 ocupa a posição (A, linhas[0]),
• A rainha 2 ocupa a posição (B, linhas[1]),
• …
• A rainha 8 ocupa a posição (H, linhas[8]).
Por exemplo, o vetor int linhas[8] = {1, 2, 3, 4, 5, 6, 7, 8}; corresponde a seguinte
configuração:
Obtemos assim uma pesquisa pela solução muito mais eficaz devido ao facto de
termos simplificado ao máximo as nossas variáveis de busca.