Oito rainhas. Outro desafio para os jogadores de xadrez é o problema das Oito Rainhas. Resumindo: é possível colocar oito rainhas em um tabuleiro vazio de modo que nenhuma rainha esteja ‘atacando’ qualquer outra – ou seja, de modo que duas rainhas nunca estejam na mesma linha, na mesma coluna ou na mesma diagonal? Use o tipo de raciocínio desenvolvido no Exercício 6.24 para formular uma heurística para a solução do problema das Oito Rainhas. Execute seu programa. [Dica: é possível atribuir um valor numérico a cada quadrado do tabuleiro, indicando quantos quadrados de um tabuleiro vazio são ‘eliminados’ quando uma rainha é colocada nesse quadrado. Por exemplo, cada um dos quatro cantos receberia o valor 22, como mostra a Figura 6.26.]

Quando esses ‘números de eliminação’ são colocados em todos os 64 quadrados, uma heurística apropriada poderia ser: coloque a próxima rainha no quadrado com o menor número de eliminação. Por que essa estratégia é intuitivamente atraente?

Passo 1

Beleza meus bacanos, espero que todos esteja bem e dispostos a estudar hoje pois nossa questão é bem longa. Abram seu compilador para evitar se perder e sigam todos os passos. Vamos nessa!

Teremos 6 funções importantes. Em primeiro lugar, a função EightQueens executará a abordagem heurística enquanto houver um movimento disponível.

A função heurística atribuirá um valor heurístico a cada quadrado no tabuleiro usando a função assignValue.

Passo 2

A função assignValue tem 4 parâmetros, a placa, a linha e a coluna. O último parâmetro é marca. Se quisermos marcar as casas marcadas pela rainha naquela linha e coluna, definimos mark como 1, caso contrário, definimos mark como 0.

A função assignValue:

Passo 3

A função checkDiagonals verifica os quadrados diagonais, usando 2 variáveis:

// movimento vertical para diagonais

int vertical[4] = {-1, -1, 1, 1};

// movimento horizontal para diagonais

int horizontal[4] = {-1, 1, -1, 1};

A combinação destes dois corresponde a cada uma das 4 diagonais.

O código da função:

As funções checkVertical e checkHorizontal:

// verifica os quadrados horizontais a partir do quadrado mais à esquerda

// verifica os quadrados verticais a partir do quadrado mais à esquerda

Finalmente, a função placeQueen:

Resposta

Ver o desenvolvimento!