Sudoku ramificació i poda

De Viquipèdia

Icono de copyedit

Nota: L'article necessita algunes millores en el contingut o l'estil:

fallen el títol, l'estructura, l'ortografia, falta la introducció...


Taula de continguts

[edita] Descripció detallada del problema

El famós joc del 'Sudoku consisteix en omplir un quadre de 9x9 cel·les organtizades en 9 subgrups de 3x3 cel·les, amb nombres de l'1 al 9, atenint-se a la restricció de que no es pot repetir el mateix nombre en la mateixa fila, columna o subgrup de 9.
Un Sudoku disposa de vàries cel·les amb un valor inicial, així que hem de començar a resoldre el problema a partir d'aquesta solució parcial sense modificar cap de les cel·les inicials.

[edita] Estratègia de resolució amb Ramificació i poda

El joc del Sudoku no és un problema d'optimització, per tant no recorrerem l'àrbre de cerca guiant-nos amb una funció de costos.
A diferència dels algoritmes de Tornar Enrere, amb Ramificació i Poda podem fer un recorregut per nivells de l'àrbre d'exploració, gestionant els nòdes vius amb una cua.
El tauler del Sudoku per resoldre vé donat per una matriu "Sol [1..9,1..9] de 0..9" on Sol[i,j] representa el valor que pren l'esmentada cel·la, on el valor zero es correspon amb una casella buida.
S'utilitzarà en aquest apartat una matriu auxiliar "inicial[1..9,1..9] de Bool" on inicial[i,j] representa una cel·la amb valor inicial que no es pot modificar i es correspon amb la cel·la "Sol[i,j]".
A l'hora de ramificar l'[Arbre (teoria de gràfs)|arbre] d'exploració, només ho fem si la solució parcial que estem atenent és k-prometedora, això vol dir, si a partir d'aquesta solució parcial podrem seguir construïnt solucions parcials. Per atendre aquest punt, utilitzarem la funció auxiliar denominada es_factible, detallada en l'exemple del Sudoku amb Tornar Enrere.
La funció es_factible comproba per una cel·la determinada, que no es repeteixi el seu valor en la mateixa fila, columna o subgrup de 3x3, atenent-se així a la restrició que comentàvem en la descripció del probelma.
Donat que un Sudoku pot tindre varies solucions, implementarem l'algorisme en conseqüència.

[edita] Estructures de dades necessàries

Encada iteració de l'algorisme necessitarem saber l'estat de la solució parcial, per tant necessitarem:
  1. La solucio parcial fins al moment.
  2. Informació en quant a la casella en la que ens trobem (fila i columna);

NODE = Registre

       fila, columna : Nat;
       Sol : Vector [1..9, 1..9] de 0..9;
       FRegistre;
La cua per gestionar els nòdes vius serà:
Vius: cua de NÒDE;

[edita] Arbre d'exploració

L'arbre d'exploració tindrà les següents característiques:
  • Alçada = m+1, sent m el nombre de caselles buides inicialment.
  • Nombre màxim de fills de cada nòde = 9, un fill per cada possible valor de la cel·la i,j.

[edita] Implementació en Pseudocodi

Fun sudoku_RiP ( sol[1..9, 1..9] de 0..9)
   Var
      Vius: cua de NODE;
      X,Y: NODE;
      inicial[1..9, 1..9] de Bool;
   FVar;
   Vius := cua_buida();            //Preparem l'arrel de l'arbre d'exploració
   X.fila := 1;            
   X.columna := 1;
   X.sol := sol;
   demanar_veg (Vius, X);
   Per (i := 1) Fins 9 Fer         //Inicializació de la matriu amb els inicials
      Per (j := 1) Fins 9 Fer
         Si (Sol[i, j] != 0) Llavors
            Inicial[i, j] := Fals;
         En altre cas
            Inicial[i, j] := Cert;
         FSi;
      FPer;
   FPer;    
   Mentre ( cua_buida(Vius) = Fals ) Fer
      X := atendre (Vius);
      Si (inicial [X.fila, X.columna] = Fals) Llavors
         Per (k := 1) Fins 9 Fer
            X.sol[X.fila, X.columna] := k;
            Si (es_factible (X.fila, X.columna, X.sol)) Llavors
               Casos
                  X.fila = 9 ^ X.columna = 9 -> mostrarPerPantalla( X.sol);
                  X.fila < 9 ^ X.columna = 9 -> Y.sol := X.sol;
                                                Y.fila := X.fila + 1;
                                                Y.columna := 1;
                                                demanar_veg(Vius, Y);
                  X.fila <= 9 ^ X.columna < 9 -> Y.sol := X.sol;
                                                 Y.fila := X.fila;
                                                 Y.columna := Y.columna + 1;
                                                 demanar_veg(Vius, Y);
               FCasos;
            FSi;
         FPer;
      En Altre Cas //inicial[X.fila, X.columna] = Cert
         Casos
            X.fila = 9 ^ X.columna = 9 -> mostrarPerPantalla( X.sol);
            X.fila < 9 ^ X.columna = 9 -> Y.sol := X.sol;
                                          Y.fila := X.fila + 1;
                                          Y.columna := 1;
                                          demanar_veg(Vius, Y);
            X.fila <= 9 ^ X.columna < 9 -> Y.sol := X.sol;
                                           Y.fila := X.fila;
                                           Y.columna := Y.columna + 1;
                                           demanar_veg(Vius, Y);
         FCasos;
      FSi;
   FMentres;        
FFun;


[edita] Funcions Auxiliars

Funció auxiliar que comprova la factibilitat d'una solució parcial.
Fun es_factible (i, j : Nat; sol[1..9, 1..9] de 0..9) DEV Bool
   Var 
      valid : Bool;
      k, l : Nat;
   FVar;
   valid := Cert;
   k := 1;
   Mentres (k <= 9 ^ valid) Fer                  //Comprovem la fila
      Si ( sol[i, j] = sol[i, k] ^  k != j ) Fer
         valid := Fals;
      FSi;
   FMientres;
   k := 1;    
   Mientres (k <= 9 ^ valid) Fer                   //Comprovem la columna 
      Si ( sol[i, j] = sol[k, j] ^ k != i ){
         Valid := Fals;
      FSi;
   FMentres;
   k := correspondencia3x3(i);
   l :=  correspondencia3x3(j);                          //Comprobamos el subgrupo de 3x3
   Mentres ( k < correspondencia3x3(i) + 3 ^ valid ) Fer 
      Mentras ( l < correspondencia3x3(j) + 3 ^ valid) Fer
         Si ( sol[i, j] = sol[k, l] ^ i != k ^ j != l) Llavors
            valid := Fals;
         FSi;
      FMentres;
   FMentres;
   Retornar valid;
FFun;


Funció auxiliar que s'utilitza per averiguar la cel·la inicial des de la que farem la comprovació de factibilitat d'una cel·la determinada en el seu corresponent subgrup de 3x3 cel·les.
Fun correspondencia3x3 (i: Nat) DEV Nat
   Var
      k : Nat;
      resultat: Nat;
   FVar;
   Si ( i MOD 3 = 0) Llavors 
      k := (i DIV 3);
   En Altre Cas
      k := ( I DIV 3) + 1;
   FSi;
   Casos
      k = 1 -> resultat := 1;
      k = 2 -> resultat := 4;
      k = 3 -> resultat := 7;
   FCasos;
   Retornar resultat;
FFun;

[edita] Altres estragègies de resolució

  • Sudoku backtracking

[edita] Bibliografia

  • Plantilla:Ref-llibre