Sudoku ramificació i poda
El Trencaclosques 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ó que no es pot repetir el mateix nombre en la mateixa fila, columna o subgrup de 9. Un sudoku disposa de diverses cel·les amb un valor inicial, de manera que hem de començar a resoldre el problema a partir d'aquesta solució parcial sense modificar cap de les cel·les inicials.
Taula de continguts |
[modifica] Estratègia de resolució amb Ramificació i poda
El Trencaclosques del Sudoku no és un problema d'optimització, per tant no recorrerem l'arbre de cerca guiant-nos amb una funció de costos. A diferència dels algorismes de tornar enrere, amb la Ramificació i Poda podem fer un recorregut per nivells de l'arbre d'exploració gestionant els nodes vius amb una cua.
El tauler del Sudoku per resoldre ve 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 d'expansió, 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 construint 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 comprova 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 problema.
[modifica] Estructures de dades necessàries
Tenint en compte que un Sudoku pot tenir diverses solucions, implementarem l'algorisme en conseqüència. En cada iteració de l'algorisme necessitarem saber l'estat de la solució parcial, per tant necessitarem:
- La solucio parcial fins al moment.
- Informació pel que fa 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 nodes vius serà:
Vius: cua de NODE;
[modifica] 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 node = 9, un fill per cada possible valor de la cel·la i,j.
[modifica] 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;
[modifica] 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;
FMentres;
k := 1;
Mentres (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); //Comprovem el subgrup de 3x3
Mentres ( k < correspondencia3x3(i) + 3 ^ valid ) Fer
Mentres ( 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 esbrinar la cel·la inicial a partir de la qual 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;
[modifica] Altres estragègies de resolució
[modifica] Bibliografia
- Martí, Narciso; Verdejo, Alberto; Ortega Yolanda. Estructuras de datos y métodos algorítmicos: ejercicios resueltos (en castellà), 2003.
