Enrere Mòdul 4
Fonaments de Programació. Llenguatge C/C++---
Pràctica  Resum teòric Exercicis
Pràctica d'ampliació Annex: la depuració

 
Les vuit reines

Aquest és un dels problemes més utilitzats per mostrar una tècnica de programació que s'anomena algorismes de tornada enrera o, en anglès, backtracking. 

 
Desenvolupament de la pràctica

Creeu un nou arxiu font C anomenat m4pa1c. i escriviu el següent codi:

El problema de les vuit reines consisteix en col·locar en un tauler d'escacs (que té 8x8=64 caselles) vuit reines de forma que cap d'elles amenaci a cap altra.

Un mètode exhaustiu de trobar totes les posicions possibles de col·locar 8 reines en un tauler d'escacs i provar una a una si es compleix la condició és un mètode molt poc eficient ja que hi ha 4.426.165.368 de possibilitats.

El mètode exhaustiu es podria millorar si assignem a cada una de les reines una columna del tauler i només ens preocupem de triar una fila per cadascuna de les reines. El número de possibilitats ha baixat a 88=16.777.216.

Si una vegada col·locada la reina de la columna 1 en la fila 4, per exemple, prohibim que la fila 4 torni a sortir, només tenim 7 possibilitats per a la segona reina. Si prohibim que la tercera reina estigui a la mateixa fila que la primera o que la segona, tenim 6 possibilitats per a la tercera reina, és a dir, només haurem de provar 8!=8·7·6·5·4·3·2·1=40.320.

El mètode de tornada enrera consisteix en explorar solucions parcials i acceptar-les o refusar-les. Una solució parcial és refusada si ella mateixa no compleix les condicions que s'imposen a una solució o bé cap de les solucions que es poden formar a partir d'ella les compleix. En el cas del problema de les vuit reines s'actuaria de la següent forma:

  1. seleccionem una casella per a la reina 1. (en aquest cas totes són possibles en principi)
  2. seleccionem una casella per a la reina 2, si no hi ha caselles disponibles tornar al punt 1.
  3. es comprova si la parella reina1 i reina 2 és possible, en cas contrari tornar al punt 2.
  4. seleccionem una casella per a la reina 3.
  5. ...

En l'esquema de l'esquerra es mostra un exemple d'exploració seguint el procés de tornada enrera pel problema de les quatre reines, un problema reduït, però que ens servirà per comprendre bé el procés. 

En primer lloc, assigna a la primera reina la fila 1. 
En segon lloc, assigna a la segona reina la fila 1, com que les dues reines s'amenacen, aquesta posició no és bona i es refusa i, per tant, no segueix l'exploració per aquesta branca de l'arbre.
S'assigna a la segona reina la fila 2 i es refusa també.
S'assigna a la segona reina la fila 3 i, com que no hi ha amenaça se segueix explorant aquesta branca. Es comproven totes les posicions de la tercera reina i cap d'elles compleix la situació, per tant, es refusa també la solució parcial 13.

Aquest procediment se segueix fins trobar la primera solució que, com es pot veure al diagrama de l'esquerra, és la 2,4,1,3 i que correspon a la següent situació:

La primera solució trobada en el cas de les vuit reines és: 1 5 8 6 3 7 2 4 que correspon a la següent posició:

El codi per resoldre aquest problema és el següent:

// m4pa1.c  - El problema de les n reines -

#include <stdio.h>
#include <stdlib.h>
#define NUM_REINES 8      //canviar aquesta línia per

 //canviar el nombre de reines

 

 

void explorar(int*,int, int);

int comprova(int*, int ); 


int main(){

    int sol[NUM_REINES]; //vector solució

    system("clear");
    explorar(sol,0,0);

    return 0;
}

 

void explorar(int *sol, int n, int ct){

    do{
       sol[n]=ct;
       if (comprova(sol, n)){
         if (n==NUM_REINES-1){
            printf("FIN\n");
            for(ct=0;ct<NUM_REINES;ct++){
                printf("%d ",sol[ct]);
            }
            printf("\n");
            exit(0);
         }
         explorar(sol,n+1,0);
       }
       if (ct==NUM_REINES-1){

         do{
             n=n-1;
         }while(sol[n]==NUM_REINES-1);
         if(n<0){
             printf("No hi ha solució\n\n");
             exit(1);
         }
         explorar(sol,n,sol[n]+1);
       }
       ct=ct+1;
    }while(1);
}


int comprova(int *sol, int n){
    int ct;

    for(ct=0;ct<n;ct++){
       if (sol[ct]==sol[n]) return 0;
       if (sol[ct]-sol[n]==ct-n) return 0;
       if (sol[ct]-sol[n]==n-ct)return 0;

    }
    return 1;
}

 

Captura de l'execució del programa.

 

Explicació del programa

El programa va col·locant les reines en el vector sol[]. Si sol[0]=2 vol dir que es col·loca la reina 0 en la fila 2. Cada reina té assignat el mateix número que la columna on està situada.

La funció comprova té com arguments el vector sol[] i un nombre enter n i aquesta funció retorna 0 en el cas que la reina n amenaci a alguna reina ja col·locada:

Hi ha dues possibilitats perquè la funció torni un 0 (amenaça):

  • mateixa fila.
  • mateixa diagonal.

La funció principal que fa tot el càlcul és la funció explorar(). Aquesta funció és una funció recursiva ja que es crida a sí mateixa. La funció explorar(sol, n, ct) es crida si les n reines anteriors a n (0,...(n-1)) ja estan ben col·locades i el que fa és explorar si la posició ct és admissible per a la reina n. Si aquesta posició és bona i no s'ha col·locat ja l'última reina, explora la següent reina des de la posició 0.