Sudoku backtracking

El famós joc del Sudoku consistix en reblir una gaveta de 9 x 9 celes dispostes en 9 subgrups de 3 x 3 celes, en números de l'1 al 9, atenent a la restricció de que no es deu repetir el mateix número en la mateixa fila, columna o subgrup de 9.

Un Sudoku dispon de vàries celes en un valor inicial, de modo que devem escomençar a resoldre el problema a partir d'esta solució parcial sense modificar cap de les celes inicials.

Estratègia de resolució usant Backtracking

El tauler del Sudoku a resoldre ve dau per una matriu “Sol [1..9,1..9] de 0..9” a on Sol[i, j] representa el valor que pren dita cela, corresponent-se el valor 0 en una casella buida.

S'utilisarà una matriu auxiliar “inicial[1..9, 1..9] de Bool” a on inicial[i, j] representa una cela en valor inicial que no es pot modificar i es correspon en la cela “Sol[i, j]”.

A l'hora de ramificar l'arbre d'exploració, solament ho farem si la solució parcial que estem atenent és k-prometedora, açò és, si a partir de dita solució parcial podrem seguir construint solucions parcials. Per a atendre a este punt, utilisarem una funció auxiliar denominada “és_factible”.

La funció “és_factible” comprova per a una cela determinada, que no es repetixca el seu valor en la mateixa fila, columna o subgrup de 3x3, atenent aixina a la restricció que comentàvem en la descripció detallada del problema.

Ya que un Sudoku Pot tindre vàries solucions, implementarem l'algoritme en conseqüència.

Arbre d'exploració

L'arbre d'exploració generat tindrà les següents característiques:

• Altura = m + 1:

Sent m el número de caselles buides inicialment.

• N.º de Fills de cada nodo = 9:

Un fill per cada possible valor de la cela i j.

Implementació en Pseudocódigo

Proc sudoku_VA (i, j: Nat; sol[1..9, 1..9] de 0..9; inicial[1..9, 1..9] de Bool)
   Si (inicial [i, j] = Fals) Llavors
      Para (k := 1) Fins a 9 Fer
         sol[i, j] := k;                                 //marcar
         Si (és_factible (i, j, sol)) Llavors
            Casos
               i = 9 ^ j = 9 -> mostrarPorPantalla(sol);
               i < 9 ^ j = 9 -> sudoku_VA (i+1, 1, sol, inicial);
               i <= 9 ^ j < 9 -> sudoku_VA( i , j+1, sol, inicial);
            FinCasos;
         FinSi;
         sol[i, j] : = 0;                                //Desmarcar
      FinPara;
   En Un atre Cas //inicial[i, j] = Cert
      Casos
         i = 9 ^ j = 9 -> mostrarPorPantalla(sol);
         i < 9 ^ j = 9 -> sudoku_VA (i+1, 1, sol, inicial);
         i <= 9 ^ j < 9 -> sudoku_VA( i , j+1, sol, inicial);
      FinCasos;
   FinSi;
FinProc;

Cridada Inicial

Proc sudoku (sol[1..9, 1..9] de 0..9)
   Var 
      inicial[1..9, 1..9] de Bool;
   FinVar;
   Para (i := 1) Fins a 9 Fer
      Para (j := 1) Fins a 9 Fer
            inicial[i, j] := Sol[i, j] != 0;
      FinPara;
   FinPara;
   sudoku_VA(1, 1, sol, inicial);
FinProc;

Funcions Auxiliars

Funció auxiliar que comprova la factibilidad d'una solució parcial.

Fun és_factible (i, j : Nat; sol[1..9, 1..9] de 0..9) DEV Bool
   Var
      valgut : Bool;
      k,l: Nat;
   FinVar;
   valgut := True;
   k := 1;
   Mentres (k <= 9 ^ valgut) Fer                   //Comprovem la columna
      Si ( sol[i, j] = sol[k, j] ^ k != i ){
         Valgut := Fals;
      FinSi;
      k := k + 1;
   FinMientras;
   l := 1;
   Mentres (l <= 9 ^ valgut) Fer                   //Comprovem la fila
      Si ( sol[i, j] = sol[i, l] ^ l != j ){
         Valgut := Fals;
      FinSi;
      l := l + 1;
   FinMientras;
   //                         Lo anterior podria compactar aixina, en un sol while que comprova files i columnes..
   // Mentres (k<=9 ^ valgut) Fer
   //    Si ( (sol[i, j] = sol[k, j] ^ k != i) v (sol[i, j] = sol[i, k] ^ k != j))
   //       Valgut := Fals;
   //    FinSi;
   // FinMientras;
   k := correspondència3x3(i);
   l :=  correspondència3x3(j);                          //Comprovem el subgrup de 3x3

Mentres ( k < correspondència3x3(i) + 3 ^ valgut ) Fer //per raons d'eficiència pot abans d'esta etapa, assignar a una variable

      Mentres ( l < correspondència3x3(j) + 3 ^ valgut) Fer // el valor de correspondència3x3(x) siga x=i o = j; aixina s'eviten 2 cridades
         Si ( sol[i, j] = sol[k, l] ^ i != k ^ j != l) Llavors // a dita funció traduint-se en millor eficiència.
            valgut := Fals;
         FinSi;
         l := l + 1;
      FinMientras;
      k := k + 1;
      l :=  correspondència3x3(j);
   FinMientras;
   Tornar valgut;
FinFun;

Funció auxiliar que s'utilisa per a averiguar la cela inicial des de la que farem la comprovació de factibilidad d'una cela determinada en el seu corresponent subgrup de 3x3 celes.

Fun correspondència3x3 (i: Nat) DEV Nat
   Var
      k : Nat;
      resultat: Nat;
   FinVar;
   Si ( i MOD 3 = 0) Llavors 
      k := (i DIV 3);
   En Un atre Case
      k := ( I DIV 3) + 1;
   FinSi;
   Casos
      k = 1 -> resultat := 1;
      k = 2 -> resultat := 4;
      k = 3 -> resultat := 7;
   FinCasos;
   Tornar resultat;
FinFun;

Vore també

• Algoritmes per a la resolució de sudokus
• Sudoku ramificació i poda