O objetivo deste exercício-programa é o de implementar e estudar o comportamento de algumas variações do algoritmo de satisfação de restrições (CSP) visto em sala de aula. O problema que será resolvido é o das 8-rainhas.

Problema: dispor 8 rainhas em um tabuleiro de chadrez de modo que nenhuma rainha ataque a outra.

Você deve formular o problema como CSP, da seguinte forma:

• Variáveis: Qi, i = 1..8 (rainha da coluna i)
• Domínios: Di = 1 .. 8 (linhas possíveis para a rainha da colina i)
• Restrições:

Qi ¹ Qj (não pode estar na mesma linha)
|Qi - Qj| ¹ |i - j| (ou mesma diagonal)

• Estado: conjunto de variáveis com seus valores associados
• Estado inicial: todas as variáveis sem nenhum valor associado
• Operadores: atribuição de valores a uma variável por vez (a escolha de qual variável será instanciada a cada expansão é determinada pelas estratégias descritas abaixo)
• Teste do goal: verifica se todas as variáveis possuem valores e se todas as restrições são satisfeitas

(a)  Escolha qualquer linha (valor) da próxima coluna. Essa é a estratégia de busca em profundidade geral. DFS gera todos os sucessores possíveis de cada nó inserindo-os no início da lista e aplica o teste do goal em cada nó visitado. Note que desta maneira violações individuais não são tratadas.

(b) Escolha qualquer linha não ameaçada da próxima coluna. Essa também é uma estratégia de busca em profundidade geral mas que gera somente sucessores que descrevam estados sem violação de restrições. Ocorre uma falha sempre que não for possível gerar sucessores de um nó sem violação e, neste caso, o algoritmo expande o próximo nó da lista.

(c) Escolha qualquer linha não ameaçada da próxima coluna mas faça BACKTRACKING  (o algoritmo DFS falha e seleciona o próximo nó da lista de sucessores) se alguma coluna à direita não possuir mais nenhuma linha não ameaçada (ou seja, se restar alguma coluna com todas suas linhas ameaçadas). Essa é estratégia forward checking (sem uso de heurísticas) e que verifica se algum domínio das variáveis restantes se tornou vazio, para isso, essa estratégia deve fazer a "manutenção" dos domínios de cada variável.

(d) Escolha a COLUNA que estiver MAIS ameaçada e em seguida escolha a linha que gera menos ameaças às colunas restantes. Essa é a estratégia forward checking (estratégia c) melhorada com a aplicação das seguintes heurísticas de CSP:

Você deverá entregar um relatório comparando o desempenho das estratégias acima. Para isso, você deve contar o número de nós gerados durante a execução de todas as estratégias.

Dicas:

• Para as estratégias (a), (b) e (c), você deve implementar o algoritmo de busca em profundidade visto em aula, gerando todos os sucessores de um nó de uma vez e inserindo-os na lista de nós ainda não expandidos.

• A estratégia (d)  pode ser implementada da seguinte maneira: DFS gera todos os sucessores de uma vez e antes de inseri-los na lista ordena-os de acordo com as heurísticas h1 e h2.