EP 8 rainhas do Bira

No curso de Computação II da Turma 14, o professor Gubi deu um EP sobre o problema das 8 rainhas. Esse é o código produzido pelo Bira, seu atual orientando.

/* p/ compilar: gcc -o rainhas  -Wall rainhas.c */
 
/* DESCRIÇÃO DO PROBLEMA: acomodar oito rainhas (peças de xadrez) num tabuleiro com lado também de 8 oito casas de modo que nenhuma das damas fique em posição de ser atacada ou atacar outras damas.
Isso é possível? Sabe-se que sim. Este programa tem o propósito de mapear todas as soluções possíveis para o problema.


Consegui também achar um jeito de comparar as soluções entre si de modo a agrupá-las determinar quais são as soluções quer não guardam entre si relações de simetria. Quando falo em simetria, quero dizer que, imaginando um tabuleiro transparente(de acrílico, por exemplo)  que contenha damas grudadas nele (com superbonder, durepóxi ou chiclete, por exemplo) de modo que não caiam facilmente quando mexemos e viramos o tabuleiro, se a distribuição das rainhas pelo tabuleiro for uma solução para o problema, então podemos obter outras soluções para o problema apenas girando o tabuleiro em torno do eixo normal ao seu plano.

A imagem especular de cada uma dessas quatro soluções encontradas (a original e seus giros) também é uma solução para o problema, de modo que temos na verdade 8 soluções simétricas (às quais chamo "grupo de simetria") para cada solução encontrada que não guarde simetria com outras soluções (fora as do seu grupo de simetria). Tentei ilustrar esses grupos de simetria graficamente nos 8 tabuleiros abaixo (usando a mesma notação do xadrez, ou algo parecido), onde cada tabuleiro de baixo é a imagem especular do que está em cima (e vice-versa, claro) e cada tabuleiro equivale ao giro anti-horário do tabuleiro à sua esquerda.


GRUPO DE SIMETRIA

   A B C D E F G H        1 2 3 4 5 6 7 8        H G F E D C B A        8 7 6 5 4 3 2 1
  _________________      _________________      _________________      _________________
1 |_|@|_|@|_|@|_|@|    H |@|_|@|_|@|_|@|_|    8 |_|@|_|@|_|@|_|@|    A |@|_|@|_|@|_|@|_|
2 |@|_|@|_|@|_|@|_|    G |_|@|_|@|_|@|_|@|    7 |@|_|@|_|@|_|@|_|    B |_|@|_|@|_|@|_|@|
3 |_|@|_|@|_|@|_|@|    F |@|_|@|_|@|_|@|_|    6 |_|@|_|@|_|@|_|@|    C |@|_|@|_|@|_|@|_|
4 |@|_|@|_|@|_|@|_|    E |_|@|_|@|_|@|_|@|    5 |@|_|@|_|@|_|@|_|    D |_|@|_|@|_|@|_|@|
5 |_|@|_|@|_|@|_|@|    D |@|_|@|_|@|_|@|_|    4 |_|@|_|@|_|@|_|@|    E |@|_|@|_|@|_|@|_|
6 |@|_|@|_|@|_|@|_|    C |_|@|_|@|_|@|_|@|    3 |@|_|@|_|@|_|@|_|    F |_|@|_|@|_|@|_|@|
7 |_|@|_|@|_|@|_|@|    B |@|_|@|_|@|_|@|_|    2 |_|@|_|@|_|@|_|@|    G |@|_|@|_|@|_|@|_|
8 |@|_|@|_|@|_|@|_|    A |_|@|_|@|_|@|_|@|    1 |@|_|@|_|@|_|@|_|    H |_|@|_|@|_|@|_|@|


   H G F E D C B A        8 7 6 5 4 3 2 1        A B C D E F G H        1 2 3 4 5 6 7 8
  _________________      _________________      _________________      _________________
1 |_|@|_|@|_|@|_|@|    H |@|_|@|_|@|_|@|_|    8 |_|@|_|@|_|@|_|@|    A |@|_|@|_|@|_|@|_|
2 |@|_|@|_|@|_|@|_|    G |_|@|_|@|_|@|_|@|    7 |@|_|@|_|@|_|@|_|    B |_|@|_|@|_|@|_|@|
3 |_|@|_|@|_|@|_|@|    F |@|_|@|_|@|_|@|_|    6 |_|@|_|@|_|@|_|@|    C |@|_|@|_|@|_|@|_|
4 |@|_|@|_|@|_|@|_|    E |_|@|_|@|_|@|_|@|    5 |@|_|@|_|@|_|@|_|    D |_|@|_|@|_|@|_|@|
5 |_|@|_|@|_|@|_|@|    D |@|_|@|_|@|_|@|_|    4 |_|@|_|@|_|@|_|@|    E |@|_|@|_|@|_|@|_|
6 |@|_|@|_|@|_|@|_|    C |_|@|_|@|_|@|_|@|    3 |@|_|@|_|@|_|@|_|    F |_|@|_|@|_|@|_|@|
7 |_|@|_|@|_|@|_|@|    B |@|_|@|_|@|_|@|_|    2 |_|@|_|@|_|@|_|@|    G |@|_|@|_|@|_|@|_|
8 |@|_|@|_|@|_|@|_|    A |_|@|_|@|_|@|_|@|    1 |@|_|@|_|@|_|@|_|    H |_|@|_|@|_|@|_|@|



O que se poderia esperar disso é que o número de total soluções (incluindo as simétricas entre si) fosse múltiplo de oito, pois cada assimétrica daria origem a oito soluções, mas não é isso que em geral acontece. As soluções assimétricas do problema para 8 rainhas, por exemplo, são 12. 12*8=96, mas apenas 92 soluções existem para esse problema.

Isso pode ser explicado pela existência de soluções que quando giradas e/ou rebatidas especularmente um número certo de vezes (que não seja, obviamente múltiplo de 4 para os giros ou de 2 para o rebatimento, porque aí é óbvio que resulta na mesma solução) resultam em soluções idênticas a ela. Ou seja, ocorrem às vezes, no grupo das 8 soluções simétricas, soluções simétricas idênticas, que chamarei a partir de agora de "soluções redundantes" ou, simplesmente, "redundâncias". O total de soluções TS passa então a ser 

 TS = 8*AS -RD

onde AS é o total de solução assimétricas(entre si)  e RD é o somatório das soluções redundantes de todos os grupos de simetria gerado pelas soluções assimétricas.

Q que eu gostaria de ter conseguido fazer, mas não consegui até agora, é recostruir o conjunto total de soluções a partir do conjunto das soluções assimétricas e do conhecimento de quais soluções são redundantes. Pareceu-me fácil inicialmente mas, depois de tentar fazer isso de 3 maneiras diferentes, desisti.

*/

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


#define LADOTAB 8
/* número que corresponde ao lado do tabuleiro e quantidade de rainhas o programa funciona com LADOTAB de 1 a 10. 
Acima de 10 ocorre segmentation fault na execução. Não consegui identificar a causa. Abaixo de 1 creio que não faz muito sentido. Não há solução nenhuma para 2 nem 3 e a solução de 1 é trivial.*/

#define NSOL 750
/* número máximo para o total das soluções que se pode encontrar.
Para LATOTAB=10, TS=724 e há 12 redundâncias, então 750 é um número razoável e econômico para o intervalo em que estamos trabalhando. Testei LADOTAB=11 com NSOL valendo potências de 10 progressivamete maiores, até 1000000, mas continuou dando segmentation fault */


/* VARIÁVEIS GLOBAIS */
int n_solacum=0; // número de soluções acumuladas num dado momento

int solacum[NSOL][LADOTAB]; //matriz na qual cada linha menor que n_solacum  corresponde a uma solução do problema

int solucao_em_teste[LADOTAB];//vetor onde está sendo analisada uma solução, neste programa toda solução particular corresponde a um vetor de tamanho LADOTAB, onde os índices correspondem às linhas do tabuleiro e os valores correspondem às colunas

int octeto[8][LADOTAB];//octeto[0][0~LADOTAB-1](a 1a. linha da matriz) recebe uma solução e a função "criaocteto" gera todas as simétricas daquela solução no resto da matriz. Em outras palavras, um octeto montado por essa função e um grupo de simetria são a mesma coisa.

char simetria='U';//para o usuário dizer se que ou não ver todas as soluções, inclusive as simétricas



/* PROTÓTIPOS DAS FUNÇÕES CRIADAS - COMEÇO */

// GERAÇÃO DE SOLUÇÕES
void percorre(int, int);
//função principal. Recursiva. É ela que avança pelo tabuleiro, testando soluções.

void volta(int);
//função auxiliar de percorre, volta para a linha anterior do tabuleiro quando a atual se esgota. Recursiva quando a linha anterior também está em sua última coluna

int testavalor(int, int);// testa se é possível colocar uma rainha numa dada posição do tabuleiro



// ESTUDOS DE SIMETRIA E REDUNDÂNCIA
void elimina_simetricas();//estuda a solução mais recentemente encontrada, testando-a para ver se é simétrica em relação a alguma das soluções mais antigas

void criaocteto(int *);
//função central para lidar com soluções simétricas. Gera o grupo de simetria da solução recebida

void descobre_redundancias();
// examinando os grupos de simetria, descobre simetrias redundantes dentro deles


// IMPRESSÃO DE SOLUÇÕES
void imprime();//imprime as soluções encontradas

/* PROTÓTIPOS DAS FUNÇÕES CRIADAS - FIM */


int main(){
  puts("digite 's' ou 'S' para ver todas as soluções, inclusive as simétricas.\nOu digite qualquer outra tecla se quiser ver somente as soluções assimétricas e as redundantes");
  simetria=getchar();
  percorre(0, 0);//a função percorre tem como argumentos dois int's que correspondem às coordenadas (no tabuleifo) a partir das quais se quer que a função percorra o tabuleiro
  imprime();
  if(n_solacum){
    if(!(simetria=='s' || simetria=='S')) descobre_redundancias();
  }
  else if(!LADOTAB) puts("Olha, não faz o MENOR SENTIDO uma pessoa querer acomodar zero damas num tabuleiro de lado zero!\n");
  else if(LADOTAB<0){
    puts("Você definiu LADOTAB como um número negativo??? Como foi que você conseguiu compilar? Pior ainda, como o programa pôde chegar até este ponto e imprimir esta mensagem?\n\n\nFalha catastrófica! Este PC atingirá massa crítica e explodirá em 13 segundos... corra por sua vida!!\n");
    exit(EXIT_FAILURE);
  }
  else printf("Não é possível acomodar %d damas num tabuleiro de lado %d de modo que nenhuma delas ataque ou seja atacada.\n\n", LADOTAB, LADOTAB);
  return 0;
}



/* GERAÇÃO DE  SOLUÇÕES - COMEÇO */

void percorre(int nivel, int coluna){
  int j;
  for(; coluna<LADOTAB && !(testavalor(nivel, coluna)); coluna++);//avança ao longo da linha a partir da coluna especificada até encontrar uma posição onde a rainha que está para ser colocada não seja atacada nem ataque nenhuma das rainhas que foram colocadas anteriormente ou até se acabar o laço
  if(coluna<LADOTAB){//foi achada uma posição segura na linha "nível" do tabuleiro
    solucao_em_teste[nivel]=coluna;//coloca a rainha na posição encontrada
    if(nivel<(LADOTAB-1)) percorre(nivel+1, 0);//se nível não é a última linha do tabuleiro, percorre a próxima
    else if(nivel==LADOTAB-1){//se nível é a última linha, foi achada uma solução
      for(j=0; j<LADOTAB; j++) solacum[n_solacum][j]=solucao_em_teste[j];//transferência da solução para a matriz solacum e incremento no número de soluções
      n_solacum++;
   if(!(simetria=='s' || simetria=='S')) elimina_simetricas(); /* Perceba que aqui está a única interface entre o bloco de funções que gera soluções e o bloco que elimina as simtetrias, que faz com que sejam impressas apenas soluções assimétricas entre si. Para desativar no programa essa parte de testes de simetria e ver a impressão do conjunto total de soluções, basta transformar esta linha do programa em comentário */
      if(coluna<LADOTAB-1) percorre(nivel, coluna+1);//se não está ainda na última posição da última linha, ver se há ainda outras soluções 
      else if(coluna==LADOTAB-1) volta(nivel);//se chegou a última posição da última linha, volta pra linha anterior e para retomar o percurso do tabuleiro (ver na função volta)
      else {//algo deu errado no laço se isso ocorre
        puts("Erro: percorre_33_e_meio");
        printf("n_solacum=%d\nultima solucao:  ", n_solacum);
        for(j=0; j<LADOTAB; j++) printf("%d", solacum[n_solacum-1][j]);
        printf("\n");
        exit(EXIT_FAILURE);
      }
    }
    else {
      puts("Erro: percorre_1");
      exit(EXIT_FAILURE);
    }
  }
  else if(coluna==LADOTAB){//não foi achada nenhuma posição segura na linha "nível" chama a função volta para retomar a busca. Isso, claro, Se nivel não for a primeira linha, Mas, se a primeira rainha a ser colocada no tabuleiro não encontra posição segura, Algo está MUITO errado
    if(nivel) volta(nivel);
    else{
      puts("Erro: percorre_4 (bizarro!)");
      return;
    }
  }
  else{//se isso acontecer, algo deve estar errado com o laço
    puts("Erro: percorre_2");
    exit(EXIT_FAILURE);
  }
}


void volta(int nivel){//retoma a busca a partir do nível anterior quando o nível que estava sendo avaliado se acaba
  if(nivel){//não há como "voltar" paraum um nível anterior à primeira linha
    if(solucao_em_teste[nivel-1]==(LADOTAB-1)) volta(nivel-1);//se o nível anterior também já estava na última coluna, volta para o anterior a ele. É nessa parte que a função é recursiva
    else if(solucao_em_teste[nivel-1]<LADOTAB-1) percorre(nivel-1, solucao_em_teste[nivel-1]+1);//caso contrário, retomar o percurso a partir da próxima coluna da linha anterior
    else{//algo deu errado, pois o nivel extrapolou as linhas do tabuleiro
      puts("Erro: volta_1");
      printf("nivel atual: %d\n", nivel);
      exit(EXIT_FAILURE);
    }
  }
}


int testavalor(int casa, int valor){//testa se a rainha pode ser inserida na linha "casa", coluna "valor" do tabuleiro
  int i;
  for(i=0; i<casa; i++){//testa se tem alguma rainha:
    if(valor==solucao_em_teste[i]) return 0;//na mesma coluna
    if(((solucao_em_teste[i]+casa-i)<LADOTAB) && valor==(solucao_em_teste[i]+casa-i)) return 0;//na  diagonal "principal"
    if(((solucao_em_teste[i]+i-casa)>=0) && valor==(solucao_em_teste[i]+i-casa)) return 0;//nadiagonal "secundária"
  }
  return 1;//significa que é segura colocar a rainha na posição dada como argumento
}
/* GERAÇÃO DE SOLUÇÕES - FIM */





/* ESTUDOS DE SIMETRIA E REDUNDÂNCIA - INÍCIO */

void elimina_simetricas(){//busca em solacum soluções pertencentes ao mesmo grupo de simetria da última solução encontrada e, se encontrar, elimina a solução mais recente das duas, que é a última solução que foi encontrada. Como 
  int i,j,k,l;
  int estudo[LADOTAB];
  for(i=0; i<LADOTAB; i++) estudo[i]=solacum[n_solacum-1][i];//criaocteto só recebe ponteiros para vetores simples
  criaocteto(estudo);//gera o grupo de simetria do vetor "estudo", que equivale à solução mais recente encontrada(ver laço acima)
  for(i=0; i<n_solacum-1; i++){//se alguma das soluções já acumuladas anteriormente for igual a alguma das soluções contidas em octeto, então essa solução é simétrica a estudo, ou melhor, solacum[n_solacum][0~LADOTAB]
    for(j=1; j<8; j++){
      for(k=0; k<LADOTAB && octeto[j][k]==solacum[i][k]; k++);
      if(k==LADOTAB){
        for(l=0; l<LADOTAB; l++) solacum[n_solacum-1][l]=LADOTAB;
        n_solacum--;
        break;//como a simetria é testada assim que a nova solução aparece, e sabendo que, se A e B são soluções pertencentes ao mesmo grupo de simetria de C, então A e B são simétricas entre si, não deve haver mais de uma solução entre as que já foram armazenadas(as que estão em linhas de solacum estritamente menores que n_solacum-1) então, ao achar a primeira simetria, pode-se quebrar o laço. Ou isso ou a solução em estudo é uma nova solução assimétrica
      }
    }
    if(k==LADOTAB) break;//continuação da quebra do laço justificada acima
  }
}


 void criaocteto(int *solucao){//gera grupo de simetria do vetor "solucao"
  int i,j,k;
  for(i=0; i<LADOTAB; i++) octeto[0][i]=solucao[i];
  for(i=1; i<8; i++){
    if(i%2){
      for(j=0; j<LADOTAB; j++) octeto[i][j]=LADOTAB-1-octeto[i-1][j];//gera imagens especulares das solução contida na linha anterior de octeto
    }
    else{
      for(j=0; j<LADOTAB; j++){//gera a rotação anti-horária da solução de duas linhas anteriores de octeto
        k=octeto[i-2][j];
        octeto[i][LADOTAB-1-k]=j;
      }
    }
  }
}


void descobre_redundancias(){//busca por simetrias redundantes por meio da c gerando todos os grupos de simetria a partir 
  int i,j,k,l,m;
  int sol[LADOTAB];
  for(m=0; m<n_solacum; m++){
    for(i=0; i<LADOTAB; i++) sol[i]=solacum[m][i];//neste ponto, o programa já achou todas as soluções e eliminou, dentre elas, as que eram simétricas. Dessa forma, o que a matriz solacum contém agora é o conjunto das soluções assimétricas. 
    criaocteto(sol);//aqui, é gerado o grupo de simetria de cada uma das soluções assimétricas...
    for(i=0; i<8; i++){
      for(j=i+1; j<8; j++){
        for(k=0; k<LADOTAB && octeto[i][k]==octeto[j][k]; k++);//...e, um a um, esses grupos são testado internamente, para ver se entre sua soluções simétricas há redundância.
        if(k==LADOTAB){
          printf("Solucao %d: octeto[%d]=octeto[%d]. Veja abaixo:\n", m+1, i, j);//uma vez que foi achada, a redundância é impressa na saída padrão
          for(k=0; k<LADOTAB; k++){
            for(l=0; l<LADOTAB; l++){
              if(l!=octeto[i][k]) printf("- ");
              else printf("R ");
            }
            printf("\n");
          }
          printf("\n");
        }
      }
    }
  }
}
/* ESTUDOS DE SIMETRIA E REDUNDÂNCIA - FIM */




/* IMPRESSÃO DE SOLUÇÕES */
void imprime(){//imprime a matriz de solução assimétricas - ou simétricas, se for suprimida a linha de percorre que chama elimina_simetricas()
  int i,j,k;
  for(i=0; i<n_solacum; i++){
    printf("Solucao %d:\n", i+1);
    for(j=0; j<LADOTAB; j++){
      for(k=0; k<LADOTAB; k++){
        if(k!=solacum[i][j]) printf("- ");
        else printf("R ");
      }
      printf("\n");
    }
    printf("\n");
    if(!((i+1)%35)){
      getchar();
      getchar();
    }
  }
}