O Problema das N-Rainhas

Objectivo

Familiarizar os alunos com a sincronização e comunicação entre processos em arquitecturas multiprocessador, através da utilização de spinlocks e do mapeamento de ficheiros em memória partilhada.

Descrição

Desenvolver uma aplicação que permita resolver em paralelo o problema das N-rainhas. O problema das N-rainhas consiste em encontrar todas as combinações possíveis de N rainhas num tabuleiro de dimensão N por N tal que nenhuma das rainhas ataque qualquer outra. Duas rainhas atacam-se uma à outra quando estão na mesma linha, na mesma coluna ou na mesma diagonal do tabuleiro. Na figura que se segue pode ver-se as posições atacadas por uma rainha colocada num tabuleiro de dimensão 7 por 7 e ao lado uma possível solução para esse mesmo tabuleiro.

Implementação

Como o número de rainhas é igual às dimensões do tabuleiro, é obrigatório ter sempre uma rainha por cada linha do tabuleiro. Sendo assim, a posição das rainhas no tabuleiro pode ser representada por um vector de N linhas que a cada linha associa a coluna em que a rainha está colocada nessa linha. Como sugestão, considere a estrutura que se segue para representar essa informação:
```
typedef struct {
  char len;        // número de rainhas colocadas no tabuleiro
  char queens[N];  // posição (número da coluna) das rainhas
} board;
```
Um procedimento sistemático de colocar as N rainhas no tabuleiro é começar pela primeira linha e considerar as N posições disponíveis. Depois, para cada uma das posições da primeira linha, considerar as posições da segunda linha que não levam a situações de ataque. Aplicando esta ideia repetidamente às restantes linhas, no final obtemos o conjunto de todas as soluções possíveis. No entanto, à medida que vamos percorrendo as linhas é necessário ir guardando as combinações intermédias que são válidas. Uma forma de fazer isso é utilizar uma fila de tarefas onde se vão colocando essas combinações.
A partir do seguinte esqueleto de código comece por implementar uma versão sequencial da fila de tarefas. De seguida, implemente uma primeira versão paralela em que os diferentes processos sincronizam nas duas operações de acesso à fila.
Por fim, extenda a versão paralela para suportar filas de tarefas múltiplas associadas a grupos de processos. Cada grupo de processos apenas consome itens da sua fila de tarefas, mas distribui alternadamente as suas combinações intermédias por todas as filas numa estratégia de round-robin.