Problema das 8 Rainhas:

É possível colocar 8 rainhas do jogo de xadrez sobre o tabuleiro de modo que nenhuma das rainhas possa atacar outra? O programa abaixo encontra todas as 92 soluções do problema por busca exaustiva (força bruta). Uma das soluções é mostrada abaixo:

♛
♛
♛
♛
♛
♛
♛
♛

Com base nas informações do problema, vamos tentar reduzir o máximo possível o espaço de busca de modo a tornar a solução por força bruta viável. Abaixo discutimos algumas opções:

  1. Testar todas possíveis posições das rainhas: Um tabuleiro 8x8 tem 64 posições. Para a primeira rainha temos 64 possibilidades, para a segunda 63, para a terceira 62, ... Logo temos 64*63*62*61*60*59*58*57/8! = C64,8, ou seja, o número de combinações de 64 elementos tomados 8 a 8. C64,8 = 64!/(8!*(64-8)!) = 64!/(8!*56!) = 4426165368. Espaço de busca grande demais!
  2. Vamos reduzir o espaço de busca sabendo que as rainhas ocupam diferentes colunas (numeradas de zero a sete). No total temos 88 = 16777216.
  3. Vamos reduzir o espaço de busca ainda mais sabendo que as rainhas não podem ocupar a mesma linha. No total temos 8! = 40320, ou seja, o número de permutações de 8 elementos. Esse espaço de busca pode ser rapidamente testado por um programa de computador.

Resolução:

Adotamos o espaço de busca da terceira opção, tendo como base o código que gera as permutações dos elementos de um vetor. Cada permutação corresponde a uma solução candidata que deve ser verificada pelo programa. Como, por construção, os elementos do espaço de busca da terceira opção já satisfazem as restrições em linhas e colunas, só falta verificar as restrições nas diagonais.

Considere uma matriz do tabuleiro 8x8, com índices de zero a sete nas linhas e colunas. Cada possível configuração das rainhas no tabuleiro, dentro do espaço de busca considerado, é representada por um vetor int linhas[8];, onde a i-ésima rainha Ri ocupa a posição (x,y)=(i-1, linhas[i-1]) do tabuleiro.

Por exemplo, o vetor int linhas[8] = {0, 1, 2, 3, 4, 5, 6, 7}; corresponde a seguinte configuração:

♛
♛
♛
♛
♛
♛
♛
♛
O programa abaixo testa todas as 8! permutações dos elementos do vetor linhas e imprime todas as soluções do problema.

Funções auxiliares:

Para gerar as permutações do vetor, precisamos de uma função auxiliar que troca/inverte dois elementos de um vetor: 
void Troca(int v[], int i, int j) {
  int tmp;
  tmp = v[i]; 
  v[i] = v[j]; 
  v[j] = tmp;
}
Também precisamos de uma função que verifica se uma dada permutação do vetor linhas corresponde a uma solução do problema. Para isso, precisamos verificar as diagonais. 
int SolucaoValida(int linhas[]){
  int i;
  int x,y;
  int xx,yy;

  for(i = 0; i < 8; i++){
    x = i;
    y = linhas[i];

    xx = x;
    yy = y;
    while(1){
      xx += 1;
      yy -= 1;
      if(xx > 7 || yy < 0) break;
      
      if(yy == linhas[xx]) 
        return 0;
    }

    xx = x;
    yy = y;
    while(1){
      xx -= 1;
      yy -= 1;
      if(xx < 0 || yy < 0) break;
      
      if(yy == linhas[xx]) 
        return 0;
    }
  }
  return 1;
}
Precisamos também de uma função para imprimir as soluções encontradas: 
void ImprimeSolucao(int linhas[]){
  char tabuleiro[8][8];
  int i,j;
  int x,y;
  static int nsols = 0;

  nsols++;

  printf("******** SOL: %d ********\n",nsols);

  for(i = 0; i < 8; i++)
    for(j = 0; j < 8; j++)
      tabuleiro[i][j] = '.';

  for(i = 0; i < 8; i++){
    x = i;
    y = linhas[i];
    tabuleiro[y][x] = 'R';
  }

  for(i = 0; i < 8; i++){
    for(j = 0; j < 8; j++){
      printf(" %c ",tabuleiro[i][j]);
    }    
    printf("\n");
  }
}

Testando as permutações:

Iniciamos com a construção do vetor int linhas[8] = {0, 1, 2, 3, 4, 5, 6, 7};, e, em seguida, chamamos a função recursiva TestaPermutacoes, responsável por gerar as permutações, iniciando no índice zero (segundo parâmetro da função). 
void Solucoes8Rainhas() {
  int linhas[8];
  int i;
  for(i = 0; i < 8; i++)
    linhas[i] = i;
  TestaPermutacoes(linhas, 0);
}
Na função TestaPermutacoes, os elementos com índices menores que k estão fixos. A função deve gerar as permutações dos elementos com índices maiores ou iguais a k. Se k=8, então todos elementos estão fixos e o vetor deve ser verificado e impresso (caso trivial). Caso contrário, fixamos um novo elemento na posição k e testamos as permutações a partir do índice k+1. Repetimos esse processo fixando todos os possíveis elementos na posição k. 
void TestaPermutacoes(int linhas[], int k) {
  int i;
  
  if(k == 8) {
    if(SolucaoValida(linhas))
      ImprimeSolucao(linhas);
  }
  else{
    for(i = k; i < 8; i++) {
      Troca(linhas, k, i);
      TestaPermutacoes(linhas, k + 1);
      Troca(linhas, i, k);
    }
  }
}

Exemplo de programa principal:

#include <stdio.h>
#include <stdlib.h>

/*Colocar aqui as funções anteriores*/
...

int main(){
  Solucoes8Rainhas();
  return 0;
}